Skip to main content
OlympiadHQ

Browse · MathNet

Print

60th Belarusian Mathematical Olympiad

Belarus counting and probability

Problem

There is a heap of 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 or exactly 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 () and defines the player to start the game. After that Mary fixes the value of (), 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 and defines himself as the first player, then Mary wins if she sets . Indeed, if Nick removes () stones, then Mary removes () stones. So exactly stones are removed from the heap after each pair of moves (Nick - Mary). Since , Mary wins.

If Nick fixes the number and defines Mary as the first player, then Mary wins if she sets for and her first move is to remove 1 stone from the heap. stones remain in the heap. It is easy to see that is divide by , i.e. is divided by for the fixed value of and . Therefore, Mary wins if she uses the symmetric strategy: when Nick removes () stones Mary removes () stones. So exactly stones are removed from the heap after each pair of moves (Nick - Mary).

If Nick sets , then Mary can choose any number from for , and play in the same way as above (first move is stone, and symmetric strategy).

If Nick sets , then Mary wins if she sets and her first move is to remove stones from the heap. stones remain in the heap. It is easy to see that is divided by , i.e. is divided by . To win Mary can use the symmetric strategy.

Techniques

Games / greedy algorithmsLeast common multiples (lcm)