Három ember és egy gyanús érme
293. feladvány: Sorsolás torzított érmével
Hárman szeretnének igazságosan kisorsolni valamit egymás között. Van náluk egy érme, de nem bíznak abban, hogy az érme pontosan 1/2 valószínűséggel esik fejre és 1/2 valószínűséggel írásra.
Felmerül az ötlet, hogy mindhárman választanak maguknak egy-egy előre rögzített fej-írás sorozatot, azaz lényegében egy-egy szót az F és I betűkből, és ezután addig dobálják az érmét, amíg a dobássorozatban valamelyikük szava meg nem jelenik. Akié elsőként jelenik meg, az nyeri a sorsolást. Vajon lehet ilyen szavakat választani?
Sokakban felmerülhet az a kézenfekvő ötlet, hogy az IFF, FIF és FFI sorozatok választása megfelelő lehet, mert ezek külön-külön ugyanakkora valószínűségűek, hiszen mindegyik pontosan egy fejből és két írásból áll. Mégsem adnak igazságos sorsolást. A gond az, hogy a felvázolt sorsolási metódusban nem az számít, hogy egy adott minta mekkora valószínűséggel fordul elő valahol, hanem az, hogy melyik jelenik meg először.
Ha például a sorozat vége IF, akkor az IFF már közel van a győzelemhez, de egy következő I ezt az előnyt megtöri. Hasonló a helyzet a FIF mintával is. Az FFI viszont különleges: ha a sorozat vége FF, akkor már csak egy I kell a győzelemhez, és ha közben újabb F érkezik, az előny továbbra is megmarad, mert a sorozat vége még mindig FF lesz. Ezért az azonos összetételű minták az első előfordulásért folyó versenyben nem feltétlenül egyenrangúak. Ez még akkor sincs így, ha az érme teljesen szabályos lenne, lásd a híres Penney's Game problémát.
Ha viszont az érme nem szabályos, akkor még jobban kidomborodik, hogy a szimmetrikusnak tűnő minták között is aszimmetria van az időbeliség miatt. Az IFF és az FFI sorozatok például hasonlónak tűnnek, de ha a fejnek sokkal nagyobb a valószínűsége, akkor jól látható, hogy az IFF-nek nagyon nagy hátránya van az FFI-hez képest, hiszen folyamatosan dobáljuk a fejeket és csak nagy ritkán egy írást, tehát az FFI elkezdése sokkal valószínűbb. Ha már volt két fej egymás után, akkor már biztosan nyer az FFI, mert újabb fej esetén is csak az ő marad esélyes.
Szóval, mindezek után, vajon lehet megfelelő szavakat választani, vagy sem?
Tipp
Keressünk három olyan írás-fej sorozatot, amik azonos hosszúak, azonos arányban van bennük az írás és a fej, és egyik sorozatnak sincs az elején (bal végén, azaz időben hátrébb) olyan rész, ami megegyezne bármelyik sorozat (jobb) végével, beleértve önmagát is!
Megoldás
Ha olyan sorozatokat keresünk, amik azonos hosszúak, azonos arányban van bennük az írás és a fej, és egyik sorozatnak sincs az elején olyan rész, ami megegyezne bármelyik sorozat végével, beleértve önmagát is, akkor ki tudjuk küszöbölni azt, amiről a bevezetőben beszéltünk. Vagyis ha találunk ilyen sorozatokat, akkor el tudjuk érni azt, hogy egyik sorozat se legyen kitüntetett a többihez képest abból a szempontból, hogy az előfordulása megnövelhetné a valószínűségét annak, hogy valamelyik sorozat már korábban előfordult.
Ilyen sorozatokra példa lehet az alábbi hármas: FFFIII, FFIFII, FIFFII. Látható, hogy mindegyik eleje F, és a végük I, ami nem egyezik. De ha kettő hosszú részsorozatot nézünk, akkor sincs egyezés, mert mindegyik elején FF vagy FI szerepel, a végükön pedig II. És ugyanígy, könnyen elelnőrizhető, hogy az ennél hosszabb részsorozatok esetében sem fogunk egyezést találni. Miért jó ez? Nézzük a pontos bizonyítást.
Tegyük fel, hogy Anna, Béla és Csaba játszik, közöttük osztottuk ki a fenti három hat hosszú sorozatot. A játékban addig dobálunk, amíg valaki nem nyer. Tegyük fel, hogy Anna nyer a 100. dobásnál. Hogy néz ki ez a győztes sorozat papírra leírva? Két részre oszthatjuk: van az első 94 dobás (törzs), ami után következik Anna hat hosszú sorozata (farok). Mármost az első 94 dobásban, azaz a sorozat törzsében még senki nem nyert, az tehát egy olyan sorozat, ami nem tartalmazhatja részsorozatként senkinek a hat hosszú sorozatát.
Most tegyük fel a kérdést: mi történik, ha fogjuk a fenti nyertes sorozatot, levágjuk Anna farkát és lecseréljük Béla farkára? Vajon ez az új sorozat garantáltan Béla győzelmét jelenti a 100. dobásnál? Könnyen belátható, hogy két dolog ronthatná el Béla győzelmét, Az egyik, ha valaki már nyert volna korábban, az első 94 dobás alatt, de ezt már Anna esetében is kizártuk. A másik, ami elronthatná Béla győzelmét, ha a ragasztásnál jön létre valaki másnak a szava, például a törzs utolsó pár betűje és Béla farkának első pár betűje véletlenül kiadja Csaba szavát a 98. dobásnál. No de itt nyer értelmet az, ahogyan konstruáltuk a szavakat, tehát ez sem lehetséges, sőt még az sem, hogy Béla korában nyer!
Mindezek alapján azt kapjuk, hogy minden egyes létező forgatókönyvhöz (legyen az 6, 100, 1000 vagy akármilyen hosszú dobássorozat), amiben Anna nyer, létezik egy hajszálpontosan párhuzamos forgatókönyv, amiben Béla nyer, és persze egy olyan is, amiben Csaba, és ezek valószínűségei megegyeznek, mert a farkak valószínűségei önmagukban azonosak. És mindez nemcsa Anna nyerő sorozataira igaz, hanem bárkiére, tehát a valószínűségek konkrét kiszámolása nélkül beláttuk, hogy a lehetséges kimenetelek azonos valószínűségű hármas csoportokba oszthatók, így igazságos lesz a sorsolás ezekkel a fenti hat hosszú sorozatokkal.
Ha szereted a fejtörőket, tekintsd meg korábbi feladványainkat is! Ha megjegyzésed lenne, vagy feladványt javasolnál, írj az eszventura@qubit.hu e-mail címre! Ha pedig tetszik a rovat, ezt a Vendégkönyvben kifejezésre juttathatod.
