Olympiad Maths Prep

Library / /26 of 30

Combinatorics Difficulty 6.9 National olympiad Prove it Belarus

There is a heap of 2520125201 stones. Nick and Mary play the following game. They, in turn, remove the stones from the heap. Per move it is allowed to remove either exactly mm or exactly nn stones. The player wins if he removes the last stone. If the last stone can not be removed by any of the players, then the result of the game is a draw. Before the start Nick fixes the value of nn (1n101 \le n \le 10) and defines the player to start the game. After that Mary fixes the value of mm (mn,1m10m \ne n, 1 \le m \le 10), then the game starts.
Can somebody of the players fix his/her number to win if both of them play to win?
(V. Kaskevich)

Solution

If Nick fixes the number nn and defines himself as the first player, then Mary wins if she sets m=11nm = 11 - n. Indeed, if Nick removes nn (mm) stones, then Mary removes mm (nn) stones. So exactly 11=m+n11 = m + n stones are removed from the heap after each pair of moves (Nick - Mary). Since 25201=22911125201 = 2291 \cdot 11, Mary wins.

If Nick fixes the number nn and defines Mary as the first player, then Mary wins if she sets m=1m = 1 for n=2,3,4,5,6,7,8,9n = 2, 3, 4, 5, 6, 7, 8, 9 and her first move is to remove 1 stone from the heap. 2520025200 stones remain in the heap. It is easy to see that 25202520 is divide by 3,4,5,6,7,8,9,103, 4, 5, 6, 7, 8, 9, 10, i.e. 2520025200 is divided by n+mn+m for the fixed value of nn and mm. Therefore, Mary wins if she uses the symmetric strategy: when Nick removes nn (mm) stones Mary removes mm (nn) stones. So exactly m+nm+n stones are removed from the heap after each pair of moves (Nick - Mary).

If Nick sets n=1n = 1, then Mary can choose any number from 2,3,4,5,6,7,8,92, 3, 4, 5, 6, 7, 8, 9 for mm, and play in the same way as above (first move is 11 stone, and symmetric strategy).

If Nick sets n=10n = 10, then Mary wins if she sets m=7m = 7 and her first move is to remove 77 stones from the heap. 2519425194 stones remain in the heap. It is easy to see that 25194=14821725194 = 1482 \cdot 17 is divided by 1717, i.e. 2519425194 is divided by n+mn+m. To win Mary can use the symmetric strategy.

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.