Sprague-Grundy sequence for the ruler game

Question

Consider the game "Ruler", which is defined as follows. We start with finitely many coins in a line. A move in this game consists of turning over any number of coins, but they must be consecutive, and the rightmost coin must be turned from heads to tails. Then the position in this game where a coin in the $n$th position is heads and all others are tails has Sprague-Grundy value given by

$$ g(n) = mex \{ 0, g(n-1) , g(n-1) \oplus g(n-2), \cdots, g(n-1) \oplus \cdots \oplus g(1) \} $$

From here, according to page I-31 of Ferguson's game theory notes, "it is easy to show" that $g(n)$ is the largest power of two dividing $n$.

Except it's not easy. But it's a nice fact and I'd like to be able to present a proof of it to my students.

Fair Game by Guy and Winning Ways, the two other sources I've seen this in, both state this without proof. It seems that it might be closely related to results about Gray codes - the partial sums $g(1), g(1) \oplus g(2), g(1) \oplus g(2) \oplus g(3), \cdots$ are a binary Gray code for the integers.

Answer 1

As in all combinatorial game theory problems, we want to use strong induction on $n$. So suppose we know it for $1, ..., n-1$, and let's prove it for $n$.

Write $n$ in the form $2^k(2x+1)$. Then the highest power of $2$ dividing $n-i$ for $i<2^k$ is the same as the highest power of $2$ dividing $i$, so it's pretty easy to see that by the time we hit $g(n-1)\oplus \cdots \oplus g(n-2^k+1)$ we have hit every nimber from $0$ to $2^k-1$ (by Gray codes, if you like).

Now we just have to show that the nimber $2^k$ never shows up in that mex. The key idea, I think, is that the order of the highest nonzero bit in the binary representation of $g(n-1)\oplus \cdots \oplus g(n-i)$ never decreases as $i$ increases. This is because of the fact that for any subsequence $g(a), g(a+1), ..., g(b)$ of the largest-power-of-two sequence, the largest value only occurs once (if it occurred twice, there would be a larger power of two halfway in between). Now we just notice that for $i=2^k$, we have $n-i = 2^k(2x+1)-2^k = 2^{k+1}x$, so $g(n-1)\oplus \cdots \oplus g(n-i) \ge 2^{k+1}$ for all $i$ greater than or equal to $2^k$.

Thus $2^k$ does not show up in the mex, while every smaller nimber does. The induction is done :)