h2. Jocul NIM

Probabil cel mai cunoscut joc impartial este jocul {$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.

Probabil cel mai cunoscut joc impartial este jocul {$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.

h4. Operatia _exclusive-or_
!>teoria-jocurilor/jocul-nim?tabel.jpg 80%!

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 alaturat.
 
De exemplu, $1 xor 7 xor 5 = 3$, deoarece avem:

Pentru a determina strategia de castig 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 alaturat.
Atunci cand facem _xor_ intre numere naturale trebuie mai intai sa transformam aceste numere in baza $2$, si apoi sa adunam fara transport bitii de pe fiecare pozitie. De exemplu, $1 xor 7 xor 5 = 3$, deoarece avem:

{$1 = (001){~2~}$}   {$xor$}
{$7 = (111){~2~}$}