Sa presupunem prin reducere la absurd ca dintr-o stare cu suma-xor $0$ putem ajunge in alta stare care are suma-xor tot $0$. Selectam o gramada oarecare cu $y$ pietre si dorim sa eliminam un numar de pietre din aceasta gramada. Daca notam cu $S$ suma-xor a numerelor de pietre din celelalte $N-1$ gramezi neselectate, atunci avem {$S xor y = 0$}. Dar {$a xor b = 0$} daca si numai daca {$a = b$}, deci {$S = y$}. Daca din gramada selectata eliminam $x$ pietre, {$0 < x &le; y$}, pentru a ajunge intr-o stare tot cu suma-xor $0$ trebuie sa avem {$S xor (y-x) = 0$}, echivalent cu {$S = y-x$}. De aici si din {$S = y$} rezulta ca {$x = 0$}, fals. Deci oricum am efectua o mutare dintr-o stare de pierdere vom ajunge intr-o stare castigatoare.

Ramane de demonstrat ca din orice stare de castig putem sa aducem adversarul intr-o stare pierzatoare. Fie $S$ suma-xor a marimilor celor $N$ gramezi. Daca exista o gramada cu $y$ pietre astfel incat {$y > y xor S$}, atunci putem elimina {$y - y xor S$} pietre din aceasta gramada, ramanand cu {$y - (y - y xor S) = y xor S$} pietre. Din gramada cu $y$ pietre am obtinut o gramada cu {$y xor S$} pietre, deci noua suma-xor va fi obtinuta din cea veche ({$S$}) xorata cu ea insasi: {$(... xor y) xor S = S xor S = 0$}. In consecinta, daca exista o gramada cu proprietatea de mai sus, atunci putem ajunge din orice stare de castig in una de pierdere. Fie $p$ pozitia celui mai semnificativ bit din reprezentarea binara a lui {$S$}. Printre cele $N$ gramezi, va exista cel putin una care are bitul de pe pozitia $p$ egal cu $1$ (altfel bitul $p$ din $S$ ar fi fost {$0$}). Fie $y$ numarul de pietre dintr-o astfel de gramada. Bitii de $1$ din $y$ si $S$ de pe pozitia $p$ se vor anula pentru ca {$1 xor 1 = 0$}. Astfel, vom avea {$y > y xor S$}:

Ramane de demonstrat ca din orice stare de castig putem sa aducem adversarul intr-o stare pierzatoare. Fie $S$ suma-xor a marimilor celor $N$ gramezi. Daca exista o gramada cu $y$ pietre astfel incat {$y > y xor S$}, atunci putem elimina {$y - y xor S$} pietre din aceasta gramada, ramanand cu {$y - (y - y xor S) = y xor S$} pietre. Din gramada cu $y$ pietre am obtinut o gramada cu {$y xor S$} pietre, deci noua suma-xor va fi obtinuta din cea veche ({$S$}) xorata cu ea insasi: {$(... xor y) xor S = S xor S = 0$}. In consecinta, daca exista o gramada cu proprietatea de mai sus, atunci putem ajunge din orice stare de castig in una de pierdere. Fie $p$ pozitia celui mai semnificativ bit din reprezentarea binara a lui {$S$}. Printre cele $N$ gramezi, va exista cel putin una care are bitul de pe pozitia $p$ egal cu $1$ (altfel bitul $p$ din $S$ ar fi fost {$0$}). Fie $y$ numarul de pietre dintr-o astfel de gramada. Bitii de $1$ din $y$ si $S$ de pe pozitia $p$ se vor anula pentru ca {$1 xor 1 = 0$}. Astfel, vom avea {$y > y xor S$}.

<center>!teoria-jocurilor/jocul-nim?xor.bmp!</center>

<center>!teoria-jocurilor/jocul-nim?xor.bmp 70%!</center>

In consecinta, putem ajunge din orice stare de castig intr-o stare de pierdere. Teorema este astfel demonstrata.