Nim játék

Az algoritmizálás és programozás tanításához alkalmaztuk a nim játékot, mint egyszerû logikai játékot.

Az alapváltozat mellett számos módosított játék is lehet, amellyel a megértés ellenõrzését, a számonkérést tudjuk megoldani.

Egykupacos nim

Nézzük elsõként a szabályt!

Két játékos játszik. Felváltva vesznek el egy kupac kavicsból, legalább 1 de legfeljebb 5 kavicsot. Az nyer, aki az utolsó kavicsot elveszi.

Kérdezzük meg elsõként, hogy van-e, aki ismeri a játékot, tudja a nyerõ stratégiát. Ha van jelentkezõ, akkor 18 darab kavicsot tegyünk, ki, ezt ne ott számoljuk ki, hanem legyen elõkészítve és kezdjen õ. Ha nincs ilyen, akkor 17 vagy 16 kaviccsal játsszunk, és ajánljuk fel a kezdés lehetõségét. A diákok közül kérjünk önként jelentkezõt, aki játszik velünk. A játék menetét le is jegyezhetjük, a táblára rajzoljunk fel 18 kört, majd az egyes játékosok lépését jelöljük be.

a) Ha egy diák ismeri a nyerõ stratégiát – állítása szerint –, akkor kezdjen õ a 18 kavicsnál, ugyanis most a második nyerhet.

A zöld vonal a diák, a kék a tanár lépéseit jelzi. Célszerû felhívni a figyelmet arra majd késõbb, hogy az utolsó diáklépésnél már mindenféleképpen nyerni fogunk.

b) Ha egy diák sem ismeri a játékot, vagy más is akar próbálkozni, akkor kezdjünk mi, elõtte változtassuk meg a kavicsok számát, például 17-re. Az elsõ lépésben most 5 kavicsot vegyünk el, és mondjuk azt, hogy minél gyorsabban legyen vége, azért :-).

E két játék után már biztos lesz olyan, aki sejti a nyerõ módszert, legalábbis hat kavicsra. Ezután tisztázhatjuk is, a nyerési stratégiát, lépésrõl lépésre, nagyjából a következõ sorrendben, hogy tulajdonképpen:

A módszer megértését ellenõrizhetjük is.

1. Hány kavicsot kell elvennie a kezdõnek, hogy nyerjen, ha 14 darab van? 2-t.

2. Hány kavicsot kell elvennie a kezdõnek, ha 24 darab kavics van, hogy nyerjen? Nem nyerhet, ha a második is ismeri a stratégiát.

3. Legkevesebb hány lépésben lehet nyernie a kezdõnek, ha 31 vagy 32 kavics van? 32 és a 6 hányadosa + 1 lépésben.

A megértés második lépése, hogy az 1 és 5 számok helyett más szerepel. Nyilván a 6 a minimális és maximális lépés összege.

4. Mikor kell kezdeni, hogy nyerjünk, ha a szabály úgy módosul, 1 a legkevesebb és 3 a legtöbb kõ, amit elvehetünk? Ha a kavicsok száma 4-gyel osztható, akkor ne, ha nem osztható, akkor mi kezdjünk.

5. Ki nyer, ha DB kavics van és MIN a legkevesebb, MAX a legtöbb elvehetõ kavicsszám? Ha DB osztható MIN+MAX-szal, akkor a kezdõ veszít, különben nyer. Ez a válasz viszont nem igaz, ehhez a MAX-nál nagyobbnak kell lennie a DB-nek!

6. Legkevesebb hány lépésben lehet nyerni, ha MIN és MAX értékek vannak és DB kavics? DB div (MIN+MAX)+1, ahol div a hányadosképzést jelenti.

Változatok

a) Ki veszít?

Módosítsuk a játék szabályát úgy, hogy az veszít, aki az utolsó kavicsot elveszi. 18 kavics esetén most a kezdõ nyer, ha így lép:

A diákok hamar rájönnek, hogy az nyer, aki elsõként el tudja érni, hogy a kavicsok száma 6k+1 alakú legyen, vagy általánosan (MIN+MAX)*k+1 alakú, feltéve hogy DB nagyobb, mint MIN+MAX.

Ez a módosítás feladható házinak is.

b) Fibonacci-nim

Lényegesen nehezebb a játék, ha megtehetõ lépések száma nem egy Fibonacci sorozat elemei lehetnek maximum. Nézzük a pontos szabályt!

Van egy kupac kavics, a két játékos felváltva vehet el valahány kavicsot. Az kezdõ játékos tetszõleges számú kavicsot elvehet, de az összeset nem. Legalább 1 kavicsot minden lépésben el kell venni. Minden további lépésben maximum az elõzõ lépésben elvett kavicsok számának a kétszeresét lehet elvenni. A játékot az nyeri, aki az utolsó kavicsot elveszi.

A módosított játék neve azért Fibonacci nim, mert az nyerhet, aki elsõként el tudja érni, hogy Fibonacci szám mennyiségû kavics maradjon a lépése után. Azaz ha a kavicsok száma eleve Fibonacci szám, akkor a második játékos nyerhet, ha nem, akkor az elsõ játékosnak van nyerõ stratégiája.

A Fibonacci számok emlékeztetõül: 1 1 2 3 5 8 13 21 34 55 87 ...

A nyerõ stratégia kicsit bonyolultabb. Minden természetes szám felbontható nem szomszédos Fibonacci számok összegére. Pl.: 27=21+5+1, vagy 49=34+13+2. A felbontást úgy kell elvégezni, hogy az adott számnál nem nagyobb Fibonacci számok közül mindig a lehetõ legnagyobbat kell választani elõször, majd a maradék esetén újfent megkeresni a legnagyobb Fibonacci számot. A maradékra hasonlóan. Ha megvan a felbontás, akkor az abban szereplõ legkisebb tagot kell kivonni elsõként, azaz ennyi kavicsot kell elvenni. Az ellenfél lépése után a kapott új szám esetén szintén ezt a stratégiát kell követni.

Nézzünk egy példát, legyen 19 kavicsunk! Ennek a felbontása 13+5+1

A kezdõ 1 kavicsot vett el.

A második játékos 1 vagy 2 kavicsot vehet el. Vegyen el 2-t!

Most maradt 16 kavics, azaz 13+3, ami azt jelenti, hogy 3-at kell elvenni. Vegyük észre, hogy ha 1-et vett volna el, akkor 17 kavics maradt volna, ami 13+3+1 felbontású, tehát 1-et kellett volna elvenni.

Most 1 és 6 között vehet el a második játékos, de ha meg akarja akadályozni a nyerést, akkor 4-nél többet nem vehet el. Tegyük fel, hogy 4-et vesz el!

A maradék 9, tehát 8+1, most 1 kavicsot kell elvenni, és így tovább.

Legyen 2 elvétele

Ismét 1-et kell elvenni, mert 5+1 a felbontás

Most csak 1 kavicsot szabad elvenni, mert egyébként a kezdõ nyer.

Megint 1 kavicsot kell, majd 1 és 2 kavics elvételével a kezdõ nyer.

A játék számítógépes megvalósításával játszva is gyakorolhatjuk vagy éppen megértethetjük a nyerõ stratégiákat.

Következõ számunkban a többkupacos nimrõl írunk.

Rozgonyi-Borus Ferenc