Maths Olympiad Prep

Library / /349 of 377

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

Consider the following two-player game. Player 1 starts with a number, NN. He then subtracts a proper divisor of NN from NN and gives the result to player 2 (a proper divisor of NN is a positive divisor of NN that is not equal to 1 or NN). Player 2 does the same thing with the number she gets from player 1, and gives the result back to player 1. The two players continue until a player is given a prime number, at which point that player loses. For how many values of NN between 2 and 100 inclusive does player 1 have a winning strategy?

Solution

Solution:

Answer: 47

We claim that player 1 has a winning strategy if and only if NN is even and not an odd power of 2.

First we show that if you are stuck with an odd number, then you are guaranteed to lose. Suppose you have an odd number abab, where aa and bb are odd numbers, and you choose to subtract aa. You pass your opponent the number a(b1)a(b-1). This cannot be a power of 2 (otherwise aa is a power of 2 and hence a=1a=1, which is not allowed), so your opponent can find an odd proper divisor of a(b1)a(b-1) (such as aa), and you will have a smaller odd number. Eventually you will get to an odd prime and lose.

Now consider even numbers that aren't powers of 2. As with before, you can find an odd proper divisor of NN and pass your opponent an odd number, so you are guaranteed to win.

Finally consider powers of 2. If you have the number N=2kN=2^{k}, it would be unwise to choose a proper divisor other than 2k12^{k-1}; otherwise you would give your opponent an even number that isn't a power of 2. Therefore if kk is odd, you will end up with 2 and lose. If kk is even, though, your opponent will end up with 2 and you will win.

Therefore player 1 has a winning strategy for all even numbers except for odd powers of 2.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.