KöMaL - Középiskolai Matematikai és Fizikai Lapok
English Információ A lap Pontverseny Cikkekről Hírek Fórum
Versenykiírás
Tudnivalók
Nevezési lap
Feladatok
A verseny állása
Korábbi évek
Arcképcsarnok
Munkafüzet

 

Rendelje meg a KöMaL-t!

Reklám:

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 2x\gex\gey, é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=n\ge1, é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 y\nez, 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 x\ney, 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.


A B. 3926. feladat statisztikája
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

  • Támogatóink:   Ericsson   Google   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma  
    Oktatáskutató és Fejlesztő Intézet   Nemzeti Tehetség Program     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley