Probabil cel mai cunoscut joc impartial este jocul de {$NIM$}. In acest joc, se considera $N$ gramezi, fiecare gramada avand un numar de pietre. La fiecare pas, jucatorul aflat la mutare elimina un numar nenul de pietre (eventual toate) dintr-o singura gramada. Jucatorii muta alternativ. Castigatorul este cel care ia ultimele pietre.
De obicei, jocul $NIM$ se joaca cu $3$ gramezi de pietre, insa strategia de castig este aceeasi indiferent de numarul gramezilor. Pentru a determina aceasta strategie ne vom folosi de operatia _xor_ ({_exclusive or_}) si proprietatile ei. Aceasta operatie se realizeaza prin operatorul $^$ in C/C++, si prin $xor$ in Pascal. Ca operatie pe biti, ea poate fi interpretata ca adunare in baza $2$ fara transport, dupa cum reiese din tabelul urmator:
De obicei, jocul NIM se joaca cu $3$ gramezi de pietre, insa strategia de castig este aceeasi indiferent de numarul gramezilor. Pentru a determina aceasta strategie vom folosi urmatoarea teorema:
<center>!teoria-jocurilor/jocul-nim?tabel.jpg!</center>
_Teorema_: Fie $N$ gramezi. Prima gramada are {$x{~1~}$} pietre, cea de a doua {$x{~2~}$}, si asa mai departe, pana la ultima care are {$x{~N~}$} pietre. O astfel de pozitie este pierzatoare in jocul de $NIM$ daca si numai daca _suma-xor_ a numerelor de pietre din gramezi este {$0$}, adica daca {$x{~1~} xor x{~2~} ... xor x{~N~} = 0$}.
De exemplu, $1 xor 7 xor 5 = 3$, deoarece avem:
Operatia _xor_ ({_exclusive or_}) se realizeaza prin operatorul $^$ in C/C++, si prin $xor$ in Pascal. Ca operatie pe biti, ea poate fi interpretata ca adunare in baza $2$ fara transport, dupa cum reiese din tabelul urmator:
{$1 = (001){~2~}$} {$xor$}
{$7 = (111){~2~}$}
{$5 = (101){~2~}$}
______________
{${@(011)@}{~2~} = 3$}
<center>!teoria-jocurilor/jocul-nim?tabel.jpg!</center>
Pe baza operatiei _xor_, strategia de castig pentru $NIM$ poate fi formulata conform urmatoarei teoreme:
De exemplu, $1 xor 7 xor 5 = 3$, deoarece avem:
_Teorema_: Fie $N$ gramezi. Prima gramada are {$x{~1~}$} pietre, cea de a doua {$x{~2~}$}, si asa mai departe, pana la ultima care are {$x{~N~}$} pietre. O astfel de pozitie este pierzatoare in jocul de $NIM$ daca si numai daca _suma-xor_ a numerelor de pietre din gramezi este {$0$}, adica daca {$x{~1~} xor x{~2~} ... xor x{~N~} = 0$}.
{$1{~10~} = 001{~(2)~}$}
{$7{~10~} = 111{~(2)~}$}
{$5{~10~} = 101{~(2)~}$}
________________________
{$011{~(2)~} = 3{~10~}$}
Pentru a demonstra aceasta teorema, trebuie sa aratam ca dintr-o stare cu _suma-xor_ egala cu $0$ (pierzatoare), oricum am muta, nu putem ajunge decat intr-o stare cu _suma-xor_ nenula (castigatoare), si ca dintr-o stare castigatoare putem efectua o mutare in mod convenabil astfel incat sa ajungem intr-o stare de pierdere.
Pentru a demonstra aceasta teorema, trebuie sa aratam ca dintr-o stare cu _suma-xor_ egala cu $0$, oricum am muta, nu putem ajunge decat intr-o stare cu _suma-xor_ nenula, si ca dintr-o stare cu suma-xor nenula putem efectua o mutare in mod convenabil astfel incat sa ajungem intr-o stare cu _suma-xor_ {$0$}.
