In the 1901 paper that named the game Nim and provided its mathematical analysis, Charles Bouton defined “safe combinations”, positions that if you leave the game in this state, your opponent cannot win. In combinatorial game theory, these are \(\mathcal{P}\) positions (the previous player has already won), as opposed to \(\mathcal{N}\) positions (the next player can win).
Bouton gives a list of “the 35 safe combinations all of whose piles are less than 16”, working in three-heap Nim. Naturally it seemed sensible to check these, so I wrote a bit of Python code to do this. Bouton’s list is good. I realised I could easily adapt my code to find out how many \(\mathcal{P}\) positions there are for three-heap Nim games with other maximum heap sizes: 1, 2, 3, and so on.
And, having generated a sequence of integers, I naturally looked to see if it was in the OEIS. This is sometimes a good way to discover that your sequence of numbers is also found in some unexpected places. It wasn’t there! So I submitted it, and I just got the exciting email “N. J. A. Sloane published your changes”. So I present A363166: “Bouton numbers: a(n) is the number of P positions in games of Nim with three nonzero heaps each containing at most n sticks”.
This is my first OEIS submission, so it’s all very pleasing, even if I’m submitting a ‘new’ sequence inspired by a 1901 paper!
Just looking at the sequence up to n=256, and it appears that a(2^k)=a(2^k-1) for k in 1-8 (i.e. a(32)=a(31)=155). Is there any general reason why this should be true?
In fact, just scanning the list, the only n’s where a(n-1)=a(n) are when n is of the form 2^k
Hi Andy,
Good spot! Yes it’s entirely natural that this is the case.
Nim analysis is based on Nim sum – bitwise XOR addition of the binary representations of heap sizes. A \(\mathcal{P}\) position is one where the Nim sum is zero.
Now in the situation where we increase the maximum heap size to \(2^k\), we have three heaps that can now have a bit in a new binary place, the \(2^k\) place. This heap size in binary will be \(10\dots 0\) since it can’t be larger than \(2^k\).
If one heap alone has \(2^k\) sticks, the Nim sum cannot be zero because that 1 bit stands alone. In the case where all three heaps have \(2^k\) sticks the Nim sum can’t be zero because the XOR addition of 1, 1 and 1 is 1 not 0. This leaves the case where two heaps are \(2^k\) and the other is not – then, the two heaps that are will Nim sum to zero, meaning the overall Nim sum is equal to the size in binary of the third heap. This cannot be zero since we insist on nonzero heap sizes, so this cannot be a \(\mathcal{P}\) position either.
Therefore an increase to \(2^k\) sticks as the maximum size can never produce more \(\mathcal{P}\) positions than the \(2^{k-1}\) case.
Hope that made sense!
Thanks Peter, that is very nice.
I have found a formula for this sequence. Put $n = 2^k + m $ where $ k $ is maximal and $ 0 \leq m<2^k $. Then the number of P positions is
\[\binom{m+1}{2}+\frac{\binom{2^k-1}{2}}{3}\]
which is
\[\frac{m(m+1)}{2}+\frac{(2^k-1)(2^k-2)}{6}\]
In any P position the largest two numbers must be the same length when written in binary, since the leading bits must xor to zero. The first term covers the case where the largest two numbers have the same length as $n$ and so are in $2^k…2^k+m$. We can choose any pair and then set the third number to their nim sum, which is necessarily shorter.
The second term covers the other case where all the numbers are shorter than $n$. We choose any pair of numbers in the range $1…2^k-1$ together with their nim sum. Each P position will occur three times; hence we must divide the number of choices by 3.
I think this method will generalise to more heaps.
This made me wonder about limiting the total number of sticks, rather than limiting each heap. Fix the total number of sticks to be exactly $n$. Let $h$ be the Hamming weight of $n$, that is, the number of 1-bits when $n$ is written in binary. When $n$ is odd the number of P positions is zero. When $n$ is even it is \[\frac{3^{h-1}-1}{2}\].