Fibonacci Nim
Tarcsay Tamás
2007/09/18 13:01
1272 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
Több évvel ezelőtt, a Sulinet Oktatási Portál Matematika Rovatában közreadtunk egy flash animációt, amelynek segítségével két játékos egymás ellen játszhatta a címben szereplő nevet viselő játékot.

A játék szabályai a következők:

Adott egy kavics halom. amelyben ismert számú kavics van Két játékos felváltva vehet el valahány kavicsot. A kezdő játékos tetszőleges számú kavicsot elvehet, de az összest nem. Legalább1 kavicsot minden lépésben el kell venni. Minden további lépésben mindegyik játékos legfeljebb az előző lépésben elvett kavicsok számának a kétszeresét veheti el. A játékot az nyeri, aki az utolsó kavicsot veszi el. Az említett web oldal itt található.  Ha a számítógép ellen akarjuk játszani a játékot, akkor léphetünk erre az angol nyelvű oldalra, de e cikk végén további, a témával foglalkozó oldalakra hívjuk fel a figyelmet.

Ha sokat játsszuk a játékot, felmerülhetnek bennünk kérdések:

  1. Hogyan lehet eredményesen játszani ezt a játékot. 
  2. Valakinek létezik nyerő stratégiája? 
  3. Ha igen a válasz az előző kérdésre, akkor kinek van nyerő stratégiája, a kezdőnek vagy az ellenfelének? 
  4. Az előző kérdésre adható válasz függ-e attól, hogy mennyi kavics van induláskor a halomban? (Megjegyezzük, hogy nyerő stratégiája van annak a játékosnak, aki tud úgy játszani, úgy hogy ellenfele bármilyen, a szabályoknak megfelelő lépéssorozata estében ő megnyeri a játékot.)

A dörzsöltebb játszadozók már a játék nevéből is sejthetnek valamit. A jól ismert Nim játék jelzőként egy ismert matematikus nevét kapta. Miről is nevezetes Fibonacci? Egy nevezetes sorozat őrzi a nevét, az ebben a sorozatban szereplő számokat pedig Fibonacci számoknak nevezzük. Ezeknek a számoknak lehet köze a most tárgyalt játékunkhoz?

Nézzünk konkrét példákat! Legyen n a kavics halomban kezdetben levő kavicsok száma! (Nyilvánvaló, hogy n nem lehet kisebb kettőnél.)

  • Ha n = 2, akkor kezdő játékos csak 1 kavicsot vehet el, ekkor a második játékos elveheti a maradék 1 kavicsot, tehát a második játékosnak nyerő stratégiája van.
  • Ha n = 3, akkor a kezdő játékos 1 vagy 2 kavicsot vehet el ekkor a második játékos már elveheti a maradék kavicsokat, tehát neki nyerő stratégiája van
  • Ha n = 4, akkor a kezdő játékos elvehet 1 kavicsot, ezzel a második játékost hozza olyan helyzetbe, amiben n = 3 esetben a kezdő volt, így most a kezdő játékosnak van nyerő stratégiája.

Az n = 5 esetet a következő fa diagram szemlélteti:

Látható, hogy a második játékos tud úgy játszani, hogy bármit tesz a kezdő játékos, ő nyer, így a második játékosnak van nyerő stratégiája.

Nézzük meg az n = 6 esetet mutató fát!

Látható, hogy ebben az esetben a kezdő játékosnak van nyerő stratégiája.

Végül vizsgáljuk az n = 7 esetet bemutató fát!

Ebben az esetben is a kezdő játékosnak van nyerő stratégiája.Ebben az esetben is a kezdő játékosnak van nyerő stratégiája.Összefoglalva, a kezdő játékosnak az n =4, 6, 7 esetekben nyerő stratégiája volt, míg a második játékosnak az n = 2, 3, 5 esetekben nyerő stratégiája volt!Összefoglalva, a kezdő játékosnak az n =4, 6, 7 esetekben nyerő stratégiája volt, míg a második játékosnak az n = 2, 3, 5 esetekben nyerő stratégiája volt!Talán nem meglepő a korábbi előkészítés után, hogy a 2, 3, 5 Fibonacci számok!Talán nem meglepő a korábbi előkészítés után, hogy a 2, 3, 5 Fibonacci számok!A cikkben szereplő fákat különböző n-ekre el lehet készíteni, és ezek alapján – esetleg – közelebb lehet jutni a korábban feltett négy kérdés megválaszolásához.A cikkben szereplő fákat különböző n-ekre el lehet készíteni, és ezek alapján – esetleg – közelebb lehet jutni a korábban feltett négy kérdés megválaszolásához. 

Itt is játszhatjuk a játékot:

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
ENABLE pilot Program iskoláknak a bullying ellen
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek