The Mathematical Solution to the Game of Nim

While the history of Nim is confusing and convoluted, the game itself is fairly simple. You have four rows of 1, 3, 5, and 7 sticks and the ability to take any amount of sticks from any single row in any single move; the goal: make the other player make the last move.

While a player new or unfamiliar to Nim might mistake the simplicity of its rules for difficulty, the game is as simple as its premise. Nim isn’t difficult, as a matter of fact it is as simple as a thing can be. And despite its survival for a couple of millennium, the game isn’t even particularly interesting. Nim is what’s known as a solved game, meaning that there is an easily calculable way to win the game every single time, provided you go second. And while the game itself might not be too interesting the mathematical theory behind it is anything but.

Before I go over the specifics of the winning formula, lets go over some definitions, first: Nim-sum. Denoted by the symbol ⊕, Nim-sum is calculated by expressing the summands as either distinct powers of 2 or as the digit 1, cancelling out equal powers, and lastly adding the remaining numbers together. For example, 5 ⊕ 7

5 = 1 + 4 + 0
7 = 4 + 2 + 1
---------------
= 2    Both 4 and 1 are cancelled

… is 2. 3 ⊕ 4 ⊕ 5

3 = 1 + 2 + 0
4 = 4 + 0 + 0
5 = 4 + 1…