Nim

Jocul NIM

Pentru a demonstra acest lucru, următoarele condiţii sunt necesare si suficiente:

# Dintr-o stare cu suma XOR 0, se poate ajunge doar în stări cu suma XOR pozitivă, sau jocul se termină. Scăzând din orice gramadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel putin un bit, deci şi suma XOR. Jocul se termină cand toate gramezile au 0 pietre, deci şi suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitiva, se poate ajunge intr-o stare cu suma XOR 0. Căutăm o gramadă cu un număr X de pietre, care are un bit de 1 pe poziţia bitului cel mai semnificativ al sumei XOR, notată cu S. Din acea grămadă se vor scădea X - (X XOR S) pietre, (X XOR S) fiind mai mic decat X deoarece se anulează bitul cel mai semnificativ al lui S. Suma XOR rămasă după scădere este egală cu 0.

# Dintr-o stare cu suma XOR 0, se poate ajunge doar în stări cu suma XOR pozitivă, sau jocul se termină. Scăzând din orice gramadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel puţin un bit, deci şi suma XOR. Jocul se termină cand toate grămezile au 0 pietre, deci şi suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitivă, se poate ajunge intr-o stare cu suma XOR 0. Căutăm o grămadă cu un număr X de pietre, care are un bit de 1 pe poziţia bitului cel mai semnificativ al sumei XOR, notată cu S. Din acea grămadă se vor scădea X - (X XOR S) pietre, (X XOR S) fiind mai mic decat X deoarece se anulează bitul cel mai semnificativ al lui S. Suma XOR rămasă după scădere este egală cu 0.

Pentru o demonstraţie mai pe larg şi alte variante de joc NIM, puteţi consulta acest 'articol':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf