Lasker Nim, Sprague-Grundy Function Proof

Question

It's been stated that the Sprague-Grundy function of Leskar's Nim is as follows:

$g (4k + 1) = 4k + 1\\ g (4k + 2) = 4k + 2\\ g (4k + 3) = 4k + 4\\ g (4k + 4) = 4k + 3$

The strategy to prove this claim is by induction, however I'm rather confused on how some claims are used in the proof of my textbook without much explination.

For the first form:

the followers of $4k + 1$ that have a single pile have Sprague-Grundy values from $0$ to $4k$. Those that have two piles, $(4k, 1), (4k −1,2), . . . , (2k + 1, 2k)$, have even Sprague-Grundy values, and therefore $g(4k + 1) = 4k + 1$.

I understand the values for moves that result in a single pile, but for moves that result in two piles, how do we know that the value of the function is even? We would have to know something about whether the the function evaulated at each of those two piles are both even or both odd, that makes the nim-sum even. But we don't know much about that.

Similar claims are given for the other proofs such as making claims on whether the function is odd or divisible by 4

How can we go by doing this?

Answer 1

Suppose that the result is true for all $n<4k+1$; that’s the induction hypothesis. If we split $4k+1$ into two piles, the possibilities are of the forms $\langle 4\ell,4m+1\rangle$, $\langle 4\ell+1,4m\rangle$, $\langle 4\ell+2,4m+3\rangle$, and $\langle 4\ell+3,4m+2\rangle$, where $\ell+m=k$ in the first two, and $\ell+m=k-1$ in the last two. In each case both piles have fewer than $4k+1$ chips, so we can apply the induction hypothesis.

• $\langle 4\ell,4m+1\rangle$: $g(4\ell)=g(4(\ell-1)+4)=4(\ell-1)+3$, and $g(4m+1)=4m+1$; both numbers are odd, so their Nim sum is even.
• $\langle 4\ell+1,4m\rangle$: This is the same, but with the piles reversed.
• $\langle 4\ell+2,4m+3\rangle$: $g(4\ell+2)=4\ell+2$, and $g(4m+3)=4m+4$; both numbers are even, so their Nim sum is even.
• $\langle 4\ell+3,4m+2\rangle$: This is the same, but with the piles reversed.

Thus, every two-pile follower of $4k+1$ has an even Sprague-Grundy value. These values are at most $4k$, so $g(4k+1)=4k+1$.

The arguments for $4k+2,4k+3$, and $4k+4$ are similar. For $4k+2$, for instance, the possible divisions into two piles are of the forms $\langle 4\ell,4m+2\rangle$ and the same with the piles reversed, $\langle 4\ell+1,4m+1\rangle$, and $\langle 4\ell+3,4m+3\rangle$.

• $\langle 4\ell,4m+2\rangle$: $g(4\ell)=g(4(\ell-1)+4)=4(\ell-1)+3$, and $g(4m+2)=4m+2$; the first is odd and the second, even, so their Nim sum is odd.
• $\langle 4\ell+1,4m+1\rangle$: $g(4\ell+1)=4\ell+1$, and $g(4m+1)=4m+1$; both have binary expansions ending in $01$, so their Nim sum has a binary expansion ending in $00$ and is therefore a multiple of $4$.
• $\langle 4\ell+3,4m+3\rangle$: $g(4\ell+3)=4\ell+4$, and $g(4m+3)=4m+4$; both are multiples of $4$, so their binary expansions end in $00$, and so does the binary expansion of their Nim sum, which is therefore a multiple of $4$.

Thus, every two-pile follower of $4k+2$ has a Sprague-Grundy value that is either odd or a multiple of $4$ and therefore is at most $4k+1$, so that $g(4k+2)=4k+2$.