In proving certain results about Nim, I found a lemma that is causing me trouble:

Lemma 1 If the Nim-sum is $0$ after a player’s turn, then the next move must change it.

To prove this, let the number of stones in the heaps be $x_1, x_2, ... x_n$, and $s$ be the nim-sum $$s=x_1⊕x_2⊕x_3⊕ . . . ⊕x_n$$ Let $t$ be the sum of the heaps after the move, $$t=y_1⊕y_2⊕y_3⊕ . . . ⊕y_n$$ Then if $s= 0$, the next move causes some $x_k=y_k$ and the rest of the $x_i=y_i$ for $i \neq k$, since only one pile of stones is changed.

Then: $$t=0⊕t$$ $$=s⊕s⊕t$$ $$=s⊕(x_1⊕x_2⊕...⊕x_n)⊕(y_1⊕y_2⊕...⊕y_n)$$ $$=s⊕(x_1⊕y_1)⊕(x_2⊕y_2)⊕...⊕(x_k⊕y_k)$$ $$=s⊕x_k⊕y_k$$

If $s$ is 0, then $t$ must be nonzero, since $x_k⊕y_k$ will never be 0. Therefore, if you make the nim-sum $0$ on your turn, your opponent must make it nonzero.

I understand why $x_k ⊕ y_k$ can't be $0$, but why can't it be equal to $s$? This would make the nimsum $0$ still, and I don't see why this wouldn't be possible.

  • 3
    $\begingroup$ $s$ is the state before the move, and is assumed to be zero. So you are effectively asking: I understand $x_k⊕y_k$ can't be zero, but why can't it be equal to zero? $\endgroup$ – Jaap Scherphuis Jan 30 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.