Another Cousin of Nim
-
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?
-
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