Question 1

What is Nim?

Accepted Answer

Nim is a mathematical strategy game where two players take turns removing objects from piles. The player who takes the last object wins (normal play) or loses (misère). Nim is completely solved using XOR of pile sizes — the player facing a position where all pile sizes XOR to zero is in a losing position.

Question 2

How do you always win at Nim?

Accepted Answer

Compute the XOR (nim-sum) of all pile sizes. If the result is 0 you are losing with best play. Otherwise find a pile to reduce so the resulting XOR equals 0. In misère Nim use the same strategy except at the endgame when only piles of size 1 remain — then aim to leave an odd number of them.

Question 3

What is Wythoff's Game?

Accepted Answer

Wythoff's Game uses two piles. A player may remove any number from one pile, or the same number from both piles simultaneously. The losing positions are pairs (floor(nφ), floor(nφ²)) where φ is the golden ratio — making this one of the most beautiful results in combinatorial game theory.

Question 4

What is Turning Turtles?

Accepted Answer

Turning Turtles is played with a row of H (heads) and T (tails) coins. On each turn a player flips one H coin to T, and may also flip any coins to its left. The Grundy value of a face-up coin at 1-indexed position i is i. XOR all face-up positions to find the winning strategy.

Question 5

What is Treblecross?

Accepted Answer

Treblecross is played on a 1D board where players alternate placing an X. The player who completes three consecutive X marks loses. The game reduces to Nim via Grundy values of open intervals between placed X marks.

Question 6

What is Lasker's Nim?

Accepted Answer

Lasker's Nim adds a split option to Classic Nim. Instead of taking stones from a pile, a player may split one pile into two non-empty piles of any sizes. The Grundy values follow a simple formula: G(n) = n if n is odd, n+1 if n is divisible by 4, and n-1 if n ≡ 2 mod 4.

Question 7

What is Ruler Nim?

Accepted Answer

In Ruler Nim a player may only take a number of stones that is a divisor of the current pile size. The Grundy value G(n) equals the 2-adic valuation of n — the largest power of 2 dividing n. So G(12) = 2, G(8) = 3, G(6) = 1.

Question 8

What is the Sprague-Grundy theorem?

Accepted Answer

Every finite impartial game is equivalent to a single Nim pile whose size is the Grundy number of that position. The Grundy number is the mex (minimum excludant) of the Grundy numbers of all positions reachable in one move. For combined games the Grundy number is the XOR of individual Grundy numbers.

Nim Games — Mathematical Strategy