Problem B. 3926. (September 2006)

B. 3926. Ann and Bob are playing the following game: There are 10 heaps of pebbles in front of them. The first heap contains 1 pebble, the second one contains 2, the third one contains 3, and so on, the tenth heap contains 10 pebbles. They take turns in carrying out one of the following two moves: they either divide a heap into two smaller ones or remove one pebble from one heap. A player who cannot do so any more will lose the game. Determine which player has a winning strategy, given that Ann starts the game.

(5 pont)

Deadline expired on October 16, 2006.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

132 students sent a solution.
5 points:	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 points:	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 points:	3 students.
2 points:	2 students.
0 point:	95 students.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, September 2006