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.