Co je Odčítací hra?
Odčítací hra je Nim s omezením každého tahu. Dál berete předměty z jedné hromádky podle své volby, ale nejméně jeden a nejvýš k, kde k je 2, 3, 4 nebo 5 a volí se v nastavení stolu (výchozí je 3). Celou hromádku smíte vzít jen tehdy, když obsahuje k nebo méně předmětů.
Vše ostatní je jako ve standardní hře: počáteční hromádky určuje stejná volba v nastavení (výchozí 1, 3, 5 a 7) a přepínač misère rozhoduje, zda vzetí posledního předmětu prohrává (zde výchozí), nebo vyhrává. Omezení mění aritmetiku hry. Velkou hromádku už nelze vyprázdnit jedním tahem, takže ji nelze použít k napravení pozice jedním úderem, a u každé hromádky záleží na její velikosti dělené k + 1: na zbytku.
Změny pravidel
| Pravidlo | Standardní Nim | Odčítací hra |
|---|---|---|
| Tahy | Standardní NimVezměte jeden nebo více předmětů z jedné hromádky, kolik chcete, až po celou hromádku. | Odčítací hraVezměte nejméně 1 a nejvýš k předmětů z jedné hromádky; k je 2, 3, 4 nebo 5, volí se v nastavení stolu (výchozí 3). |
| Hromádky | Standardní NimNěkolik hromádek: výchozí 1, 3, 5 a 7 předmětů, nebo jiná sada zvolená v nastavení stolu. | Odčítací hraStejné hromádky, volené stejnou možností. |
| Cíl | Standardní NimVýchozí je misère: kdo vezme poslední předmět, prohrává. Nastavení lze přepnout na normální hru, kde vzetí posledního předmětu vyhrává. | Odčítací hraStejně, se stejným přepínačem misère. |
| Vítězná hra | Standardní NimNormální hra: nechte hromádky s nim-součtem (bitovým XOR jejich velikostí) rovným nule. Misère: totéž, dokud by nezbyly jen hromádky o jednom předmětu; pak jich nechte lichý počet. | Odčítací hraNormální hra: každá hromádka se počítá jako zbytek své velikosti po dělení k + 1 a tyto zbytky necháváte s nim-součtem nula; jediná hromádka je pro hráče na tahu prohraná právě tehdy, když je její velikost násobkem k + 1. Misère: jediná hromádka je pro hráče na tahu prohraná právě tehdy, když je její velikost o jedna větší než násobek k + 1. |
Historie
Počítací hry s omezením každého tahu jsou staré. Sbírka matematických zábav Problèmes plaisants et délectables od Clauda-Gasparda Bacheta de Méziriac, poprvé vydaná v Paříži v roce 1612, popisuje hru, v níž dva hráči střídavě přičítají k průběžnému součtu číslo od 1 do 10 a kdo první dosáhne 100, vyhrává. Vítězným plánem je dosáhnout součtů 12, 23, 34 a tak dále až do 89, v krocích po 11: stejná aritmetika jako u jediné hromádky 100, z níž každý tah bere 1 až 10.
Samotný Nim dostal své jméno a úplnou teorii od Charlese L. Boutona v roce 1901. Práce Rolanda Sprague (1935) a Patricka Grundyho (1939) ukázaly, že každá hra tohoto druhu, včetně odčítací hry, se chová jako hromádka Nimu určité velikosti, a tak se řeší verze s několika hromádkami. Odčítací hry jsou standardním příkladem v teorii kombinatorických her, například v knize Winning Ways for your Mathematical Plays od Elwyna Berlekampa, Johna Conwaye a Richarda Guye.