Normal play Nim with piles of 3, 5 and 7, where the player taking the last object wins. Who wins with correct play, list every winning first move, and state the rule that decides it.

Normal play Nim with piles of 3, 5 and 7, where the player taking the last object wins. Who wins with correct play, list every winning first move, and state the rule that decides it.

Approach: Compute the bitwise XOR of the pile sizes and use the standard characterisation of losing positions, then find every move that sends the XOR to zero.

The first player wins, and the three winning moves are 3 to 2, 5 to 4, or 7 to 6. The XOR of the piles is 3 xor 5 xor 7, which equals 1, and a position is losing for the player to move exactly when that XOR is zero. From a nonzero XOR some move reaches zero, and from zero every move leaves it nonzero, so the player facing zero is eventually left with nothing to take. The rule works because XOR is binary addition with no carry, so each bit is balanced independently. Here each pile can drop by 1, since 2 xor 5 xor 7, 3 xor 4 xor 7 and 3 xor 5 xor 6 all vanish. Taking the whole pile of 7 loses, since 3 xor 5 leaves 6, which is nonzero.

Follow-up: In misere Nim with the same piles 3, 5 and 7, which first moves win?

Key concepts: nim sum, xor, losing position, binary carry.