A B. 3926. feladat (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?

(5 pont)

A beküldési határidő 2006. október 16-án LEJÁRT.

Megoldás: A játéknak vizsgáljuk azt az általánosabb változatát, amelyben akárhány kupac, és mindegyik kupacban bármennyi 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'', ezen utóbbiak számát jelölje z. Kell, hogy valamelyik játékosnak legyen nyerő stratégiája. Azt fogjuk bebizonyí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. Mivel a konkrét feladatban y=10 és z=9, abban az esetben Annának van nyerő stratégiája.

Nyilván 2xxy, és minden egyes lépés során a 2x-y nemnegatív egész szám értéke csökken, a játék tehát véges sok lépésen belül véget ér, mégpedig akkor, amikor a játékosok előtt már egyetlen kavics sincs. 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. Ahhoz, hogy az állításunkat 2x-y szerinti teljes indukcióval igazoljuk, tegyük fel, hogy 2x-y=n1, és az állítást már igazoltuk minden olyan játék esetén, amikor 2x-y<n. Az első játékos első lépése után egy ilyen játékkal állunk tehát szemben, ahol a két játékos szerepe felcserélődik.

Háromféle lépést különböztetünk meg. Az a) típusú lépésben az első játékos egy kupacot oszt két kisebb részre, ekkor x értéke nem változik, y értéke pedig 1-gyel nő. A b) típusú lépésben az első játékos egy kis kupacból vesz el egy kavicsot, ekkor x és y értéke egyaránt 1-gyel csökken, míg z értéke vátozatlan marad. A c) típusú lépében az első játékos egy nagy kupacból vesz el egy kavicsot, ekkor x értéke 1-gyel csökken, miközben y értéke változatlan marad.

Az indukciós lépés igazolására térve, tegyük fel először, hogy x,y,z paritása megegyezik. Bármit is lép az első játékos, a három mennyiség között lesz egy olyan, amelyik változatlan marad, és lesz egy olyan, amelyik 1-gyel változik, tehát a paritása ellenkezőjére változik. Az így keletkező új játékban az indukciós feltevés szerint az első játékosnak van nyerő stratégiája. Az eredeti játékban tehát a második játékosnak van nyerő stratégiája.

Tegyük fel végül, hogy x,y,z paritása nem egyezik meg. 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 kell legyen legalább egy kis kupac. Ekkor az első játékosnak módjában áll b) tí pusú lépéshez folyamodni, amellyel eléri célját.

Ha x és z paritása egyezik meg, akkor xy, tehát van legalább egy nagy kupac. Ha van egy nagy kupac, amelyben legalább 3 kavics van, akkor egy a) típusú lépéssel az kettéválasztható egy kis és egy nagy kupacra, melynek során y értéke eggyel nő, miközben x és z értéke változatlan marad. Ha ilyen nincs, akkor minden egyes nagy kupacban pontosan 2 kavics van. Ekkor az első játékos végrehajthat egy c) típusú lépést, melynek során mind x, mind z értéke 1-gyel csökken, miközben y értéke nem változik.

Ha pedig y és z paritása egyezik meg, akkor megintcsak van legalább egy nagy kupac. Ha van egy nagy kupac, amelyben legalább 3 kavics van, akkor egy c) típusú lépéssel elérhető, hogy y és z értéke ne vátozzon, de x értéke 1-gyel csökkenjen. Ha viszont minden egyes nagy kupacban pontosan 2 kavics van, akkor egy a) típusú lépés alkalmazható, melynek során x értéke nem vátozik, y értéke 1-gyel nő, z értéke pedig 1-gyel csökken, vagyis mindhárom mennyiség paritása ugyanolyan lesz.

Statisztika:

132 dolgozat érkezett.
5 pontot kapott:	Aczél Gergely, Bencs 111 Ferenc, Berecz Dénes, Blázsik Zoltán, Éles András, Fonyó Dávid, Herber Máté, Honner Balázs, Keresztfalvi Tibor, Kiss 002 Benedek, Kornis Kristóf, Korom-Vellás Judit, Kunos Ádám, Peregi Tamás, Sümegi Károly, Szalóki Dávid, Szűcs Gergely, Tossenberger Anna, Tóth 666 László Márton, Varga 171 László, Varga Vajk, Véges Márton, Virányi Lóránd.
4 pontot kapott:	Damásdi Gábor, Gévay Gábor, Gombor Tamás, Grosz Edward, Györgyi Péter, Szirmay-Kalos Barnabás, Szőke Nóra, Tallián György.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	95 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2006. szeptemberi matematika feladatai