Problem
COM-B1-M08-P024 Piles \(7,11,13\)
There are three piles of \(7\), \(11\), and \(13\) stones. In one move, a player may take any positive number of stones from one pile. The last move wins. Find a winning first move and prove that it is winning.
Compute \(7\oplus11\oplus13\).
In binary, \(7=0111\), \(11=1011\), and \(13=1101\). The nim-sum is \(0111\oplus1011\oplus1101=0001\). We need to reduce one pile so that the nim-sum becomes \(0\). For example, reduce \(13\) to \(12\), because \(7\oplus11\oplus12=0\). After that, if the opponent changes one pile, the nim-sum becomes nonzero. In the pile containing the highest set bit of this nim-sum, one can reduce the number so that the total nim-sum becomes \(0\) again. Repeating this, the first player always returns a zero nim-sum to the opponent and eventually takes the last stone.
Strong for Book 1, but useful as a bridge to more advanced combinatorics.