Arvotaan r lukua joukosta {1, 2,..., N}. Oletetaan tietenkin että 1 <= r <= N. Mikä on odotusarvo pisimmälle ketjulle peräkkäisiä kokonaislukuja näiden r:n luvun joukossa?
Simuloimalla sain tällaisen kuvaajan (r vaaka-akselilla ja (simuloitu) odotusarvo pystyakselilla), kun N=100:
http://aijaa.com/kwZvJY
Tarkkoja laskelmia (r: E(Cmax):
N=2
1: 1
2: 2
------------
N=3
1: 1
2: 5/3
3: 3
------------
N=4
1: 1
2: 3/2
3: 5/2
4: 4
Simuloimalla sain tällaisen kuvaajan (r vaaka-akselilla ja (simuloitu) odotusarvo pystyakselilla), kun N=100:
http://aijaa.com/kwZvJY
Tarkkoja laskelmia (r: E(Cmax):
N=2
1: 1
2: 2
------------
N=3
1: 1
2: 5/3
3: 3
------------
N=4
1: 1
2: 3/2
3: 5/2
4: 4
Vastaukset 12
Vanhimmat
Keksin tällaiset kaavat tapauksille r=2 ja r = N-1, (ensimmäiset epätriviaalit tapaukset alku- ja loppupäästä, kun N>=2 [kun N=2, niin "loppupää" onkin ensin :D ja kun N=3 samat] )
-----------------------------
Kun r=2, niin (N 2)/N
------------------------------
Kun r=N-1, niin parillisille N kaava (3N-2)/4 ja parittomille (N(3N-2)-1)/(4N).
Tämä on yhteydessä oktagonaalilukuihin jollain tavalla.
------------------------------------
Arvolle r=3 löytyi nyt kaava (N 6)/N.
Lisää kaavoja löytynyt:
r = 3:
1 6/N
-----------------------------------
r = 4:
1 36/N - 36/(N-1) 12/(N-2)
-----------------------------------------------
r = 5:
= 1 220/N - 360/(N-1) 180/(N-2) - 20/(N-3)
----------------------------------------------
Nämä ovat siis vain löydetty siten, että arvasin, että kaavassa osoittaja on jokin polynomi (nimittäjähän on N:n ja r:n binomikerroin) ja sitten selvitin sen arvoista. Näyttäisi, että sinne tulee aina r:n asteen polynomi.
Niiden täytyy alkaa "keskivaiheilla jotenkin summautumaan" ja kaavan lyhenemään, jotta päästään esimerkiksi tuohon N-1:n kaavaan.
Melko intuitiivisesti selvää, että N:n kasvaessa kaikki "alkupään" (jotka eivät siis lähellä N:ää kun se kasvaa, ja kun se kasvaa niin mikäänhän ei ole enää sitä lähellä jostain asti) odotusarvot (siis se kaava arvolla r) lähenevät 1:stä. Eihän siellä paljon tule pitempiä pötköjä kuin ykkösen pituisia peräkkäisiä, jos N on suuri ja otetaan vain "vähän" lukuja.
Toisaalta tuo toiseksi viimeinen (r=N-1) lähenee 3/4N:ää. Tämäkin on jotenkin intuitiivisesti uskottavaa: Poistetaan vain yksi luku, jota ei oteta. 1...N jakautuu kahteen osaan, joista pitempi on se pisin ketju. Se voidaan poistaa siitä keskeltä, jolloin saadaan 1/2 ja sitten jotenkin keskiarvoistamalla kumpikin puolikas (symmetriset) saadaan puolikas pois puolikkaasta ja toiselle puolelle eli 3/4.
Tässähän on periaatteessa symmetria näiden r:n arvojen suhteen, mutta en ainakaan suoraan näe miten se ilmenee kaavassa.
r = 6:
1 1230/N - 2700/(N-1) 2040/(N-2) - 600/(N-3) 60/(N-4)
Kyllä nämä jotain erikoisia lukuja nämä kertoimet ovat! Selvästikin joka toinen tulee miinuksella ja joka toinen plussalla. Ja N-(r-2):een asti mennään. Tai toisin sanottuna siinä on r termiä tuossa summassa. Tämähän tulee osamurtohajotelmasta. Ykkönen taitaa olla se /(N-r 1). (N-r 1):hän nimittäin supistuu aina pois tuosta alkuperäisestä kaavasta, kun sen niille polynomeille kirjoittaa [N(N-1)(N-2)...(N-r 1)/r! nimittäjässä], tai siis niin näyttäisi käyvän.
Meneekö tuo osamurtohajotelma muuten aina noin nätisti, että siitä tulee noin siisti? Vai onko tässä kaavassa senkin nojalta jotain erikoista?
Onkohan jotenin odotusarvon lineaarisuus pelissä. Ja tämän voisikin laskea osissa. Hhhmmmmm.....
r = 7:
1 6216/N - 16800/(N-1) 16800/(N-2) - 7560/(N-3) 1470/(N-
4) - 84/(N-5)
-----------------
Kirjoitan nyt N:n tilalle x:n kun tuli laitettua se ja en jaksa en enää kirjoittaa uudestaan.
------------------
r = 8:
1 112/(-6 x) - 2520/(-5 x) 19320/(-4 x) - 65800/(-3 x) 110880/(-2 x) - 90552/(-1 x) 28616/x
----------------------------------
Taitaa suuremmissa laskuissa alkaa tulemaan Pythonin floatissa epätarkkuutta mutta nuo nyt ainakin pitäisi olla oikein.
Mites jos siitä puolesta välistä koitetaan arvioida tuota odotusarvoa eli r=N/2 (kok. luku). Nämä on nyt simuloitu (näin suurille ihan turha yrittää tarkkaan laskea tarkkaa arvoa, jos ei sitten keksi kaavaa!), tässä on siis N/2: (odotusarvo)
500: 9.280000
550: 9.451000
600: 9.531000
650: 9.547000
700: 9.788000
750: 9.815000
800: 9.871000
850: 10.039000
900: 10.248000
950: 10.153000
1000: 10.275000
1050: 10.319000
1100: 10.358000
1150: 10.461000
1200: 10.565000
1250: 10.567000
1300: 10.656000
1350: 10.685000
1400: 10.832000
1450: 10.853000
1500: 10.947000
1550: 10.776000
1600: 10.984000
1650: 11.018000
1700: 11.125000
1750: 11.145000
1800: 11.269000
1850: 11.095000
1900: 11.214000
1950: 11.317000
2000: 11.394000
2050: 11.362000
2100: 11.350000
2150: 11.305000
2200: 11.439000
2250: 11.338000
2300: 11.541000
2350: 11.600000
2400: 11.486000
2450: 11.667000
Kyllä se pikkuhiljaa kasvaa ja kasvaa, mutta näyttäisi, että ei se ole mikään positiivinen prosenttiosuus N:stä ole. Pitäisipäkin kokeilla esim. r=N-2 tulisiko tällä jokin raja-arvo, kun jakaa N:llä. Pitäisikin myös keksiä merkintä tuolle odotusarvolle, merkitään sitä siis nyt vain E(N, r).
N = 1000, E(N,r) = 611.223000, E(N,r)/N = 0.611223
N = 1100, E(N,r) = 663.302000, E(N,r)/N = 0.603002
N = 1200, E(N,r) = 737.113000, E(N,r)/N = 0.614261
N = 1300, E(N,r) = 802.891000, E(N,r)/N = 0.617608
N = 1400, E(N,r) = 861.760000, E(N,r)/N = 0.615543
N = 1500, E(N,r) = 916.566000, E(N,r)/N = 0.611044
N = 1600, E(N,r) = 984.862000, E(N,r)/N = 0.615539
N = 1700, E(N,r) = 1034.190000, E(N,r)/N = 0.608347
N = 1800, E(N,r) = 1096.621000, E(N,r)/N = 0.609234
N = 1900, E(N,r) = 1153.775000, E(N,r)/N = 0.607250
N = 2000, E(N,r) = 1214.472000, E(N,r)/N = 0.607236
N = 2100, E(N,r) = 1276.475000, E(N,r)/N = 0.607845
N = 2200, E(N,r) = 1364.307000, E(N,r)/N = 0.620140
N = 2300, E(N,r) = 1407.446000, E(N,r)/N = 0.611933
N = 2400, E(N,r) = 1457.775000, E(N,r)/N = 0.607406
N = 2500, E(N,r) = 1513.825000, E(N,r)/N = 0.605530
N = 2600, E(N,r) = 1577.757000, E(N,r)/N = 0.606830
N = 2700, E(N,r) = 1629.256000, E(N,r)/N = 0.603428
N = 2800, E(N,r) = 1711.332000, E(N,r)/N = 0.611190
N = 2900, E(N,r) = 1764.590000, E(N,r)/N = 0.608479
N = 3000, E(N,r) = 1812.446000, E(N,r)/N = 0.604149
N = 3100, E(N,r) = 1903.929000, E(N,r)/N = 0.614171
N = 3200, E(N,r) = 1948.071000, E(N,r)/N = 0.608772
Joo, kyllä se raja-arvo jotain 0.6 nolla yksi tai kaksi on, 0.61 veikkaisin.
Jännä olisi tietää nuo raja-arvot N-m kaikilla m.
Sehän alkaa 0.75, 0.61, ....
Mites jos siitä puolesta välistä koitetaan arvioida tuota odotusarvoa eli r=N/2 (kok. luku). Nämä on nyt simuloitu (näin suurille ihan turha yrittää tarkkaan laskea tarkkaa arvoa, jos ei sitten keksi kaavaa!), tässä on siis N/2: (odotusarvo)
500: 9.280000
550: 9.451000
600: 9.531000
650: 9.547000
700: 9.788000
750: 9.815000
800: 9.871000
850: 10.039000
900: 10.248000
950: 10.153000
1000: 10.275000
1050: 10.319000
1100: 10.358000
1150: 10.461000
1200: 10.565000
1250: 10.567000
1300: 10.656000
1350: 10.685000
1400: 10.832000
1450: 10.853000
1500: 10.947000
1550: 10.776000
1600: 10.984000
1650: 11.018000
1700: 11.125000
1750: 11.145000
1800: 11.269000
1850: 11.095000
1900: 11.214000
1950: 11.317000
2000: 11.394000
2050: 11.362000
2100: 11.350000
2150: 11.305000
2200: 11.439000
2250: 11.338000
2300: 11.541000
2350: 11.600000
2400: 11.486000
2450: 11.667000
Kyllä se pikkuhiljaa kasvaa ja kasvaa, mutta näyttäisi, että ei se ole mikään positiivinen prosenttiosuus N:stä ole. Pitäisipäkin kokeilla esim. r=N-2 tulisiko tällä jokin raja-arvo, kun jakaa N:llä. Pitäisikin myös keksiä merkintä tuolle odotusarvolle, merkitään sitä siis nyt vain E(N, r).
N = 1000, E(N,r) = 611.223000, E(N,r)/N = 0.611223
N = 1100, E(N,r) = 663.302000, E(N,r)/N = 0.603002
N = 1200, E(N,r) = 737.113000, E(N,r)/N = 0.614261
N = 1300, E(N,r) = 802.891000, E(N,r)/N = 0.617608
N = 1400, E(N,r) = 861.760000, E(N,r)/N = 0.615543
N = 1500, E(N,r) = 916.566000, E(N,r)/N = 0.611044
N = 1600, E(N,r) = 984.862000, E(N,r)/N = 0.615539
N = 1700, E(N,r) = 1034.190000, E(N,r)/N = 0.608347
N = 1800, E(N,r) = 1096.621000, E(N,r)/N = 0.609234
N = 1900, E(N,r) = 1153.775000, E(N,r)/N = 0.607250
N = 2000, E(N,r) = 1214.472000, E(N,r)/N = 0.607236
N = 2100, E(N,r) = 1276.475000, E(N,r)/N = 0.607845
N = 2200, E(N,r) = 1364.307000, E(N,r)/N = 0.620140
N = 2300, E(N,r) = 1407.446000, E(N,r)/N = 0.611933
N = 2400, E(N,r) = 1457.775000, E(N,r)/N = 0.607406
N = 2500, E(N,r) = 1513.825000, E(N,r)/N = 0.605530
N = 2600, E(N,r) = 1577.757000, E(N,r)/N = 0.606830
N = 2700, E(N,r) = 1629.256000, E(N,r)/N = 0.603428
N = 2800, E(N,r) = 1711.332000, E(N,r)/N = 0.611190
N = 2900, E(N,r) = 1764.590000, E(N,r)/N = 0.608479
N = 3000, E(N,r) = 1812.446000, E(N,r)/N = 0.604149
N = 3100, E(N,r) = 1903.929000, E(N,r)/N = 0.614171
N = 3200, E(N,r) = 1948.071000, E(N,r)/N = 0.608772
Joo, kyllä se raja-arvo jotain 0.6 nolla yksi tai kaksi on, 0.61 veikkaisin.
Jännä olisi tietää nuo raja-arvot N-m kaikilla m.
Sehän alkaa 0.75, 0.61, ....
Mites jos siitä puolesta välistä koitetaan arvioida tuota odotusarvoa eli r=N/2 (kok. luku). Nämä on nyt simuloitu (näin suurille ihan turha yrittää tarkkaan laskea tarkkaa arvoa, jos ei sitten keksi kaavaa!), tässä on siis N/2: (odotusarvo)
500: 9.280000
550: 9.451000
600: 9.531000
650: 9.547000
700: 9.788000
750: 9.815000
800: 9.871000
850: 10.039000
900: 10.248000
950: 10.153000
1000: 10.275000
1050: 10.319000
1100: 10.358000
1150: 10.461000
1200: 10.565000
1250: 10.567000
1300: 10.656000
1350: 10.685000
1400: 10.832000
1450: 10.853000
1500: 10.947000
1550: 10.776000
1600: 10.984000
1650: 11.018000
1700: 11.125000
1750: 11.145000
1800: 11.269000
1850: 11.095000
1900: 11.214000
1950: 11.317000
2000: 11.394000
2050: 11.362000
2100: 11.350000
2150: 11.305000
2200: 11.439000
2250: 11.338000
2300: 11.541000
2350: 11.600000
2400: 11.486000
2450: 11.667000
Kyllä se pikkuhiljaa kasvaa ja kasvaa, mutta näyttäisi, että ei se ole mikään positiivinen prosenttiosuus N:stä ole. Pitäisipäkin kokeilla esim. r=N-2 tulisiko tällä jokin raja-arvo, kun jakaa N:llä. Pitäisikin myös keksiä merkintä tuolle odotusarvolle, merkitään sitä siis nyt vain E(N, r).
N = 1000, E(N,r) = 611.223000, E(N,r)/N = 0.611223
N = 1100, E(N,r) = 663.302000, E(N,r)/N = 0.603002
N = 1200, E(N,r) = 737.113000, E(N,r)/N = 0.614261
N = 1300, E(N,r) = 802.891000, E(N,r)/N = 0.617608
N = 1400, E(N,r) = 861.760000, E(N,r)/N = 0.615543
N = 1500, E(N,r) = 916.566000, E(N,r)/N = 0.611044
N = 1600, E(N,r) = 984.862000, E(N,r)/N = 0.615539
N = 1700, E(N,r) = 1034.190000, E(N,r)/N = 0.608347
N = 1800, E(N,r) = 1096.621000, E(N,r)/N = 0.609234
N = 1900, E(N,r) = 1153.775000, E(N,r)/N = 0.607250
N = 2000, E(N,r) = 1214.472000, E(N,r)/N = 0.607236
N = 2100, E(N,r) = 1276.475000, E(N,r)/N = 0.607845
N = 2200, E(N,r) = 1364.307000, E(N,r)/N = 0.620140
N = 2300, E(N,r) = 1407.446000, E(N,r)/N = 0.611933
N = 2400, E(N,r) = 1457.775000, E(N,r)/N = 0.607406
N = 2500, E(N,r) = 1513.825000, E(N,r)/N = 0.605530
N = 2600, E(N,r) = 1577.757000, E(N,r)/N = 0.606830
N = 2700, E(N,r) = 1629.256000, E(N,r)/N = 0.603428
N = 2800, E(N,r) = 1711.332000, E(N,r)/N = 0.611190
N = 2900, E(N,r) = 1764.590000, E(N,r)/N = 0.608479
N = 3000, E(N,r) = 1812.446000, E(N,r)/N = 0.604149
N = 3100, E(N,r) = 1903.929000, E(N,r)/N = 0.614171
N = 3200, E(N,r) = 1948.071000, E(N,r)/N = 0.608772
N = 3300, E(N,r) = 2020.149000, E(N,r)/N = 0.612166
N = 3400, E(N,r) = 2073.877000, E(N,r)/N = 0.609964
N = 3500, E(N,r) = 2136.031000, E(N,r)/N = 0.610295
N = 3600, E(N,r) = 2178.470000, E(N,r)/N = 0.605131
N = 3700, E(N,r) = 2274.072000, E(N,r)/N = 0.614614
N = 3800, E(N,r) = 2325.082000, E(N,r)/N = 0.611864
N = 3900, E(N,r) = 2408.724000, E(N,r)/N = 0.617622
N = 4000, E(N,r) = 2449.636000, E(N,r)/N = 0.612409
N = 4100, E(N,r) = 2502.997000, E(N,r)/N = 0.610487
N = 4200, E(N,r) = 2600.970000, E(N,r)/N = 0.619279
N = 4300, E(N,r) = 2641.723000, E(N,r)/N = 0.614354
N = 4400, E(N,r) = 2703.666000, E(N,r)/N = 0.614470
N = 4500, E(N,r) = 2784.844000, E(N,r)/N = 0.618854
N = 4600, E(N,r) = 2815.597000, E(N,r)/N = 0.612086
N = 4700, E(N,r) = 2843.240000, E(N,r)/N = 0.604945
N = 4800, E(N,r) = 2928.448000, E(N,r)/N = 0.610093
N = 4900, E(N,r) = 2992.075000, E(N,r)/N = 0.610628
Joo, kyllä se raja-arvo jotain 0.6 nolla yksi tai kaksi on, 0.61 veikkaisin.
Jännä olisi tietää nuo raja-arvot N-m kaikilla m.
Sehän alkaa 0.75, 0.61, ....
Oho, mites se noin monta kertaa tuli? Kun tässä oli joku palvelinvirhe, niin luulin, ettei se mennyt.