Nim With Three Piles
The puzzle
Three piles hold 3, 5 and 7 counters. Players alternate; a move is to take any number of counters, at least one, from a single pile. Whoever takes the last counter wins.
Who wins, and what is the first move?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Write the pile sizes in binary and add each column without carrying - that is, XOR them.
Hint 2
3 = 011, 5 = 101, 7 = 111. Column by column, mod 2: 001. Not zero, so the player to move can win.
Show the answer Hide the answer
The first player wins. Take one counter from the pile of 7, leaving 3, 5 and 6 - whose nim-sum is zero.
How to get there
Compute the nim-sum: XOR the pile sizes. 3 XOR 5 = 6, and 6 XOR 7 = 1. It is non-zero, which means the position is a win for the player about to move.
A winning move makes the nim-sum zero. Note that 3 XOR 5 = 6, so changing the third pile from 7 to 6 leaves 3 XOR 5 XOR 6 = 0. Taking one counter from the seven does exactly that.
Why zero is losing: from a zero position every move changes exactly one pile, and changing one pile must change the nim-sum away from zero - so the opponent always hands you a non-zero position, and you hand back a zero one. The game strictly shrinks, so it ends, and it ends on the player facing 0, 0, 0 - a nim-sum of zero with nothing to take. That is Bouton's theorem, and it makes Nim one of the few games solved completely.
The technique worth keeping
Look for a quantity that is zero exactly at the losing positions and that every move must disturb. If you can always restore it and your opponent never can, you have a complete strategy rather than a heuristic.