I have been researching this variant of Nim. I have been unable to prove the following claim. What is annoying is that I feel I am missing something really obvious. Does anyone have any ideas on how to solve this:
Let's first say that one position dominates another if all its corresponding pile sizes are at least as great. Note that the positions must be distinct. For example, $(1,2,4)$ dominates $(0,1,4)$ whereas $(5,8,7)$ does not dominate $(4,2,8)$.
Here is the actual problem. Let $m$ be a positive odd integer and $\oplus$ denote the bitwise xor. Let $a,b,c$ be non-negative integers with the following conditions:
- $a \oplus b \geq m$
- $0 < a < \frac{m}{2} \leq b < m \leq c$
Show that for all integers $0 \leq i < m$, there exists a position $(a^\prime,b^\prime,c^\prime)$ dominated by $(a,b,c)$ such that:
- $a^\prime + b^\prime + c^\prime = 2i$
- $a^\prime \oplus b^\prime \oplus c^\prime = 0$
Choose $c'=a'+b'=a'\oplus b'=i$. Then at each position, exactly $0$ or $1$ bits are set in $a'$ and $b'$ depending on whether the corresponding bit in $i$ is set. It remains to be decided how to distribute the set bits in $i$ over $a'$ and $b'$. Obtain $a',b'$ from $a,b$ as follows: Clear all bits that are cleared in $i$. Since $a\oplus b\ge m\gt i$, the most significant bit change from $a\oplus b$ to $i$ is $1\to0$, and that bit was set and gets cleared in one of $a'$ and $b'$, say, $a'$. Change all bits in $a'$ that are set in $i$ but not in $a\oplus b$.
Since the most significant changed bit is worth more than all less significant changes added together, we have $a'\le a$ and $b'\le b$, and also $c'=i\lt m\lt c$, so $(a',b',c')$ thus constructed is dominated by $(a,b,c)$. Note that $a\lt\frac m2\le b\lt m$ hasn't been used.