Maths Olympiad Prep

Library / /25 of 31

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Italy

Problem:

For a fixed integer n>1n>1, Alberto and Barbara play the following game:

1. Alberto chooses a positive integer;
2. Barbara chooses an integer greater than 1 that is a multiple or a divisor of Alberto's number (including the number itself);
3. Alberto returns to Barbara the number she said, possibly adding or subtracting 1;
the game continues by alternately repeating steps 2 and 3. Barbara wins if she manages to choose nn within 50 moves. For which values of nn can Barbara win against any strategy of Alberto?

Solution

Solution:

Barbara manages to say the number nn within 50 moves (in fact, at most 8 are needed), regardless of Alberto's strategy, if and only if nn is a multiple of 6.

Indeed, suppose that nn is a multiple of 6. Then we have that:
- if at a certain step Alberto chooses an even number, at the next step Barbara can choose 2, at which point Alberto can only play 1, 2, or 3, and in any case at the next step Barbara will be able to say nn;
- if at a certain step Alberto chooses an odd number dd, at the next step Barbara can choose 3d3d, at which point Alberto either plays an even number (falling into the previous case) or leaves 3d3d unchanged. At this point Barbara chooses the number 3, at which Alberto can only play 2, 3, or 4. If he plays 2 or 4 he loses because they are even numbers, if he plays 3 he loses because at the next step Barbara plays nn.

Now suppose that nn is not a multiple of 6. Then Alberto can always play a number that is not a multiple or divisor of nn, thus preventing Barbara from winning on the next move. One possible strategy for Alberto is the following.
- At the first step he chooses n+1n+1.
- When Barbara returns a number a>na>n, Alberto examines aa and a+1a+1. Since n>1n>1, at least one of the two numbers is not a multiple of nn and can therefore be played.
- When Barbara returns a number b<nb<n, Alberto examines b1b-1, bb, and b+1b+1. Being three consecutive numbers, at least one will be even and at least one (possibly the same one) will be divisible by 3. Then nn cannot be simultaneously divisible by b1b-1, bb, and b+1b+1, because otherwise it would be divisible by 6, which is against our assumption. Hence in this case too at least one of the three numbers can be played "safely" by Alberto.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.