Nim - počáteční situace
Nim - počáteční situace

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.


\\begin{array}{l}
3 = 011_{2} \\\\
4 = 100_{2} \\\\
5 = 101_{2} \\\\
\\end{array}

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).


\\begin{array}{r l}
3 =&011_{2} \\\\
4 =&100_{2} \\\\
5 =&101_{2} \\\\
\\hline
& 010_{2} \\\\
\\end{array}

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.


\\begin{array}{r l}
1 = & 001_{2} \\\\
4 = & 100_{2} \\\\
5 = & 101_{2} \\\\
\\hline
& 000_{2}
\\end{array}

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>.







Doporučujeme