A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Megoldás. A játéknak vizsgáljuk azt az általánosabb változatát, amelyben akárhány kupac, és mindegyik kupacban tetszőleges számú kavics lehet. A kavicsok számát jelölje , a kupacok számát . Ha egy kupacban csak egyetlen kavics van, azt nevezzük ,,kis'' kupacnak, a többit pedig ,,nagy'' kupacnak, utóbbiak számát jelölje . Először azt mutatjuk meg, hogy a játék biztosan véget ér, bárhogyan is játszik Anna és Balázs. Mivel , azért nemnegatív egész szám. Belátjuk, hogy értéke minden lépés során csökken. Ha a soron következő játékos egy kupacot két kisebb kupacra oszt, akkor nem változik, pedig -gyel nő, így értéke valóban csökken. Ha pedig egy kupacból elvesz egyetlen kavicsot, akkor -gyel csökken, pedig vagy nem változik, vagy -gyel csökken, de értéke mindkét esetben csökken. Mivel értéke minden lépésben legalább -gyel csökken, de végig nemnegatív, a játék véges sok lépésben véget ér. Azt fogjuk szerinti teljes indukcióval bizonyítani, hogy pontosan akkor van Balázsnak, vagyis a második játékosnak nyerő stratégiája, ha az , , számok közül vagy mindegyik páros, vagy mindegyik páratlan; egyébként Annának, vagyis az első játékosnak van nyerő stratégiája. Ha , akkor , vagyis az első játékos nem tud lépni, és így valóban a második játékosnak van nyerő stratégiája. Tegyük fel, hogy , és az állítást már minden olyan játékra igazoltuk, ahol . Vizsgáljuk először azt az esetet, amikor , és paritása megegyezik. Könnyen meggondolható, hogy bármit is lép az első játékos, a három mennyiség között lesz olyan, amelyik változatlan marad, és lesz olyan is, amelynek értéke pontosan -gyel változik, így megváltozik a paritása. Az így keletkező új játékban az indukciós feltevés szerint az első játékosnak van nyerő stratégiája, vagyis az eredeti játékban a másodiknak, ahogyan azt állítottuk. Tegyük fel végül, hogy , és nem azonos paritásúak. Elegendő azt megmutatni, hogy az első játékos tud úgy lépni, hogy ezután , , paritása megegyező legyen, hiszen ezután alkalmazhatja a folytatásban az új játék második játékosának nyerő stratégiáját. Ha és paritása megegyezik (de paritásával ellentétes), akkor , tehát van legalább egy kis kupac is. Az első játékos egy kis kupacból elvesz egy kavicsot, így és értéke -gyel csökken, pedig nem változik, ezután a három mennyiség paritása megegyezik. Ha és paritása egyezik meg, akkor , tehát van legalább egy nagy kupac. Ha van olyan nagy kupac is, amelyben legalább kavics van, akkor az első játékos kettéválasztja egy kis és egy nagy kupacra, ekkor értéke -gyel nő, miközben és értéke változatlan marad. Ha ilyen nincs, akkor mindegyik nagy kupacban pontosan kavics van. Az első játékos egy nagy ‐ tehát pontosan két kavicsot tartalmazó ‐ kupacból elvesz egy kavicsot, így és értéke -gyel csökken, miközben értéke nem változik. Az első játékos mindkét esetben el tudta érni, hogy lépése után a három mennyiség paritása egyezzen meg. Végül, ha és paritása azonos, akkor megint csak van legalább egy nagy kupac. Ha van legalább kavicsot tartalmazó nagy kupac is, akkor az első játékos egy ilyen kupacból elvesz egy kavicsot, így a lépés során és nem változik, míg -gyel csökken. Ha viszont minden egyes nagy kupacban pontosan kavics van, akkor az első játékos egy ilyen kupacot két kis kupacra oszt. Így értéke nem változik, értéke -gyel nő, értéke pedig -gyel csökken. Az első játékos ismét mindkét esetben el tudta érni, hogy lépése után a három mennyiség paritása azonos legyen. Ezzel befejeztük az indukciós lépés igazolását. Teljes indukcióval beláttuk, hogy ha , , azonos paritásúak, akkor a második játékosnak van nyerő stratégiája, különben pedig az elsőnek. A feladatban szereplő játék esetén , , így az első játékosnak, vagyis Annának van nyerő stratégiája. |