Solution
Nim Where You May Split a Pile
Show the problem again
Four piles contain 7, 10, 12 and 13 stones. Two players alternate; a move is either (a) to remove any positive number of stones from one pile, or (b) to split one pile into two non-empty piles without removing any stones. The player who cannot move loses. The first player has exactly one winning first move, and it is of type (a). How many stones does it remove? Give an integer.
Worked solution
The answer is 4. Lasker's Nim has Grundy values g(4k+1) = 4k+1, g(4k+2) = 4k+2, g(4k+3) = 4k+4, g(4k+4) = 4k+3, so g(1..) = 1, 2, 4, 3, 5, 6, 8, 7, 9, 10, 12, 11, 13, ... (checked by direct computation). The piles 7, 10, 12, 13 have values 8, 10, 11, 13, whose XOR is 8 ⊕ 10 ⊕ 11 ⊕ 13 = 4. The first player wins by making a pile's value change by 4: the target value for the 13-pile is 13 ⊕ 4 = 9, the value of a pile of 9, reachable from 13 by removing 4 stones. A full search of the game confirms that this is the only winning move (no splitting move or other removal works). So 4 stones are removed.
Source: Lasker's Nim (Emanuel Lasker, 1931), analysed in Winning Ways. Statement written for AxiomIQ.