Consider the following variant of the Nim game (source: HDU-5795):
Two players take turns picking candies from $n$ heaps, the player who picks the last one will win the game. On each turn they can pick any number of candies which come from the same heap (picking no candy is not allowed). To make the game more interesting, players can separate one heap into three smaller heaps (no empty heaps) instead of the picking operation. Please find out which player will win the game if each of them never make mistakes.
One quickly realises that this problem amounts to calculating the following function $f$, the Sprague–Grundy function for a pile of $x$ candies:
Define $f : \mathbb N \rightarrow \mathbb N$ recursively: $f(0) = 0$,
$$
f(x) = \text{mex} \{ f(0), …, f(x - 1) \} \cup \{ f(a) \oplus f(b) \oplus f(c) | a + b + c = x \text{ and } a, b, c \ge 1 \}.
$$
By calculating $f$ for some small values of $x$, one discovers the following pattern:
$$
f(x) = \cases{ x + 1, \quad \text{if } x \equiv 7 \pmod{8}, \\
x - 1, \quad \text{if } x \equiv 0 \pmod{8} \text{ and } x \ge 8, \\
x, \quad \text{otherwise}.}
$$
Now let’s prove (why not?) this formula by induction. Assume that the value of $f$ has been established for $0, …, x- 1$. Now let’s consider $f(x)$.
Case 1
$x \not \equiv 0 \pmod 8$. In this case $\{f(0),… f(x-1)\} = \{0, …, x- 1\}$.
We need the following lemma:
$$
y_1 \oplus y_2 \oplus y_3 = y_1 + y_2 + y_3 - \sum_i 2^{i + 1} \left\lfloor \frac{t_i}2 \right\rfloor
$$
where $t_i$ represents the total occurrences of $1$’s at the $i$-th binary bit in $y_1, y_2, y_3$ (the lowest bit indexed as $0$). This simply formalises the idea that “XOR is the binary addition without carry”. The subtracted part $\sum_i 2^{i + 1} \left\lfloor \frac{t_i}2 \right\rfloor$ is the sum of carry of all binary bits.
Now let’s suppose we have $f(a) \oplus f(b) \oplus f(c) = x$ for some $a + b + c = x \text{ and } a, b, c \ge 1$. By the above lemma, this is equivalent to
$$
f(a) + f(b) + f(c) - \sum_i 2^{i + 1} \left\lfloor \frac{t_i}2 \right\rfloor = x
$$
Now notice that the carry $\sum_i 2^{i + 1} \left\lfloor \frac{t_i}2 \right\rfloor$ part (later referred to as the carry) is always an even number and that $f(a) \le a+1$ (and the same for $b, c$).
Suppose that the carry is $2$ and that $f(a) = a+1$, $f(b) = b+1$ and $f(c) = c$. But this can not happen, because in this case $f(a), f(b) \equiv 0 \pmod 8$ and the occurrence of $1$ on the lowest bit can be at most $1$ (if $c$ is odd) and thus can not contribute to the carry.
So the carry must be $0$ and that $f(a) + f(b) + f(c) = x$. Then we have two possibilities:
- $f(a) = a, f(b) = b, f(c) = c$. Then we must make sure that for each binary bit, there can be at most one $1$ in $a, b, c$. On the other hand, $a, b, c \not \equiv 0 \pmod 8$ (since otherwise their $f$ value would be one less than themselves), so they must each occupy one bit for the three lowest bits. Then we must have $x \equiv 7 \pmod 8$. Further, in this case, a solution would always exist; one may simply take $a = 1$, $b = 2$ and $c = x - 3$.
- $f(a) = a + 1, f(b) = b- 1, f(c) = c$. But then $b - 1 \equiv 7 \pmod 8$ and $c \not \equiv 0 \pmod 8$, so the carry cannot be $0$.
Therefore we have shown that we can only have $f(a) \oplus f(b) \oplus f(c) = x$ when $x \equiv 7 \pmod 8$. So for $x \equiv 1, 2,3,4,5,6 \pmod 8$, we see that $f(x) = x$ by the definition of $\text{mex}$.
The next task is to show that we cannot have $f(a) \oplus f(b) \oplus f(c) = x + 1$ when $x \equiv 7 \pmod 8$. Using similar logic as above, the carry cannot be $2$ and must be $0$, in other words $f(a) + f(b) + f(c) = x + 1$.
Then again we have two possibilities:
- $f(a) = a + 1, f(b) = b, f(c) = c$. Then $a \equiv 7 \pmod 8$, so $b + c = x - a \equiv 0 \pmod 8$. But we cannot have the carry, so $b, c \equiv 0 \pmod 8$. This means that $f(b) = b - 1$ which leads to a contradiction.
- $f(a) = a + 1, f(b) = b + 1, f(c) = c - 1$. Then $a, b \equiv 7 \pmod 8$ and $c \equiv 0 \pmod 8$, which means $x = a + b + c \equiv 6 \pmod 8$, another contradiction.
Therefore $f(x) = x + 1$ for $x \equiv 7 \pmod 8$.
Case 2
Now we consider the case $x \equiv 0 \pmod 8$ and $x \ge 8$. In this case $\{f(0),… f(x-1)\} = \{0, …, x-2, x\}$.
Suppose that $f(a) \oplus f(b) \oplus f(c) = x - 1$ for some $a + b + c = x \text{ and } a, b, c \ge 1$.
Again the carry cannot be $2$ and must be $0$. We then consider the two cases $f(a) = a - 1, f(b) = b, f(c) = c$ and $f(a) = a - 1, f(b) = b-1, f(c)= c+1$, and one can quickly realise that they are both not possible.
Therefore $f(x) = x - 1$ for $x \equiv 0 \pmod 8$.
We have thus finished the proof.
Generalisation
Can we have a generalised formula for the following $f_n$, where we have previously considered $n = 3$?
For $n \ge 2$, define $f_n : \mathbb N \rightarrow \mathbb N$ recursively: $f_n(0) = 0$,
$$
f_n(x) = \text{mex} \{ f_n(0), …, f_n(x - 1) \} \cup \{ f_n(a_1) \oplus … \oplus f_n(a_n) | \sum_{i=1}^n a_i = x \text{ and } a_i \ge 1 \}.
$$
For $n = 2$, a similar pattern arises as in $n = 3$.
A calculation for $n = 4$ reveals that the pattern seems non-trivial.
| $f_4 (x) - x$ | all such $x \le 100$ |
|---|---|
| 0 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 39, 75, |
| 1 | 15, 31, 32, 33, 34, 35, 36, 37, 40, 41, |
| 2 | 38, 42, 43, 44, 48, |
| 3 | 45, 46, 49, 50, 51, |
| 4 | 52, 53, 54, 55, 56, 57, 58, 67, |
| 5 | 59, 60, 61, 62, 63, 64, 65, 68, 69, |
| 6 | 66, 70, 71, 72, 76, |
| 7 | 73, 74, 77, 78, 79, |
| 8 | 80, 81, 82, 83, 84, 85, 86, 95, |
| 9 | 87, 88, 89, 90, 91, 92, 93, 96, 97, |
| 10 | 94, 98, 99, 100, |
Looks rather chaotic… So let me leave the question here for the curious reader.