infoarena informatica de performanta

Jocul NIM

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 vom folosi urmatoarea teorema:

Teorema: Fie N gramezi. Prima gramada are x₁ pietre, cea de a doua x₂, 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₁ xor x₂ ... xor x_N = 0.

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:

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.