Egyik este a kocsmában Beliánék a következő játékot játszották. Belián elővett egy doboz gyufát, majd három kupacba rendezte a szálakat úgy, hogy az egyikbe 3, a másikba 4 a harmadikba pedig 5 szál jutott.
A játékot két személy játssza, és felváltva választanak egy kupacot, majd abból tetszés szerint néhány szál gyufát elvesznek maguknak. Ezután a másik játékos jön, ő is választ, és elvesz annyit, amennyit akar. A lényeg, hogy egyszerre csak az egyik kupacból vehet el gyufát, és mindenképp legalább egyet el kell vennie.
A játékot az nyeri, aki az utolsó szál gyufát elveszi.
Beliánt néhány kör után ki kellett zárni, mert mindig ő nyert, így Arszlán és Cipórián közt folyt a verseny napkeltéig.
Kérdésünk az, hogy milyen trükköt ismerhetett Belián. Adjunk nyerő stratégiát a kezdő játékos számára. Mi a helyzet abban az esetben, ha az veszít, akinek az utolsó gyufát el kell vennie?
A kezdő játékosnak van nyerő stratégiája. Nincs más dolga, csak, hogy összexorolja a kupacban levő gyufák számát, és úgy vegyen el a kupacból, hogy lépései után a xor értéke mindig nulla legyen.
⊕-szal jelölve a xor műveletet, kezdetben 3 ⊕ 4 ⊕ 5 = 2. Így az első lépésnek választhatjuk az első kupacból két gyufa elvételét, hiszen így 1 ⊕ 4 ⊕ 5 = 0 marad.
Ha nulla a xor értéke, akkor a rákövetkező játékos ezt mindenképp elrontja, és fordítva: ha nem nulla az érték, akkor van olyan lépés, amivel nullára állítható.
A győztes lépés előtt már csak egy kupac van, és úgy állítjuk a (most már egytagú) xort nullára, hogy minden gyufát elveszünk az asztalról.
A módszer működik több kupac esetén is, és akárhogy megválaszthatjuk a kezdetben a kupacokban levő gyufák számát. Ha a kezdeti xor értéke nem nulla, akkor az első, egyébként a második játékosnak lesz nyerő stratégiája.
A fordított játékszabályok esetén pontosan ez a stratégia játszható egészen addig, amíg csak 1 olyan kupac nem marad, amiben legalább két gyufa van. Ekkor ebből a kupacból kell annyit elvenni, hogy az asztalon páratlan számú kupac maradjon, utána felváltva vesznek el a játékosok egy-egy gyufát, az utolsó az ellenfélnek marad, így ő veszít.
A részleteket a wikipedián olvashatjátok, de egyedül sem nehéz belátni, hogy a módszer miért működik, ez egy jó gondolkodtató feladat lehet.
Comments are closed.
ha előttem egy kupac gyufa marad összesen, akkor nyertem.
természetesen ez csak akkor alakulhat ki, ha előtte még két kupac gyufa volt az asztalon – hiszen egyébként a másik vette volna el mindet -, valamint pontosan ilyen okok miatt biztos, hogy mindkét kupacban 1-1 gyufa volt összesen, hiszen egyébként a másik nem vette volna el az egyik kupac összes gyufáját. magyarán, aki 1/1/0 állásnál lépni következik, az bukott.
pont emiatt bukott az, aki x/x/0-s állásnál kénytelen lépni (tehát, hogy összesen két kupac van az asztalon ugyanannyi gyufával), hiszen ilyenkor a másiknak nem kell mást tennie, csak “tükrözni” a lépést, azaz annyi gyufát elvenni a másik kupacból, hogy ismét egyenlő számú gyufa legyen.
így nyerő pozíció az x/x/y állás (a lépni következő játékos részére: a harmadik kupac elvételével x/x/0-ás, vesztett helyzetbe hozhatja ellenfelét; ugyanígy természetesen nyerő az x/y/0 pozíció (itt egyenlő kupacméretet kell ismét kialakítani).
ezek alapján vesztes az 1/2/3 felállás (vagy teljesen eltakarít egy kupacot -> x/y/0 nyertem, vagy lesz két egyforma kupac -> x/x/y, nyertem).
a nyerő stratégia: a kezdő játékos a 3 gyufás kupacból elvesz 2-t, marad 1/4/5.
a lehetséges következő állások
0/4/5, 0/1/4, 0/1/5 nyerő állás a soron következő játékosnak (0/x/y)
1/4/4, 1/1/4, 1/1/5 szintén (x/x/y)
1/2/4, 1/2/5, 1/3/4, 1/3/5 esetén a soron következő játékos 1/2/3-at alakít ki és nyer.
a fordítottra stratégiát meg az általánosítást egyelőre meghagyom másnak 🙂
Van az itt ismertetettnek egy sokkal egyszerűbb megfogalmazása is, ami aztán általánosítható nagyobb/több kupacra.
Milyen invariánsra figyeljen a kezdő játékos?
1. Levesz egy kupacot.
2. A játékos társ nem fog teljes kupacot elvenni, mert akkor egyből nyernék.
3. A két meglévő kupacból, a nagyobb számosságúból elveszem a lehető legtöbbet, úgy, hogy a megmaradó gyufák összes száma páros legyen.
4. 2.-t és 3.-at iteráljuk.
A végén 1-1-es állásnál az ellenfélnek kell választania => nyertünk.
@rusty:
Ha az veszít akinek az utolsót kell levennie a 3. lépésben páratlan számú gyufát hagyunk az asztalon.
@rusty: a példában ha a kezdő játékos elvesz egy kupacot, akármelyiket, akkor a másik játékos fog nyerni, egyszerűen úgy, hogy egyenlővé teszi és úgy tartja a meglevő két kupacban levő gyufák számát, ez tehát nem nyerő stratégia a kezdőnek. ez egyben általános nyerő stratégia abban az esetben, ha már csak két kupac maradt. három kupacon még gondolkodok 🙂