Nim, and the nim-sum.

Note

Charles Bouton solved Nim in a 1901 paper in the Annals of Mathematics. Write every heap in binary and add the columns without carrying, which is XOR. That number is the nim-sum. If it is zero, the player about to move loses against perfect play. If it is anything else, they win.

Two facts make that true. Any move from a zero nim-sum changes exactly one heap, so at least one bit flips and the sum stops being zero. From a non-zero sum s, look at its highest set bit and pick a heap h with that bit set. Then h XOR s is smaller than h, so shrinking that heap to h XOR s is a legal move, and it brings the sum back to zero. The empty table has nim-sum zero, so the player who keeps handing over zeros takes the last match.

The 1 3 5 7 start has nim-sum 1 XOR 3 XOR 5 XOR 7 = 0. Whoever moves first there has already lost, so pressing the second button on that setup is a polite way of letting you win. When the opponent is handed a zero it cannot escape, and it takes a single match from the biggest heap to give you as many chances as possible to slip.

The last-match-loses version, called misère, needs only one change. Play exactly as before until your move would leave no heap bigger than one. At that point, leave an odd number of single matches instead of an even one. Bouton covered this too. For most other games, misère play is much harder, and that gap is a whole chapter of Conway's work.

The Sprague-Grundy theorem, from the 1930s, goes further. Every finite impartial game, where both players have the same moves, is equivalent under the normal rule to a single Nim heap. So the XOR on this page is the tool for adding up any such games played side by side. The "won positions you gave back" counter ticks every time you move from a non-zero sum to another non-zero sum.