Integers from to are written on a blackboard. Tom and Jerry play the following game. They, in turn (Tom is the first), erase these numbers. Per move it is allowed to erase exactly , or exactly , or exactly numbers. The player wins if he erases the last number.
Who wins if both of the players play to win?
Solution
It is easy to see that if either or numbers remain on the blackboard, then the player who must move wins, but if or numbers 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 numbers remain on the blackboard 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 |
|----|----|----|----|----|----|----|----|----|-----|-----|-----|-----|
| 1 | - | 1 | - | 5 | - | 1 | 8 | 5 | 8 | 5 | 8 | - |
| +14 | -15 | +16 | -17 | +18 | -19 | +20 | +21 | +22 | +23 | +24 | +25 | -26 | ... |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | - | 1 | - | 5 | - | 1 | 8 | 5 | 8 | 5 | 8 | - | ... |
The second row of the table contains the possible winning moves (to win the player can erase so many numbers that after his move the quantity of the numbers remained on the blackboard 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 numbers for the beginning player. To win Jerry can erase so many numbers 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.