Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

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 :)

share|improve this answer
    
Thanks. I basically came up with this proof on the way home but it's good to see some independent confirmation of it. –  Michael Lugo Sep 18 '10 at 2:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.