Solution
Nim with Two Piles at Once
Show the problem again
Four piles of stones contain 5, 8, 11 and 13 stones. Two players alternate. On each turn a player chooses one or two piles and removes at least one stone from each chosen pile (the amounts may differ). The player who takes the last stone wins. The first player has exactly one winning first move. After that move, how many stones are left in total? Give an integer.
Worked solution
The answer is 33. This is Moore's Nim with k = 2. A position is losing for the player to move exactly when, for every binary digit position, the number of piles having a 1 there is divisible by k + 1 = 3 (not by 2, as in ordinary Nim). For 5 = 0101, 8 = 1000, 11 = 1011 and 13 = 1101, the column counts of ones, from the 8s place down to the 1s place, are as follows: the 8s column has 8, 11, 13 (count 3), the 4s column has 5, 13 (count 2), the 2s column has 11 (count 1), the 1s column has 5, 11, 13 (count 3). The 4s and 2s columns are not divisible by 3, so the position is not losing. One two-pile move can repair both columns: reduce 5 (0101) to 3 (0011) and 13 (1101) to 11 (1011). The piles become 3, 8, 11, 11 with column counts 3, 0, 3, 3 (8s, 4s, 2s, 1s), all divisible by 3. Exhaustive search of the game shows this is the only winning move. The position then holds 3 + 8 + 11 + 11 = 33 stones.
Source: E. H. Moore's generalization of Nim (1910). Statement written for AxiomIQ.