Browse · MathNet
Print60th Belarusian Mathematical Olympiad
Belarus counting and probability
Problem
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 or exactly stones. The player wins if he removes the last stone. Before the start Nick fixes the value of (). After that Mike fixes the value of (, ), 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 stones remain in the heap before the move of a player and he can win, then we write , otherwise we write .
Let . 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 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 . 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 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 . 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 | - | ... |
We see that the signs in the table are repeated with the period equaled 11 (it is easy to prove by induction). Since it follows that 330 is marked with the sign "-". Thus the number 330 is the losing number of the stones for the beginning player.
Now, let . 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 it follows that 330 is marked with the sign "-". Thus the number 330 is the losing number of the stones for the beginning player.
Now we will solve the problem moving backward. We write all numbers from 1 to 330 and mark them with "+" or "-". If stones remain in the heap before the move of a player and he can win, then we write , otherwise we write .
Let . 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 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 . 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 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 . 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 | - | ... |
We see that the signs in the table are repeated with the period equaled 11 (it is easy to prove by induction). Since it follows that 330 is marked with the sign "-". Thus the number 330 is the losing number of the stones for the beginning player.
Now, let . 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 it follows that 330 is marked with the sign "-". Thus the number 330 is the losing number of the stones for the beginning player.
Final answer
Mike
Techniques
Games / greedy algorithmsInduction / smoothing