Competition problem — Combinatorics

Library / /29 of 30

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Belarus

There is a heap of 330 stones. Nick and Mike play the following game. They, in turn (Nick is the first), remove the stones from the heap. Per move it is allowed to remove exactly 1 or exactly $m$ or exactly $n$ stones. The player wins if he removes the last stone. Before the start Nick fixes the value of $n$ ( $1 < n < 10$ ). After that Mike fixes the value of $m$ ( $m \ne n$ , $1 < m < 10$ ), and Nick begins the game.
Can somebody of the players fix his number to win if both of them play to win?

Solution

We separate the numbers from 2 to 9 into the pairs (2, 7), (3, 8), (5, 6), (4, 9). In order to win Mike can use the following rule: if Nick fixes one of the numbers from any of the pairs, then Mike fixes the other number from the same pair.

Now we will solve the problem moving backward. We write all numbers from 1 to 330 and mark them with "+" or "-". If $k$ stones remain in the heap before the move of a player and he can win, then we write $+k$ , otherwise we write $-k$ .

Let $n, m = 2, 7$ . We have the following table

| +1 | +2 | -3 | +4 | +5 | -6 | +7 | +8 | -9 | +10 | +11 | -12 | +13 | +14 | -15 | +16 | ... |

We see that the signs in the table are repeated with the period equaled 3 (it is easy to prove by induction).
Since $330 \div 3$ it follows that 330 is marked with the sign "-". Thus the number 330 is the losing number of the stones for the beginning player.

Let $n, m = 3, 8$ . We have the following table

| +1 | -2 | +3 | -4 | +5 | -6 | +7 | +8 | +9 | +10 | -11 |
| 1 | - | 1 | - | 1 | - | 1 | 8 | 3 | 8 | - |
| +12 | -13 | +14 | -15 | +16 | -17 | +18 | +19 | +20 | +21 | -22 | ... |
| 1 | - | 1 | - | 1 | - | 1 | 8 | 3 | 8 | - | ... |

We see that the signs in the table are repeated with the period equaled 11 (it is easy to prove by induction).
Since $330 \div 11$ it follows that 330 is marked with the sign "-". Thus the number 330 is the losing number of the stones for the beginning player.

Let $n, m = 5, 6$ . We have the following table

| +1 | -2 | +3 | -4 | +5 | +6 | +7 | +8 | +9 | +10 | -11 |
| 1 | - | 1 | - | 5 | 6 | 5 | 6 | 5 | 6 | - |
| +12 | -13 | +14 | -15 | +16 | +17 | +18 | +19 | +20 | +21 | -22 | ... |
| 1 | - | 1 | - | 5 | 6 | 5 | 6 | 5 | 6 | - | ... |

Now, let $n, m = 4, 9$ . We have the table

| +1 | -2 | +3 | +4 | -5 | +6 | -7 | +8 | +9 | -10 |
| 1 | - | 1 | 4 | - | 1 | - | 1 | 9 | - |
| +11 | -12 | +13 | +14 | -15 | +16 | -17 | +18 | +19 | -20 | ... |
| 1 | - | 1 | 4 | - | 1 | - | 1 | 9 | - | ... |

We see that the signs in the table are repeated with the period equaled 10 (it is easy to prove by induction).
Since $330 \div 10$ it follows that 330 is marked with the sign "-". Thus the number 330 is the losing number of the stones for the beginning player.

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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.