Maths Olympiad Prep

Library / /26 of 44

Number theory Difficulty 5.8 AIME, harder Prove it Slovenia

A positive integer nn is written on the blackboard. In each step we replace the number by the sum of any two positive integers whose product is equal to the number on the board. Determine the smallest number that can be obtained after a finite number of steps in terms of the initial number nn.

Solution

First, let us show the following: if the number on the blackboard has decreased after the change, then the new number is greater than or equal to 55. We cannot obtain the number 11 because the sum of two positive integers can never be equal to 11. The number 2=1+12 = 1 + 1 can only be obtained from 11, the number 3=1+23 = 1 + 2 can only be obtained from 22, and the number 4=1+3=2+24 = 1 + 3 = 2 + 2 can only be obtained from 33 or 44. So, if the number obtained is less than 55, then it has not decreased during the change. If the starting number was n<5n < 5, then we cannot get a smaller number.

Now, let us show that if a number is greater than 55, then it can be reduced. Assume that the number m>5m > 5 is on the blackboard at a given time. If mm is even, i.e. of the form m=2km = 2k, where k>2k > 2 is a positive integer, then it can be replaced by k+2k + 2. In this way we have obtained a number smaller than mm, since the condition k+2<2kk + 2 < 2k is equivalent to the assumption k>2k > 2. If mm is odd, then we can express it as m=2k1m = 2k - 1, where k>3k > 3 is a positive integer. In this case, we can first replace it by (2k1)+1=2k(2k - 1) + 1 = 2k and then with k+2k + 2. Once again we have obtained a number smaller than mm, because the condition k+2<2k1k + 2 < 2k - 1 is equivalent to our assumption k>3k > 3. Therefore, if the starting number is n5n \ge 5, we can reduce it to the number 55, using a finite number of steps, and according to the reasoning above this is the smallest number that can be obtained.

The smallest number we can obtain after a finite number of steps is equal to 55 if n5n \ge 5 and is equal to n<5n < 5.

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.