Maths Olympiad Prep

Library / /261 of 520

Number theory Difficulty 5.2 AIME, harder Find the answer

Example 1 There are nn stones, and two people take turns to take them. It is stipulated that the number of stones taken each time is a positive divisor of the current number of stones, and the one who takes the last stone loses. Question: Who has a winning strategy?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution: The final losing position is a single stone, and the player who creates this state wins. Note that 1 is an odd number, which is a significant characteristic of a losing position. Therefore, we call a state with an odd number of stones an odd state. If a player can make a clever move to always reach a losing state:

Naturally, for any odd state, after one operation, only an odd number of positive divisors of the stones can be taken out, resulting in an even state. For an even state, the player can take away one stone, leaving an odd number of stones, thus reaching an odd state.

In summary, when nn is odd, the given state is a losing position, meaning the second player has a winning strategy; when nn is even, the given state is a winning position, meaning the first player has a winning strategy.

Using a similar method, we can solve a problem from the 1989 Leningrad Mathematical Olympiad:

Two people play a game, with the number 2 written on the blackboard. They take turns replacing the number nn on the blackboard with n+dn+d, where dd is any positive divisor of nn other than itself. The player who writes a number greater than 19891989 loses. Who has the winning strategy?

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.