Feladat: B.3926 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Aczél Gergely ,  Bencs Ferenc ,  Berecz Dénes ,  Blázsik Zoltán ,  Éles András ,  Fonyó Dávid ,  Herber Máté ,  Honner Balázs ,  Keresztfalvi Tibor ,  Kiss Benedek ,  Kornis Kristóf ,  Korom-Vellás Judit ,  Kunos Ádám ,  Peregi Tamás ,  Sümegi Károly ,  Szûcs Gergely ,  Szalóki Dávid ,  Tossenberger Anna ,  Tóth László Márton ,  Varga László ,  Varga Vajk ,  Véges Márton ,  Virányi Lóránd 
Füzet: 2008/január, 25 - 26. oldal  PDF file
Témakör(ök): Teljes indukció módszere, Oszthatósági feladatok, Többszemélyes véges játékok, Feladat
Hivatkozás(ok):Feladatok: 2006/szeptember: B.3926

Anna és Balázs a következő játékot játsszák. Előttük van 10 kupac kavics, az elsőben 1, a másodikban 2, a harmadikban 3, és így tovább, a tizedikben 10 darab kavics. Felváltva lépnek és egy lépésben a soron következő játékos vagy egy kupacot két kisebb részre oszt, vagy pedig egy kupacból elvesz egyetlen kavicsot. A játékot Anna kezdi és az veszít, aki nem tud a szabályok szerint lépni. Kinek van nyerő stratégiája?

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 x, a kupacok számát y. 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 z. 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 2xxy, azért 2x-y nemnegatív egész szám. Belátjuk, hogy 2x-y é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 x nem változik, y pedig 1-gyel nő, így 2x-y értéke valóban csökken. Ha pedig egy kupacból elvesz egyetlen kavicsot, akkor x 1-gyel csökken, y pedig vagy nem változik, vagy 1-gyel csökken, de 2x-y értéke mindkét esetben csökken. Mivel 2x-y értéke minden lépésben legalább 1-gyel csökken, de végig nemnegatív, a játék véges sok lépésben véget ér.
Azt fogjuk 2x-y 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 x, y, z 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 2x-y=0, akkor x=y=z=0, 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 2x-y=n1, és az állítást már minden olyan játékra igazoltuk, ahol 2x-y<n. Vizsgáljuk először azt az esetet, amikor x, y és z 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 1-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 x, y és z nem azonos paritásúak. Elegendő azt megmutatni, hogy az első játékos tud úgy lépni, hogy ezután x, y, z 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 x és y paritása megegyezik (de z paritásával ellentétes), akkor yz, tehát van legalább egy kis kupac is. Az első játékos egy kis kupacból elvesz egy kavicsot, így x és y értéke 1-gyel csökken, z pedig nem változik, ezután a három mennyiség paritása megegyezik.
Ha x és z paritása egyezik meg, akkor xy, tehát van legalább egy nagy kupac. Ha van olyan nagy kupac is, amelyben legalább 3 kavics van, akkor az első játékos kettéválasztja egy kis és egy nagy kupacra, ekkor y értéke 1-gyel nő, miközben x és z értéke változatlan marad. Ha ilyen nincs, akkor mindegyik nagy kupacban pontosan 2 kavics van. Az első játékos egy nagy ‐ tehát pontosan két kavicsot tartalmazó ‐ kupacból elvesz egy kavicsot, így x és z értéke 1-gyel csökken, miközben y é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 y és z paritása azonos, akkor megint csak van legalább egy nagy kupac. Ha van legalább 3 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 y és z nem változik, míg x 1-gyel csökken. Ha viszont minden egyes nagy kupacban pontosan 2 kavics van, akkor az első játékos egy ilyen kupacot két kis kupacra oszt. Így x értéke nem változik, y értéke 1-gyel nő, z értéke pedig 1-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 x, y, z 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 y=10, z=9, így az első játékosnak, vagyis Annának van nyerő stratégiája.