Complete derivation for perfect play for Nim?

Question

Does anybody have a proper derivation for Nim? I don't want to see just Nim sums,binary conversions but also why we use those Nim sums and binary conversions,etc. Basically, teach it to me like i'm five. I'm a high school student who is doing this topic for my extended essay, and i dont have much knowledge of combinatorial game theory.(i can draw simple game trees and im reasonably familiar with surreal nos, im reading through On Numbers and Games right now, but again, i feel like some things are being left unexplained, such as why we have to convert hackenbush diagrams to binary code to get the values of the Games.) So the more basic you go, the better. Thank you.

Answer 1

I don't know how much clearer this will be than the proof on Wikipedia. But I've tried to minimize notation by sacrificing conciseness.

Setup

For Nim, I'll refer to "heaps of tokens" (rather than "rows of cards", etc.). A Nim "position" is just a particular setup, like "2 heaps of 5 tokens and 1 heap of 7 tokens".

Firstly, for those who are not already familiar with the strategy for Nim, I highly recommend this youtube video by Mathologer (Burkard Polster). To keep things simple, I'll focus only on normal play, where the player who takes the last token wins.

Balanced positions

We call a Nim position "balanced" if when you separate the heaps into distinct powers of $2$ (e.g. $13 = 8+4+1$), there are even numbers of each power of $2$.

For example, the position with heaps of sizes $3,5,7,8,9$ is balanced because "$1+2,1+4,1+2+4,8,1+8$" shows four $1$s, two $2$s, two $4$s, and two $8$s. $3,3,4,4=1+2,1+2,4,4$ is also balanced because there are two $1$s, two $2$s, and two $4$s. As a special case, the endgame position with no tokens is also balanced, since something like $0,0,0,0,0$ has zero powers of $2$, and zero is even.

$3,5,7$ is not balanced since there are three $1$s in $1+2,1+4,1+2+4$, and three is odd. $9$ is another unbalanced position since it has only one $8$.

Balanced positions can only become unbalanced

I claim that if you make a move (remove $1$ or more tokens from a single heap) in a balanced position, then you necessarily make it unbalanced.

Suppose we have a balanced position, and move in some heap to get a new number of tokens. If all the powers of $2$ in that heap were left exactly the same, it would be the same number, so some power of $2$ must change (either a new one we didn't have, or we lose an old one, or both). For example, moving from $7=1+2+4$ to $4$ loses both $1$ and $2$. Moving from $9=1+8$ to $7=1+2+4$ loses $8$ but gains $1$, etc.

But whatever change we make to the powers of $2$ in a single heap will unbalance things. For example, if we gain a $4$, then we're adding one to the even number of $4$s we had in the balanced position, and that makes the number of $4$s odd. If we lose a $2$, then we're subtracting one from the even number of $2$s we had in the balanced position, and that would make the number of $2$s odd. This doesn't depend on which power(s) of $2$ we gain or lose, since we can't gain or lose more than one of the same power of $2$ (e.g. $4+4$ would be written as $8$).

Unbalanced positions can be balanced

I claim that if the current position is unbalanced, then there is a move that balances it. Note that since it's unbalanced, there is an odd number of at least one power of $2$.

So suppose for example that $8$ is the largest power of $2$ with an odd amount (so there are an even number of $16$s, $32$s, etc.). Since there are an odd number of $8$s, there is at least one heap with an $8$ in it. For example, in the position $1,9,16,16$, the heap of size $9=1+8$ has an $8$. I claim that we can balance the position by removing tokens from any heap with an $8$ in it.

We could balance the position if we could "magically" replace the heap with one that removes the $8$, and add/removes lower powers as needed (remember, everything above $8$ already has an even amount).

[For example, if all the powers of $2$ that have an odd amount are $1$ and $2$ and $8$. Then we could balance the position if we could "magically" replace the heap with one that removes the $8$, and adds/removes the $1$ and the $2$ as needed. If our heap had $25=1+8+16$, then we could balance the position by leaving $18=2+16$ (which we can do by removing $7$).]

By removing the right amount, we can always do the above "magical" replacement when the desired new heap size is less than the original one. And the desired heap size can't be the same as the old one since the $8$s make the position unbalanced. But we'd have a problem if the desired size were more than the old one. In the worst case (with the highest possible desired size) we'd remove $8$, but need to add $1$ and $2$ and $4$, which sum to $7=8-1$, so the desired size is at most $1$ less than the starting one, and we can always get there by removing tokens from this heap.

The argument above doesn't depend on the number $8$: $1+2=4-1$, $1+2+4+8=16-1$, etc. So we really can always balance an unbalanced position by removing the right amount of tokens from a heap with the largest odd-amount power of $2$.

Conclusion

Since players only remove tokens, the total number of tokens will eventually go down to zero. Since the endgame position is balanced, if the starting position is unbalanced, the first player can win by repeatedly making balancing moves (the opponent has no choice but to keep unbalancing).

Gap

I didn't prove above that it's always possible to write a nonnegative integer as a sum of distinct powers of $2$, but since the OP mentioned "binary conversions", I assumed that wasn't my responsibility. That's also addressed here.