iMatek

Nim stratégiai játék

  • logika, nim játék, nim-összeg, stratégia, számrendszerek

Mire jó a Matek?

Picture of matematikai alkalmazások

matematikai alkalmazások

Matematikai érdekességek, amelyek jól jöhetnek az érettségin vagy a felvételin is.

Alkalmazások
nim

Oszd meg, ha tetszik!

A kettes számrendszer a kulcs a nyeréshez

A Nim játék egy ősi stratégiai játék, amely a kombinatorikus játékelmélet fontos példája. Ebben a posztban bemutatjuk a Nim játék történeti hátterét, a játékszabályokat, a játék során alkalmazandó stratégiákat, valamint részletesen tárgyaljuk a Nim-összeg fogalmát. A játékban nyerő helyzetek kiszámítása a Nim-összeg segítségével történik, amely lehetővé teszi, hogy a játékosok kiszámítsák a legjobb lépést minden helyzetben.
A Nim játék eredete nem teljesen ismert, de évszázadok óta játszották különböző formákban a világ számos részén. A játék modern változatának matematikai elemzését Charles L. Bouton készítette el 1901-ben, aki először dolgozta ki a nyerő stratégiát, és bevezette a Nim-összeg fogalmát. A játék érdekes módon kapcsolatban áll a digitális rendszerekkel, mivel a stratégia kulcsa a kettes számrendszerben végzett műveletek alkalmazása.
A Nim játékszabályai
A Nim játékban az alábbi alapvető szabályok érvényesek:
  1. A játékosok előtt több sorban különböző számú elemek találhatók (például korongok, kövek, stb.).
  2. Két játékos felváltva lép.
  3. Egy lépésben egy sorból a játékos tetszőleges számú elemet eltávolíthat (akár egyet, akár az összeset).
  4. A játék addig tart, amíg minden elem el nem fogy.
  5. Az a játékos veszít, aki az utolsó elemet eltávolítja.
A Nim játék egy ősi stratégiai játék, amely a kombinatorikus játékelmélet fontos példája. Ebben a posztban bemutatjuk a Nim játék történeti hátterét, a játékszabályokat, a játék során alkalmazandó stratégiákat, valamint részletesen tárgyaljuk a Nim-összeg fogalmát. A játékban nyerő helyzetek kiszámítása a Nim-összeg segítségével történik, amely lehetővé teszi, hogy a játékosok kiszámítsák a legjobb lépést minden helyzetben.
A Nim játék eredete nem teljesen ismert, de évszázadok óta játszották különböző formákban a világ számos részén. A játék modern változatának matematikai elemzését Charles L. Bouton készítette el 1901-ben, aki először dolgozta ki a nyerő stratégiát, és bevezette a Nim-összeg fogalmát. A játék érdekes módon kapcsolatban áll a digitális rendszerekkel, mivel a stratégia kulcsa a kettes számrendszerben végzett műveletek alkalmazása.
A Nim játékszabályai
A Nim játékban az alábbi alapvető szabályok érvényesek:
  1. A játékosok előtt több sorban különböző számú elemek találhatók (például korongok, kövek, stb.).
  2. Két játékos felváltva lép.
  3. Egy lépésben egy sorból a játékos tetszőleges számú elemet eltávolíthat (akár egyet, akár az összeset).
  4. A játék addig tart, amíg minden elem el nem fogy.
  5. Az a játékos veszít, aki az utolsó elemet eltávolítja.
Az oldal alján található egy Nim játék, amellyel érdemes néhány menetet játszani, ha meg akarjuk érteni a nyerő stratégiát. Az első játék után lehetőség van beállítani a korongok számát, amellyel többféle játékot ki lehet próbálni.
Mielőtt a nyerő stratégia levezetését elkezdenénk érdemes megnézni néhány egyszerű játékhelyzetet. A következő ábrákon a \(\bullet\) (tömör körök) az egyes csoportokban lévő elemeket jelölik, a \(\color{#71abff}{\bullet}\) (kék körök) az egyes játékosok lépéseit, az \(\circ\) (üres körök) a már elvett elemek helyét, a \(|\) (függőleges vonalak) pedig az egyes sorok (csoportok) határát. A fenti Nim játékszabályok alapján egymás alatti sorokban mutatjuk be a két játékos lépéseit.
\[ \begin{array}{c|c} \text{j\’at\’ekos}&\text{j\’at\’ek helyzete}\\ \hline A&\color{#71abff}{\bullet}\color{#71abff}{\bullet}\bullet | \bullet\bullet | \bullet\\ B&\circ\circ\bullet | \color{#71abff}{\bullet}\color{#71abff}{\bullet} | \bullet\\ A&\circ\circ\bullet |\circ\circ |\color{#71abff}{\bullet}\\ B&\circ\circ\color{#71abff}{\bullet} | \circ\circ |\circ\\ \color{#008454}{A}&\circ\circ\circ | \circ\circ | \circ\\ \end{array}\notag \]
A játékot az \(A\) játékos nyerte, ugyanis az utolsó elemet \(B\) vitte el. Nézzük át a lépéseket és vizsgáljuk meg, hogy valamelyik játékosnak nem lett volna-e jobb lépése, azaz nem hibázott-e valamelyikük. Kezdjük \(B\) első lépésével:
\[ \begin{array}{c|c} \text{j\’at\’ekos}&\text{j\’at\’ek helyzete}\\ \hline A&\color{#71abff}{\bullet}\color{#71abff}{\bullet}\bullet | \bullet\bullet | \bullet\\ B&\circ\circ\bullet | \bullet\bullet | \color{#71abff}{\bullet}\\ A&\circ\circ\bullet | \color{#71abff}{\bullet}\bullet | \circ\\ B&\circ\circ\color{#71abff}{\bullet} | \circ\bullet | \circ\\ A&\circ\circ\circ | \circ\color{#71abff}{\bullet} | \circ\\ \color{#008454}{B}&\circ\circ\circ | \circ\circ | \circ\\ \end{array}\notag \]
A második lépésben \(B\) változtatott és nyert. Bár a nyerő stratégia alapjait még nem vizsgáltuk meg, de előzetesen azt is mondhatjuk, hogy \(B\) végig hibátlanul játszott és \(A\)-nak csak akkor volt esélye nyerni, ha \(B\) hibázott.
Egy másik kérdés is felmerül a játék kapcsán. Van-e nyertes vagy vesztes helyzet? Ennek megítéléséhez nézzünk két egyszerű példát. A \(\bullet |\bullet |\bullet\) helyzet egyértelműen vesztes helyzet annak, aki a következő elemet veszi el, ugyanis az utolsó is biztosan neki jut. Tehát biztosan van vesztes helyzet, amelyet el sem lehet rontani. Legyen most a játék helyzete \(\bullet\bullet |\bullet\bullet\), amelyben biztosan vesztes lépés ha valamely játékos mindkét elemet elveszi az egyik halmazból, mert a másik biztosan nyer a maradékból egyet elvéve. Sajnos azzal a lépéssel sem lehet nyerni, ha egyet vesz el az első játékos, és a másik játékos nem hibázik, ugyanis ekkor a másik játékos kettőt vesz el a másik halmazból így egyetlen egy marad, amely szintén ahhoz vezet, hogy az elsőnek lépő játékos veszít. A későbbiekben látni fogjuk, hogy a két helyzet lényegesen különbözik a stratégia szempontjából, bár egyik sem nyújt nyerési esélyt a kezdő játékosnak, ha a másik nem hibázik.
Térjünk vissza az első példához, és keressünk egy olyan tulajdonságot, amely egyértelmű nyerést vagy vereséget jelent a kezdő játékosnak. Ha találunk ilyet, akkor ez a helyzet egy stratégiai cél lehet, főleg akkor, ha hibátlan játék mellett ez már biztos győzelmet jelent valamelyik játékosnak. A nyerő stratégia levezetése helyett induljunk ki magából a stratégiából és vizsgáljuk meg, hogy hogyan működik, amelyhez definiáljuk a Nim-összeget.
Nim-összeg
Az egyes sorokban lévő elemek számát felírjuk kettes számrendszerben, majd a kapott számok között (bitenként) elvégezzük a \(XOR\), azaz a “kizáró vagy” műveletet. A “kizáró vagy” logikai művelet jele \(\oplus\), a hozzá tartozó értéktáblázat:
\[ \begin{array}{|c|c|c|} \hline A&B&A\oplus B\\ \hline 0&0&0\\ \hline 0&1&1\\ \hline 1&0&1\\ \hline 1&1&0\\ \hline \end{array}\notag \]
Legyen \(a=5\) és \(b=7\), és számítsuk ki \(a\oplus b\) értékét.
\[ \begin{aligned} \phantom{\oplus\;}a=5_{10}&=011_2\\ \oplus\; b=7_{10}&=111_2\\ \hline &\phantom{=l}100_2 \end{aligned}\notag \]
Tehát \(5\oplus 7=100_2=8\), amely egyben a \(\bullet\bullet\bullet\bullet\bullet | \bullet\bullet\bullet\bullet\bullet\bullet\bullet\,\) alakú Nim játékhoz tartozó Nim-összeg.
Nim játék nyerő helyzete
A játék egy adott állapotában akkor és csak akkor van nyerő stratégiája a soron következő játékosnak, ha a Nim-összeg nem nulla. Az állítást úgy is megfogalmazhatjuk, hogy ha a játék adott állapotában a Nim-összeg nulla akkor a soron következő játékos nem tud nyerni, ha a másik játékos nem hibázik. Nézzünk egy játékot, amelynek levezetése során az egyes helyzetekhez meghatározzuk a Nim-összeget, hogy lássuk kinek milyen esélyei vannak.
\[ \begin{array}{c|c|c} \text{j\’at\’ekos}&\text{j\’at\’ek helyzete}&\text{Nim-\Hoe sszeg}\\ \hline A&\bullet\bullet\bullet | \bullet\bullet\color{#71abff}{\bullet} | \bullet&11_2\oplus 11_2\oplus 01_2=01_2=1_{10}\\ B&\bullet\bullet\color{#71abff}{\bullet} | \bullet\bullet\circ | \bullet&11_2\oplus 10_2\oplus 01_2=00_2=0_{10}\\ A&\bullet\bullet\circ |\bullet\bullet\circ |\color{#71abff}{\bullet}&10_2\oplus 10_2\oplus 01_2=01_2=1_{10}\\ B&\color{#71abff}{\bullet}\color{#71abff}{\bullet}\circ |\bullet\bullet\circ |\circ&10_2\oplus 10_2=00_2=0_{10}\\ A&\circ\circ\circ |\bullet\color{#71abff}{\bullet}\circ |\circ&\\ B&\circ\circ\circ |\color{#71abff}{\bullet}\circ\circ |\circ&\\ A&\circ\circ\circ |\circ\circ\circ |\circ&\\ \end{array}\notag \]
A korábban megfogalmazott nyerő helyzet feltétele szerint értékeljük a játékot. Az \(A\) játékosnak nyerő helyzete volt a kezdeti lépés során, amelyet ki is használt, ugyanis úgy alakította át, hogy \(B\)-hez már nulla Nim-összegű játék került. \(B\) nem tudott (nem is lehet) úgy elvenni elemeket, hogy a Nim-összeg nulla legyen, így csak abban bízhatott, hogy \(A\) hibázik. \(A\) következő lépése során sem hibázott, így végül nyert.
A korábban megfogalmazott nyerő helyzetre vonatkozó szabály alkalmazásához két fontos megállapítást tehetünk az előző játék alapján.
  1. Ha egy csoport kiürül, akkor nem vesszük figyelembe a Nim-összeg kiszámításakor.
  2. Ha már csak egyetlen csoportban van egynél több elem, akkor a nyerő lépés, ha egy kivételével az összeset elvesszük.
A nyerő helyzet és a Nim-összeg használata csak abban segített, hogy felismerjük, hogy nyerő helyzetben vagyunk-e, illetve mire kell törekednünk a játék során:
  1. Ha olyan helyzetben mi léphetünk, amikor a Nim-összeg nem nulla, akkor nyerő helyzetben vagyunk.
  2. Ha a Nim-összeg nem nulla, akkor úgy kell elvennünk elemeket, hogy nullára változzon.
A játék hosszú történelme során ennél pontosabb stratégiát is sikerült kialakítani, amelyet a következő fejezetben ismerhetünk meg.
A stratégia
Ha valaki ismeri a stratégiát és nem vesztes helyzetben kapja meg az első lépés lehetőségét, akkor a nyertes lépések minden esetben elérhetőek számára és csak a számára, azaz ha nem hibázik, akkor biztosan nyer.
A Nim-összeg továbbra is a segítségünkre lesz. Ha nem nulla Nim-összegű játékhelyzetet kapunk, akkor a Nim-összeg és minden csoport értéke között végezzük el a \(XOR\) műveletet. Egyetlen sor esetében fog az eredeti csoporthoz tartozó szám csökkeni a \(XOR\) művelet után. ebből a sorból kell elvenni eleme(ke)t úgy, hogy ezzel a lépéssel nulla lesz a Nim-összeg, így a másik játékosnak továbbra sincs esélye nyerni. A fenti stratégia minden helyzetben egyértelműen működik.
Nézzünk ismét egy játékot, amelyen kipróbálhatjuk a stratégiánkat, azaz egy nem nulla Nim-összegű helyzetből indulunk ki és a stratégiai lépéseket követően azt várjuk, hogy a Nim-összeg nulla lesz. Legyen a játék \(\bullet\bullet | \bullet\bullet\bullet |\bullet\bullet\bullet\bullet\bullet\bullet\bullet\,\), amelynek a csoportokban lévő elemek számát jelöljük \(s_i\)-vel, ahol \(i=1,2,3\), a játékhoz tartozó aktuális Nim-összeget jelöljük \(N\)-nel.
\[ \begin{aligned} \phantom{\oplus\;}s_1=2_{10}&=010_2\\ \phantom{\oplus\;}s_2=3_{10}&=011_2\\ \oplus\; s_3=7_{10}&=111_2\\ \hline &\phantom{=l}110_2=6_{10} \end{aligned}\notag \]
Tehát \(N=6\), így a soronkénti \(XOR\) műveletet is el tudjuk végezni.
\[ \begin{array}{c|c|c} s_i&s_i\oplus N&\text{Cs\Hoe kkent?}\\ \hline 2_{10}=010_2&010_2\oplus 110_2=100_2=6_{10}&\times(2 < 6)\\ \hline 3_{10}=011_2&011_2\oplus 110_2=101_2=5_{10}&\times(3 < 5)\\ \hline 7_{10}=111_2&111_2\oplus 110_2=001_2=1_{10}&\checkmark 7 > 1\\ \end{array}\notag \]
A stratégia szerint az utolsó csoportból kell elvenni eleme(ke)t. A játék következő állapota \(\bullet\bullet |\bullet\bullet\bullet |\bullet\circ\circ\circ\circ\circ\circ\,\), amelyhez a Nim-összeg nulla.
A következő lépésben meghatározzuk, hogy a kiválasztott csoportból hány elemet kell elvenni. Ha nem szeretnénk elvégezni az előző számítást minden lépés előtt, akkor egy könnyítés: Legyen az \(N\) Nim-összeg kettes számrendszerbeli alakjának balról számított első \(1\)-es számjegye a jobbról számított \(k\)-adik számjegy. Válasszuk ki azt az \(s_i\) elemű csoportot, amelynek a kettes számrendszerben felírt értékének (elemek számának) jobbról számított \(k\)-adik számjegye szintén \(1\). Ekkor legyen \(m=s_i\oplus N\), amely pozitív és teljesülni fog rá, hogy \(m < N\). Az előző példában \(N=6\), \(s_3=7\), így \(m=7\oplus 6=1\).
Végül vegyünk el az \(s_1\) számosságú csoportból \(s_i-m\), azaz az előző példánál maradva \(7-1=6\) darab elemet.
Ha egyszerűbb memorizálni egy-egy helyzetet, akkor az alábbiakban felsoroljuk azokat az állásokat, amelyek Nim-összege nulla, a \(2\)-es, a \(3\)-as és a \(4\)-es csoportokba osztott elemek esetén. A \(3\)-as csoportot tartalmazó sorban van egy elem, amely Nim-összege nem \(0\), ennek ellenére azonos tulajdonságú, azaz nem lehet nyerni ebből az állapotból annak a játékosnak aki következik.
\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2-es csoport}&2\;2&3\;3&4\;4&n\;n\\ \hline \text{3-as csoport}&\color{#71abff}{1\;1\;1}&1\;2\;3&1\;4\;5&1\;6\;7&1\;8\;9&2\;4\;6&2\;5\;7&3\;4\;7&3\;5\;6&4\;8\;12&4\;9\;13&\ldots\\ \hline \text{4-es csoport}&1\;2\;4\;7&1\;2\;5\;6&1\;3\;4\;6&1\;3\;5\;7&2\;3\;4\;5&2\;3\;6\;7&2\;3\;8\;9&4\;5\;6\;7&4\;5\;8\;9&n\;n\;\;m\;m&m\;m\;\;m\;m&\ldots\\ \hline \end{array}\notag \] \[\begin{array}{l}\quad n\ne m, n > 0,m > 1\end{array}\notag\]
A fenti táblőázatba bekerült egy olyan elem, amelynek a NIm-összege nem nulla \((1,1,1)\), amely mellett van másik két kivétel is, amelyek Nim-összege nulla, azonban mégsem biztosítanak nyereményt a kezdő lépést végző játékosnak. Az \((1,1)\) és az \((1,1,1,1)\) helyzetek éppen fordítva működnek, az elsőnek lépő játékos fog nyerni.
A fentiekben levezetett stratégia meglehetően sok számítást kíván, amely rontja a játékélményt. Szerencsére a leírtak alapján készíthetünk egy olyan ellenőrzést, amelyhez nem kell ilyen sokat számolni. Csoportosítsuk minden sorban az elemeket úgy, hogy egy-egy csoportba mindig kettő hatványinak megfelelő számú elem kerüljön. A csoportokat mindig úgy alakítsuk ki, hogy egy sorban kettő lehető legnagyobb hatványával csoportosítsuk az elemeket, minden lépésben. Például ha \(7\) elem van, akkor a megfelelő csoportosítás \(4,2,1\) (a \(2,2,2,1\) csoportosítás nem megfelelő). Ha elvégeztük a csoportosítást, akkor számoljuk össze a teljes játékban az azonos számú elemeket tartalmazó csoportokat. Ha minden esetben páros számú csoportokat kapunk, akkor a Nim-összeg nulla. Ellenkező esetben a Nim-összeg nem nulla, és úgy érdemes elemeket elvenni, hogy az azonos elemszámú csoportból páros számú legyen. A fenti módszert az alábbi játékhelyzeten követhetjük végig.
\[ \begin{array}{c} \bbox[2pt,#71abff]{\bullet\,\bullet}\\ \bbox[2pt,#71abff]{\bullet\,\bullet}\bbox[2pt,#55D9A9]{\bullet}\\ \bbox[2pt,#ffab00]{\bullet\bullet\bullet\,\bullet}\bbox[2pt,#55D9A9]{\bullet}\\ \bbox[2pt,#be87dd]{\bullet\bullet\bullet\bullet\bullet\bullet\bullet\,\bullet}\\ \end{array}\notag \]
A fenti ábráról leolvashatjuk, hogy a négy és a nyolc elemet tartalmazó csoportból van páratlan számú (egy-egy). Ha a \(8\) elemet tartalmazó csoportból elveszünk \(4\)-et, akkor a játékhelyzet Nim-összege \(0\) lesz.
5. Becslések – Egyetemi statisztika
Statisztikai becslések
2025

5. Becslések – Egyetemi statisztika

790 Ft
(Az ár tartalmazza a 27% ÁFA-t)
A kurzus lejárata:
2025. július 15.
                        Részletek Vásárlás
6. Hipotézisvizsgálat – Egyetemi statisztika
Hipotézisvizsgálat
2025

6. Hipotézisvizsgálat – Egyetemi statisztika

790 Ft
(Az ár tartalmazza a 27% ÁFA-t)
A kurzus lejárata:
2025. július 15.
                        Részletek Vásárlás

Kapcsolat

Dokumentumok

Pénzügyi Partnerünk

CIB Bank

Elfogadott kártyák

Bankkártyák

Vásárlási kisokos

    Írj nekünk!



    Facebook Map-marker-alt Tiktok

    Ügyfélszolgálat

    • Telefon: +36 30 427-6190
    • hétfő-péntek: 8:00-16:00
      Copyright © iMatek 2020-2025 – Minden jog fenntartva