Fórum: Érdekes matekfeladatok

Nem jött megoldás, így lelövöm. Kezdetben n szín van, a játék véget ér, ha egy szín marad. Tetszőleges n² egymásutáni fordulóban (1 forduló amikor 2 golyót a játékvezetőnek adunk és 2-t visszakapunk) van olyan szín ami legalább n-szer szerepel az odaadott golyószínek között (skatulyaelv, sőt van ami legalább 2n-szer), és legfeljebb persze n²-szer (mindez stratégiától függetlenül igaz). Ha ezen fordulók mindegyikében pont a másik színből adott vissza a játékvezető, akkor ebből a színből több nem marad (és később sem jöhet "vissza" a szabályok miatt). Ennek valószínűsége legalább . Nézzünk n-1 egymásutáni blokkot, azaz n² hosszú fordulót, ha minden blokkban vesztünk egy színt, akkor a játék természetesen véget ér, ennek a valószínűsége legalább q=r^n-1. Azaz annak a valószínűsége, hogy n²(n-1) fordulóban befejeződik a játék legalább q, így annak a valószínűsége, hogy nem fejeződik be a játék legfeljebb s=1-q<1.

Ebből már készen vagyunk, mert ekkor Pr2(m)=Pr(játék m lépésben nem fejeződik be)<c*p^m, ahol c>0,p<1 (Miért is? Bontsuk fel az m fordulót n²(n-1) hosszú fordulókra, bármelyiket is választjuk legfeljebb s<1 valószínűséggel nem ér benne véget a játék, így m forduló után is játszunk legfeljebb valószínűséggel .)

Legyen Pr1(m)=Pr(játék pontosan m lépésben ér véget), ekkor , azaz véges a várható érték, stratégiától függetlenül.

Sőt itt valamivel többet is beláttam, hiszen c,p csak n-től függött (de a stratégiától nem), azaz létezik v(n) véges szám, hogy a várható érték kisebb, mint v(n). Itt v(n) egyébként ki is számolható.

Hadd szedjem külön a feladat első részét.

(c) Lássuk be, hogy bármilyen stratégiával játszol is, a lépések számának várható értéke véges.

Ezt a feladatot nem volt jó ötlet ezen a fórumon feladnom, mert a megoldásához túl sok előismeret kell. A középiskolás fórumozóktól ezért elnézést kérek.

Aha, értem! Bocsánat, hogy nem fogalmaztam egyértelműen. Valóban, a játékvezető nem adja vissza a két golyót, amit odaadtál neki, így minden lépés után pontosan n golyó lesz nálad.

Jó a megoldásom, csak egy másik feladatra. Az persze számomra nem volt világos, hogy a játékvezető a két golyót lenyúlja amit odaadsz neki, így persze nálad mindig n golyó lesz, az én feladatomban pedig minden lépés után 2-vel több.

A számok, amiket megadtál, szerintem nem stimmelnek. n=3 esetén az első lépés után három golyóból két egyforma színű, és egy különböző lesz. Ez után minden további lépés után 1/2 valószínűséggel nyertél, 1/2 valószínűséggel visszajutsz egy hasonló állapothoz, csak most a másik színből van két golyód, mint az előbb. Így aztán biztosan legalább 2 lépés kell a nyerésig, nem 1, mint a táblázatban mutatod. Nem nehéz belátni, hogy a lépések várható száma pontosan 3.

Látható, hogy n=3 esetén még lényegében nincs választásod a játék során. A következő, n=4 esetben már van választásod. Például ha az első lépés után két fehér, egy sárga, és egy piros golyód van, akkor kétféleképpen dönthetsz. Odaadhatod a játékvezetőnek a sárga és a piros golyót, ez a kevésbé kockázatos stratégia, mert ekkor legközelebb biztosan két fehér és két másik azonos színű golyód van. Vagy kockáztathatsz, odaadva a játékvezetőnek egy fehér és egy sárga golyót, ekkor 1/2 valószínűséggel már három fehér golyód lesz, amivel közelebb jutottál a nyeréshez; de 1/2 valószínűséggel két sárga, egy fehér és egy piros golyód lesz, amivel helyben maradtál.

Te választod meg a stratégiát, de a feladat kitűzésében azt állítottam, hogy a lépések számának várható értéke bármely stratégia esetén ugyanannyi.

Nagyobb n-ekre megnézve látszik, hogy tart 1-hez, ami nagyon igaznak tűnik. Például a(1000) kb. 974.7749818216391980931583112 .

Optimális stratégiával a sorozat első 20 tagja (Neil adatbázisában nincs benne a számlálók sorozata, a nevezők 2 hatványok)

1 0

2 1

3 1

4 5/2

5 5/2

6 33/8

7 33/8

8 93/16

9 93/16

10 965/128

11 965/128

12 2379/256

13 2379/256

14 11333/1024

15 11333/1024

16 26333/2048

17 26333/2048

18 480429/32768

19 480429/32768

20 1079775/65536

"Minden lépésben megnézed a golyókat"

"A várható érték miért ugyanannyi függetlenül attól, hogy melyik golyókat választod?"

Játszhatok egy stratégia szerint, vagy véletlenül kell a golyókat kiválasztanom? Optimális stratégiával O(n) lesz a válasz: mindig a két eddig legtöbbet kihúzott színt választom (ha több lehetőség van, akkor véletlenül döntök a leggyakoribbak közül), ez persze mese eddig, hogy miért is ez lenne az opt. Várható értéket sem mutatja, de sokkal könnyebben kiszámítható ezzel a várható érték.

Míg hülyén játszva O(n²). Teljesen véletlenül játszva is érdekes (lehet) a feladat.

Igen, veheted úgy, hogy a játékvezető csukott szemmel választ egyet. Én úgy képzelem, hogy egy golyót a játékvezető jobb kezébe adsz, egyet a bal kezébe. Ezután ha a játékvezető fejet dob, akkor két olyat ad vissza, amilyen a bal kezében van, ha írást, akkor két olyat, ami a job kezében van.