Nim (hra)

Nim je hra, ve které se dva hráči střídají ve sbírání předmětů, které jsou rozděleny do několika hromádek. V jednom tahu lze vzít libovolný počet předmětů (větší než nula) z jedné hromádky. Vyhrává hráč, který si vezme poslední předmět. V klasické verzi hry je počet hromádek tři.

Zvláštní případ, kdy je hromádka pouze jedna, ale maximální počet předmětů, které lze vzít za kolo, je omezený, se nazývá Bacheova hra . Nim je kompletní informačně omezená hra . Klasická hra Nîmes je základem Sprague-Grundyho teorému . Tato věta říká, že běžná hra součtu nezaujatých her je ekvivalentní obyčejné hře Nim. Zároveň každý nestranný herní termín odpovídá hromadě Nim, přičemž počet objektů se rovná hodnotě funkce Sprague-Grundy pro herní pozici této hry.

Historie hry

O čínské hře se zmiňovali Evropané již v 16. století. Název „nim“ dal hře americký matematik Charles Bouton , který v roce 1901 popsal vítěznou strategii hry . Existuje několik možností původu názvu hry:

z německého slovesa nehmen nebo ze staroanglického slovesa Nim , což znamená „vzít“;
Anonymní z anglického slovesa Win ("vyhrát").

Hračka „Dr. Nim“, malý míčový počítač vynalezený v 60. letech, nehrála v něm, ale ve hře Basche .

Herní strategie

V obecném případě se uvažuje o hromadě položek s položkami. Hráči se střídají. Pohyb spočívá v tom, že hráč bere z hromady předmětů. Každé pozici hry je přiřazen součet této pozice - výsledek sečtení velikostí všech hromad v binárním číselném systému bez zohlednění přenosu bitů, to znamená přidání binárních číslic čísel v poli. zbytků modulo 2 : $p$ ${\displaystyle N_{1},N_{2},\cdots N_{p))$ $i\in [1,p]$ $n\in [1,N_{i}]$ ${\displaystyle S=N_{1}\oplus N_{2}\oplus \cdots \oplus N_{p))$

Vítěznou strategií je opustit pozici s ním – částka rovna nule po vašem pohybu. Vychází ze skutečnosti, že z libovolné pozice s nim-součtem, který se nerovná nule, lze jedním tahem získat pozici s nulovým součtem nim a z pozice s nulovým součtem nim, libovolným tahem. vede k pozici s nenulovým součtem nim .

Příklad : Předpokládejme, že jsou ve hře tři hromádky, které obsahují 2 (0010 v binárním vyjádření), 8 (1000) a 13 (1101) předmětů. Součet nim této pozice je 7 (0111). Vítěznou strategií je tedy vzít si tři předměty ze třetí hromádky - zbude 10 (1010) předmětů a součet nim pozice bude 0 (0000). Předpokládejme, že po vašem tahu soupeř vezme všechny předměty z první hromádky – vítěznou strategií by bylo vzít si dva předměty z třetí hromádky. V tomto případě po vašem tahu budou hromádky obsahovat 0 (0000), 8 (1000) a 8 (1000) položek, součet nim bude stále 0.

Možnosti

Obraťte to

Hráči dokončí hromádky až do určitého počtu . K dispozici jako quest v počítačové hře " Strážci vesmíru ". Hra je ekvivalentní běžnému stavovému nim . $N$ ${\displaystyle \{N-N_{i}\}_{i=1}^{p))$

Nim-Bashe

Nemůžete si vzít žádné další položky. Hra je ekvivalentní běžnému stavovému nim $k$ ${\displaystyle \{N_{i}\operatorname {mod} (k+1)\}_{i=1}^{p))$

Čokoláda

Je tam čokoládová tyčinka , jeden plátek "otrávený". Hráč sám rozbije čokoládu podél čáry a sní neotrávenou část. Ten, komu zbyde otrávený plátek, prohrává. Hra se rovná nim se čtyřmi hromádkami. $m\krát n$

Lakomec

V této variantě prohrává hráč, který vzal poslední předmět. Vítězná strategie je shodná s vítěznou strategií běžné hry až do okamžiku, kdy by v důsledku hráčova tahu měl na stole zůstat určitý počet hromádek s jediným předmětem v každé z nich. V případě lakomce musí hráč zanechat lichý počet hromádek, zatímco vítězná strategie běžné hry vyžaduje ponechání sudého počtu hromádek tak, aby součet neem byl nula. To lze formulovat následovně: pokud existuje právě jedna hromádka obsahující více než jednu položku, vezměte z ní všechny položky nebo všechny kromě jedné, takže zůstane lichý počet jednotlivých hromádek; jinak se držte vítězné strategie běžné hry.

Multinym

Obecnější případ hry Nîmes navrhl Eliakim Moore . Ve hře mohou hráči brát předměty maximálně z hromádek. Je snadné vidět, že obvyklá hra je on . Pro jeho vyřešení je nutné zapsat velikosti každé haldy v binární číselné soustavě a tato čísla sečíst v -ární číselné soustavě bez dělení slov. Pokud je číslo 0, pak aktuální pozice prohrává, v opačném případě vyhrává a je z ní přesun na pozici s nulovou hodnotou. $Nim_{i}$ $i$ $Nim_{1}$ $(i+1)$

Forked-nim

Další verzi hry navrhl Matvey Bernstein. V něm můžete libovolnou hromadu místo tahu libovolně rozdělit na dvě libovolné hromady. Ve všech ostatních ohledech se hraje podle obvyklých pravidel.

Ve filmu a televizi

Tato hra slouží jako metafora toho, co se děje ve filmu " Loni v Mariánských Lázních " [1] .

Viz také

Poznámky

↑ Oliver Knill. Matematika ve filmech : Loni v Mariánských Lázních . Matematika ve filmech . Katedra matematiky Harvardská univerzita. Datum přístupu: 22. června 2009. Archivováno z originálu 21. února 2012.

Literatura

Ball W., Coxeter G. Matematické rekreace a eseje. - M .: Mir, 1986. - S. 47-51.
Fomin SV Číselné soustavy . - 5. vyd. - M .: Nauka, 1987. - S. 48.
Gardner M. Piškvorky. —M.: Mir, 1988. ISBN 5-03-001234-6 .
Jean-Paul Delahaye . Stratégies magiques au pays de Nim // Pour la science: Journal. - Paříž: Belin, 2009. - T. 377 , č. 3 . - S. 88-93 . Archivováno z originálu 10. června 2013.