Why is the winning strategy for Nim and other impartial games unique?

Question

Wikipedia says that "both mex and XOR yield a winning strategy for Nim and there can be only one such strategy". Why can there be only one unique winning strategy for Nim and impartial games in general? Why can't there be two or more distinct winning strategies?

Answer 1

Here is what I think that (rather unclear) statement is intended to mean. Consider a three-pile Nim game in a position $(a,b,c)$. I claim that there is at most one winning move you can make by taking from the third pile. Indeed, suppose there are two such moves, so there exist $d<e<c$ such that moving to $(a,b,d)$ and moving to $(a,b,e)$ are both winning moves. But now note that after moving to $(a,b,e)$, your opponent can win by moving to $(a,b,d)$, which is a contradiction since you were supposed to win after moving to $(a,b,e)$.

Now let $a\oplus b$ be the Nim-sum of $a$ and $b$ defined using the mex rule and let $a\oplus' b$ be the Nim-sum of $a$ and $b$ defined using bitwise xor. Let $c>\max(a\oplus b,a\oplus' b)$ and consider the Nim position $(a,b,c)$. You can prove that $(a,b,a\oplus b)$ and $(a,b,a\oplus' b)$ are both winning moves. (Or, really, you can prove that there is a winning strategy for 3-pile Nim given by always moving to positions where one pile is the $\oplus$-sum of the other two, and similarly for $\oplus'$.) By the discussion in the previous paragraph, this implies that $a\oplus b=a\oplus' b$.

(Note, though, that this does not mean the winning strategy for Nim is unique--only that there is at most one winning move in any fixed pile. There may be winning moves in multiple different piles. For instance, as Mark S. pointed out in the comments, the position $(1,3,3)$ has a winning move in each of the three piles.)