TAOCP 7.1.3 Exercise 9

We prove that a position $(a_1,\ldots,a_k)$ is losing for the player to move if and only if a_1 \oplus \cdots \oplus a_k = 0.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 9. [M26] (Nim.) Two people play a game with $k$ piles of sticks, where there are $a_j$ sticks in pile $j$. If $a_1 = \cdots = a_k = 0$ when it is a player's turn to move, that player loses; otherwise the player reduces one of the piles by any desired amount, throwing away the removed sticks, and it is the other player's turn. Prove that the player to move can force a victory if and only if $a_1 \oplus \cdots \oplus a_k \ne 0$. [Hint: Use exercise 8.]

Verified: yes
Solve time: 4m46s

We prove that a position $(a_1,\ldots,a_k)$ is losing for the player to move if and only if

$$ a_1 \oplus \cdots \oplus a_k = 0. $$

Equivalently, we prove by induction that the Sprague–Grundy value equals the XOR of heap sizes.

Let

$$ x = a_1 \oplus \cdots \oplus a_k. $$

Step 1. Terminal position

If all $a_j=0$, then there are no moves, so

$$ g(0,\ldots,0)=\mathrm{mex}(\varnothing)=0, $$

and also $x=0$. The claim holds.

Step 2. Induction hypothesis

Assume that for all positions with smaller total heap size, the Grundy value equals the XOR.

Fix a position $A=(a_1,\ldots,a_k)$ and let $x$ be its XOR. We show that for every integer $y<x$, there exists a legal move from $A$ to a position whose XOR equals $y$. This implies that the set of reachable Grundy values contains all integers $<x$, and does not contain $x$, hence $\mathrm{mex}=x$.

Step 3. The value $x$ is not reachable

Suppose a move changes heap $j$ from $a_j$ to $b<a_j$. Let the new XOR be $x'$. Then

$$ x' = x \oplus a_j \oplus b. $$

If $x'=x$, then $a_j=b$, contradicting $b<a_j$. Hence $x$ is not reachable.

Step 4. Constructing a move for any $y<x$

Let $y<x$ and define

$$ d = x \oplus y. $$

Then $d \neq 0$, and let $m$ be the highest bit where $d$ has a 1. Thus

$$ 2^m \le d < 2^{m+1}, $$

and $d_m=1$, while all bits above $m$ are zero.

We will modify a single heap to achieve XOR equal to $y$.

Define the target heap value

$$ b = a_j \oplus d = a_j \oplus x \oplus y. $$

We must choose $j$ so that $b < a_j$.

Existence of a suitable heap $j$

We claim there exists $j$ such that the $m$-th bit of $a_j$ is $1$.

Indeed, since $m$ is the highest bit of $d=x\oplus y$, we have that the $m$-th bit of $x$ and $y$ differ. Because $y<x$, the highest bit where they differ is exactly where $x$ has a 1 and $y$ has a 0. Hence $x_m=1$.

But

$$ x = a_1 \oplus \cdots \oplus a_k, $$

so the $m$-th bit of $x$ is the XOR of the $m$-th bits of the $a_j$. Since this XOR equals $1$, there must exist at least one index $j$ such that $a_{j,m}=1$.

Fix such a $j$.

Let

$$ b = a_j \oplus d. $$

  • For all bits above $m$: since $d$ has no 1s above position $m$, $a_j$ and $b$ agree in all higher bits.
  • At bit $m$: $a_{j,m}=1$ and $d_m=1$, so $b_m=0$.

Thus the highest bit where $a_j$ and $b$ differ is $m$, where $a_j$ has 1 and $b$ has 0. Therefore,

$$ b < a_j. $$

So this is a valid move.

Resulting XOR

After replacing $a_j$ by $b$, the new XOR is

$$ x \oplus a_j \oplus b = x \oplus a_j \oplus (a_j \oplus d) = x \oplus d = x \oplus (x \oplus y) = y. $$

Hence every $y<x$ is reachable.

Step 5. Conclusion

The set of XOR-values of options contains all integers $<x$ and does not contain $x$, so

$$ \mathrm{mex} = x. $$

Thus the Sprague–Grundy value of the position is

$$ g(a_1,\ldots,a_k)=a_1\oplus\cdots\oplus a_k. $$

A position is losing exactly when this XOR is zero, completing the proof. ∎