Moves to P-positions in Nim

Question

Let $A$ be an N-position in Nim such that all moves to P-positions reqire exactly $k$ tokens to be removed. What can we say about $A$?

Answer 1

As you may know, a winning move is one that changes the ginary XOR of theheap sizes to $0$, which means to XOR one of the existing heap sizes with the current XOR sum $s$. By assumption, for each heap size $n_i$ in $A$, we have either $n_i\operatorname{XOR} s>n_i$ or $n_i\operatorname{XOR} s=n_i-k$. The first case occurs exactly when $n_i$ has a zero bit at the msb bit of $s$. As $x\operatorname{XOR}y=x-y+2(x\operatorname{AND}y)$, we conclude that all $n_i$ with a $1$ the msb bit of $s$ (which must be an odd number of heaps) have the same AND with $s$,i.e., they agree at all bit positions occuring in $s$. And vice versa, from any odd number of heaps having a few bits in common in this way, we can construct an $N$-position by adding one or more heaps of suitable size.