Úvod do teorie kombinatorických her

Betlová varianta hry (15-30, 3) NIM

Hráči z jedné hromádky zápalek odebírají 1, 2 nebo 3 zápalky. Pravidelně se střídají. Prohraje ten hráč, který je donucen vzít poslední zápalku. Na počátku hry (třeba losem) se určí, kdo bude začínat: počítač, nebo hráč. Zvolí se varianta 'složitosti' hry, tj. na základní desce bude 15-30 zápalek. Hra je determinovaná, tj. je předem rozhodnuto, který hráč vyhraje. Kritické pozice jsou totiž 1, 5, 9, ..., 1 + 4k. Stačí uvážit, že druhý hráč se snaží udržovat dorovnání počtu ještě neodebraných zápalek na počet p=1 (mod 4). Hry, ve kterých platí pravidlo Kdo poslední táhne, prohrál!, jsou betlové (misère). Díky determinovanosti hry, program, není-li ve vyhrávající pozici, odebere jednu zápalku (mohl by jich ale odebrat až tři). V partizánské variantě Kdo poslední táhne, vyhrál! je naopak výhodné být v pozici 1, 2, 3, ale ne 4 zápalek atd. Pozice p = 0 (mod 4) jsou prohrávající (kritické) pozice.

Zdroj: O appletu NIM