Browse · MathNet
PrintUkrainian National Mathematical Olympiad
Ukraine algebra
Problem
The number is written on the board. Two players are playing the following game. A move consists of replacing the number on the board with the difference of this number and one of its divisors. The player who writes loses. Who of the two players can guarantee the win?
(Oleksiy Piskun)
(Oleksiy Piskun)
Solution
It is easy to observe that odd numbers have only odd divisors. So, if the player moves from an odd number, he has to write an even number. This provides a strategy for the second player: subtract from the current number at any move. Then the first player will always deal with an odd number, so will write an even number. Since the number written on the board always decreases, eventually the first player will have to write .
Final answer
Second player
Techniques
IntegersGames / greedy algorithmsDivisibility / Factorization