Nim where the last stone loses

Question

Three piles hold 3, 4 and 5 stones. On a turn a player removes any positive number of stones from one pile. In ordinary Nim the player who takes the last stone wins. In this misère version, the player who takes the last stone loses. Who wins from 3, 4, 5 with best play, and what is the winning first move? How does the misère strategy differ from the ordinary one?

Accepted Answer

The first player wins by taking 2 stones from the pile of 3, leaving 1, 4, 5. The misère strategy is identical to ordinary Nim except in the endgame where every pile has at most one stone. Ordinary Nim in one line. Write the pile sizes in binary and take the exclusive-or (XOR) of all of them. A position is losing for the player to move exactly when the XOR is zero. For 3, 4, 5: 011 XOR 100 XOR 101 = 010, which is 2, not zero, so the first player is winning and should move to a zero-XOR position. Changing the 3 to 4 XOR 5 = 1 does it: take 2 from the pile of 3, leaving 1, 4, 5 (XOR 001 XOR 100…

Nim where the last stone loses

Your answer

Discussion

Learn the concepts

Related questions