Nim (odebírání zápalek) je kombinatorická hra pro dva hráče spočívající v odebírání objektů z několika hromádek. V každém tahu smí hráč odebrat odebrat několik objektů (vždy alespoň jeden, maximální počet je omezen pravidly dané varianty) z některé hromádky. Hráč, který odebere poslední objekt vyhrává.
Častou variantou je betlová hra – misère Nim, ve které kráč, který odebere poslední objekt, prohrává.
Historie hry
Původ této hry není zcela objasněn, ale má se za to, že pochází z Číny. První evropské odkazy na tuto hru pocházejí z 16. století. Výherní strategii pro Nim dokázal a publikoval v roce 1901 Charles L. Bouton v článku Nim, a game with a complete mathematical theory.
Výherní strategie
Základem výherní strategie je převedení jednotlivých hromádek do binární (dvojkové) soustavy. Předpokládejme, že máme 3 hromádky s 3, 4 a 5 objekty. Hráč smí odebrat 1, 2 nebo 3 objekty vždy právě z jedné hromádky.
Nyní sečteme bez přenosu do vyššího řádu jednotlivé cifry těchto čísel (provedeme operaci XOR). Výsledku budeme říkat nim-součet (nim-sum).
Abychom se dostali do výherní pozice, tak musíme upravit počty objektů tak, aby byl výsledek nulový. V tomto případě musíme změnit prostřední cifru prvního řádku na hodnotu 0 – to znamená, že musíme z první hromády odebrat dva objekty.
Bylo dokázáno, že protihráč nemůže hru ve svém tahu zvrátit, a zároveň ať bude hrát libovolným způsobem, tak jsme schopni jeho tah vyvážit – opět zajistit nulovost nim-součtu.
Modifikace pro misère Nim
Výherní strategie pro misère Nim je totožná, pouze v okamžiku, kdy již zbývají pouze hromádky velikosti 1, provedeme tah tak, aby jich zbyl lichý počet (dle strategie pro běžnou hru bychom ponechali sudý počet hromádek).
Literatura
- BOUTON, L. Charles. The Annals of Mathematics, 2nd Ser., Vol. 3, No. 1/4. (1901 - 1902), pp. 35-39.
- Nim. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 25 February 2002, last modified on 22 November 2010 [cit. 2010-11-27]. Dostupné z WWW: <http://en.wikipedia.org/wiki/Nim>.