Another Cousin of Nim

  1. Two players have twenty checkers on the table. Each has his turn and removes one, two or three checkers but is forbidden to take the same number of checkers previously removed by his opponent. The player who takes the last checker or prevents his opponent from playing is the winner. Your opponent begins by removing 3 checkers. Who will be the winner?
  2. Fifty checkers on the table and you begin. What is your best strategy ?
[And of course the inevitable extension - what is the best strategy for starting with N checkers on the table? What are the losing positions? -KD]

Source: Le Monde 22/09/98 - Elisabeth Busser and Gilles Cohen. Submitted by Philippe Fondanaiche.

Solutions were received from several people: Joel Haywood, Larry Baum, David Toelkes, Igor Volkov, Philippe Fondanaiche.

In general, you can win as long as the current pile does not have a multiple of 4 checkers. Your best strategy at any point is to remove a number of checkers to return the pile to a multiple of 4. If your opponent previously removed 2 checkers, you can instead remove 1 checker, and on your next move, you will be able to return the pile to 4k checkers. For the endgame, this same technique will either have you taking the last checker or leaving your opponent with no move to make, both winning states.

So for the above games, your opponent will lose in each case. In the first, you should play by removing a single checker to leave a pile of 16. In the second, remove 2, to leave 48.

Some readers read the problem as each player had their own separate pile of checkers. They correctly observed that the first player could always win by repeatedly taking 3 checkers from their own pile, thereby reaching the end of their pile sooner. The endgame is to reach 3 checkers, and either take all 3 or remove them one at a time.
Mail to Ken