A nim-játékot ketten játsszák. Véges számú, meg nem különböztetett elemet (a gyakorlatban gyufákat, gombokat stb.) tetszés szerinti számú halomba osztunk. A játékosok felváltva tesznek egy-egy lépést. Egy lépés abban áll, hogy tetszés szerint választott egyik halomból veszünk el valamennyi elemet, legalább egyet, de elvehetjük az egész halmot is. Az nyer, aki az utolsó elemet veszi el, akár egymagában, akár más, ugyanazon halomhoz tartozó elemekkel együtt.
A játék nyerő stratégiája általánosan ismert. A matematikai irodalomban a játék, úgy látszik, első ízben 1902-ben szerepelt Bouton egy rövid közlésében, ami az Annals of Mathematics c. folyóiratban jelent meg. E közlés leírja a nyerő stratégiát és a stratégia helyességének bizonyítását; nem írja azonban le, hogyan jutott a stratégiához. Úgy tudom, hogy a játékról szóló egyéb közlések sem pótolták e hiányt. Pedig egy probléma megoldása kevésbé tanulságos, ha nem árulja el, hogyan lehet a megoldáshoz jutni. Különösen igaz ez, ha a megoldás ‐ mint a nim-játék esetében ‐ váratlan, úgyszólván hajánál fogva előhúzottnak látszik.
E sorok írója a játékkal 1913-ban ismerkedett meg, mint feladattal: keresd meg a nyerő stratégiát. Ez sikerült is, de csak váratlanul hosszas, kacskaringós keresés után. Az 50 év előtti gondolatmenetek felújítása azt mutatta, hogy a megoldási menet több fázisában olyan módszer szerepelt, amit Pólya György számos közlésében és több könyvében heurisztikusnak nevezett. Ezért talán nem haszontalan a tényleges megoldást, a zsákutcákban végződő kísérletektől megtisztítva, némi részletességgel vázolni.
Minden egyes lépés előtt a játszma helyzetét az egyes halmokban megmaradt elemek számai jellemzik; két halom esetén egy számpár, három esetén egy szám-trió s í. t. Kérdés, lehet-e olyan játékmódot találni, aminek ismeretében a játékos okvetlen nyer, bármilyen lépéseket is tesz ellenfele. A nyerő stratégia lényege, hogy a játékos mindig tudja, milyen helyzetet hagyhat ellenfele számára. Az ilyen helyzetet vesztő állásnak nevezzük, ha pedig egy állás nem ilyen, megnyerhetőnek mondjuk. Miután a feltételezett nyerő stratégiát mindkét játékos ismerheti, a helyes játék is csak akkor biztosítja a nyerést, ha az illető játékos első lépése előtt az állás nem volt vesztő. Az így értelmezett vesztő állásokra nyilvánvaló, hogy
1. egyikből sem lehet egy másikba egyetlen lépéssel eljutni;
2. megnyerhető állásból okvetlen lehet egyetlen lépéssel vesztő állást előállítani.
Nyilvánvalóan vesztő állás az a két halmos helyzet, amelyikben mindkét halom egy tárgyból áll: a soron levő játékos el kell vegye az egyik elemet, társa a másikat veszi és nyer.
A játék állását úgy írjuk le, hogy a halmok elemeinek számait növekvő sorrendben, vesszőkkel elválasztva, zárójelben írjuk fel, pl. $\left(\mathrm{2,}\mathrm{5,}10\right)$, $\left(\mathrm{1,}\mathrm{1,}2\right)$ stb. Egyelőre speciálisan párokra és triókra keresünk stratégiát. (Aki előtt csak egy halom van, az azt elveszi és nyer.)
Számpár esetén néhány próba után könnyen rá lehet jönni, hogy azok a vesztő állások, amelyekben a két szám egyenlő. Valóban, az egyenlőséget bármely lépés megszünteti; ha a két szám nem egyenlő, az egyenlőséget egy lépésben elő lehet állítani; az $\left(\mathrm{1,}1\right)$ vesztő pár pedig speciális esete a szabálynak. Két halom esetén tehát tényleg van egyszerű stratégia. Hogy áll a dolog, ha három halomról van szó ?
Egy vesztő trió számainak különbözőknek kell lenniük, különben egy lépéssel vesztő párt lehetne előállítani. Minden trió három párt tartalmaz. Két vesztő trió nem tartalmazhatja ugyanazt a párt, különben valamelyikből egy lépéssel lehetne előállítani a másikat. Általánosabban: vesztő triók tetszés szerinti halmazában egy számpár csak egyszer szerepelhet, mint valamelyik trió része.
A legegyszerűbb, különböző számokból álló trió az $\left(\mathrm{1,}\mathrm{2,}3\right)$. Kevés próbálkozás mutatja, hogy ez vesztő hármas, mert bármit elvéve vagy $\left(a\mathrm{,}b\right)$ vagy $\left(a\mathrm{,}a\mathrm{,}b\right)$ alakú helyzet áll elő, ahol $a\ne b$. Az $\left(\mathrm{1,}\mathrm{3,}4\right)$ hármas viszont nem vesztő, mert az $\left(\mathrm{1,}3\right)$ pár az $\left(\mathrm{1,}\mathrm{2,}3\right)$-nak része.
Következik sorban az $\left(\mathrm{1,}\mathrm{4,}5\right)$ trió. Ennek bármelyik csoportjából vesz is el partnerünk, mi vagy $\left(a\mathrm{,}a\right)$ alakú párt hozhatunk létre (ha hagyott két egyenlő halmot, vagy ha egyet teljesen elvett), vagy az $\left(\mathrm{1,}\mathrm{2,}3\right)$ helyzetet, és ezekről már tudjuk, hogy vesztő állások, tehát $\left(\mathrm{1,}\mathrm{4,}5\right)$ is az. Ugyanígy jutunk az $\left(\mathrm{1,}\mathrm{6,}7\right)$ vesztő trióhoz. Merésznek látszó (nem teljes !) indukció arra a feltevésre vezet, hogy $\left(\mathrm{1,}2n\mathrm{,}2n+1\right)$ általában vesztő trió. Egy így is van. Bármit lép is a partner, a következő lépéssel vagy egy $\left(\mathrm{1,}2k\mathrm{,}2k+1\right)$ alakú triót lehet előállítani, ahol $k<n$, vagy egy $\left(k\mathrm{,}k\right)$ alakú vesztő párt. Ennek igazolását az olvasóra bízzuk. Így általános formulát nyertünk azokra a vesztő triókra, amikben a legkisebb szám $1$. Ezen az úton lehetne tovább haladni, de a partner lehetséges lépéseinek száma gyorsan növekszik, és ezzel együtt fokozódnak a közvetlen kipróbálással történő bizonyítás nehézségei. Más eljárást kell keresnünk.
Remélni lehet, hogy vesztő triók egyes sajátságait felismerhetjük, ha nagy számú ilyen triót találunk. Célszerűnek látszik például, ha igyekszünk előállítani az összes vesztő triókat, amikben egy megadott számnál nagyobb nem fordul elő. Miután tudjuk, hogy egy vesztő trió halmazban egy bizonyos számpár csak egyszer fordulhat elő, közelálló gondolat azokból a számpárokból kiindulni, amikben az adott számnál nincs nagyobb. Ezekből triókat úgy kell felépítenünk, hogy minden felhasznált számpárt (egyetlen trió képzésére három számpár szükséges) elhagyunk, és a további triókat a maradó párokból állítjuk össze. Hogy az eljárást egyértelművé tegyük, a számpárokat határozott sorrendben írjuk, és mindig lehetőleg a sorrendben előbb álló számpárokat használjuk fel trió képzésre.
A számpárokat elsősorban a kisebbik szám nagyságrendjében írjuk. Ha a két kisebb szám egyenlő, akkor a sorrendet a két nagyobb szám határozza meg. Tehát $\left(\mathrm{2,}6\right)$ megelőzi $\left(\mathrm{3,}4\right)$-et, és $\left(\mathrm{3,}1\right)$ megelőzi $\left(\mathrm{3,}9\right)$-et. Áttekinthetőség kedvéért azokat a párokat, amiknek kisebb száma ugyanaz, egy sorba írjuk. Ez alá kerül az a (rövidebb) sor, amiben a kisebb szám a megelőzőnél $1$-gyel nagyobb. Derékszögű háromszög alakú séma jön így létre, aminek átfogójában azok a párok vannak, amiknek nagyobb száma a megengedett legnagyobb szám. Előnye sémánknak az, hogy ha a megengedett legnagyobb szám helyébe egy nagyobb szám kerülne, a hozzájáruló párokat a nagyobb számok sorrendjében az egymás után következő átfogókba lehet írni anélkül, hogy a kisebb sémán közbeiktatásokkal bármit változtatni kellene. Az átfogókat a párok közös nagyobb száma szerint sorra $2$-es, $3$-as, $4$-es stb. átfogónak fogjuk nevezni. Ha például $6$ a megengedett legnagyobb szám, akkor a $15$ lehetséges pár így rendeződik el: