Maths Olympiad Prep

Library / /1 of 2

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Romanian Master of Mathematics (RMM)

Problem:

Amy and Bob play the game. At the beginning, Amy writes down a positive integer on the board. Then the players take moves in turn, Bob moves first. On any move of his, Bob replaces the number nn on the blackboard with a number of the form na2n-a^{2}, where aa is a positive integer. On any move of hers, Amy replaces the number nn on the blackboard with a number of the form nkn^{k}, where kk is a positive integer. Bob wins if the number on the board becomes zero. Can Amy prevent Bob's win?

Solution

Solution:

The answer is in the negative. For a positive integer nn, we define its square-free part S(n)S(n) to be the smallest positive integer aa such that n/an / a is a square of an integer. In other words, S(n)S(n) is the product of all primes having odd exponents in the prime expansion of nn. We also agree that S(0)=0S(0)=0.

Now we show that (i) on any move of hers, Amy does not increase the square-free part of the positive integer on the board; and (ii) on any move of his, Bob always can replace a positive integer nn with a non-negative integer kk with S(k)<S(n)S(k)<S(n). Thus, if the game starts by a positive integer NN, Bob can win in at most S(N)S(N) moves.

Part (i) is trivial, as the definition of the square-part yields S(nk)=S(n)S\left(n^{k}\right)=S(n) whenever kk is odd, and S(nk)=1S(n)S\left(n^{k}\right)=1 \leq S(n) whenever kk is even, for any positive integer nn.

Part (ii) is also easy: if, before Bob's move, the board contains a number n=S(n)b2n=S(n) \cdot b^{2}, then Bob may replace it with n=nb2=(S(n)1)b2n' = n-b^{2} = (S(n)-1) b^{2}, whence S(n)S(n)1S\left(n'\right) \leq S(n)-1.

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.