Two cats, Bill and Tom, play the following game. They, in turn (Bill starts), eat fishes from the heap of 50 fishes. Per move it is allowed to eat exactly 1, or exactly 4, or exactly 7 fishes. The player wins if he eats the last fish of the heap.
Who of the cats wins if both of them play to win?
Solution
It is easy to see that if either or fishes remain in the heap, then the player who must move wins, but if fishes remain, then this player loses. So we will solve the problem moving backward. We write all numbers from to and mark them with "+" or "-". If fishes remain in the heap before the move of a player and he can win, then we write , otherwise we write . We have the following table
| +1 | -2 | +3 | +4 | -5 | +6 | +7 | -8 | +9 | -10 | +11 | +12 | -13 | +14 | +15 | -16 | ... |
|----|----|----|----|----|----|----|----|----|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | - | 1 | 4 | - | 4 | 7 | - | 1 | - | 1 | 4 | - | 4 | 7 | - | ... |
The second row of the table contains the possible winning moves (to win the player can eat so many fishes that after his move the number of the fishes remained in the heap would be marked with "+" ). We see that the signs in the first row of the table are repeated with the period equaled (it is easy to prove by induction).
Since leaves remainder when divided by , it follows that and are marked with the same sign, i.e. "-". Thus the number is the losing number of the fishes for the beginning player. To win Tom can eat so many fishes as it is written in the second row of the table.
Looking for a route rather than an archive? The track puts 2,000
problems in a working order, from AMC 10 level to the IMO shortlist.