Maths Olympiad Prep

Library / /95 of 101

Number theory Difficulty 7.4 National olympiad, round 2 Prove it Estonia

Kati writes the numbers
20,21,22,,2100,30,31,32,,3100,60,61,62,,6100 2^0, 2^1, 2^2, \dots, 2^{100}, 3^0, 3^1, 3^2, \dots, 3^{100}, 6^0, 6^1, 6^2, \dots, 6^{100}
on the board. In each step, she performs one of the following operations:
(1) She can pick two numbers and replace them with their greatest common divisor and least common multiple; or
(2) She can pick two numbers, one of which is divisible by the other, and replace them with some two numbers whose greatest common divisor and least common multiple would be the two picked numbers.
Find the least and the greatest sum of all numbers on the board that can be achieved via finitely many steps.

Solution

At all points throughout the process, every number on the board can be written as 2α3β2^\alpha 3^\beta for some 0α,β1000 \le \alpha, \beta \le 100. Moreover, the list of exponents of both 22 and 33 does not change throughout the process. Indeed, in a step of the first kind, two numbers 2α13β12^{\alpha_1} 3^{\beta_1} and 2α23β22^{\alpha_2} 3^{\beta_2} are turned into 2min(α1,α2)3min(β1,β2)2^{\min(\alpha_1, \alpha_2)} 3^{\min(\beta_1, \beta_2)} and 2max(α1,α2)3max(β1,β2)2^{\max(\alpha_1, \alpha_2)} 3^{\max(\beta_1, \beta_2)}, preserving both the exponents α1,α2\alpha_1, \alpha_2 of 22 and the exponents β1,β2\beta_1, \beta_2 of 33. A step of the second kind is just the reverse of a step of the first kind, so the exponents are preserved again.
Thus the lists of both the exponents of 22 and 33 are
0,,0103 copies;1,1,2,2,,100,100. \underbrace{0, \dots, 0}_{103 \text{ copies}}; 1, 1, 2, 2, \dots, 100, 100.

By the rearrangement inequality, we obtain that the sum of the numbers on the board is the greatest when they are
1,,1103 copies;6,6,62,62,,6100,6100. \underbrace{1, \dots, 1}_{103 \text{ copies}}; 6, 6, 6^2, 6^2, \dots, 6^{100}, 6^{100}.
The sum of these numbers equals 101+2610115101 + 2 \cdot \frac{6^{101}-1}{5}. These numbers can be achieved by performing a step of the first kind on the numbers 2γ2^\gamma and 3γ3^\gamma for every γ=1,,100\gamma = 1, \dots, 100.

By the rearrangement inequality, we obtain that the sum of the numbers on the board is the least when the lists of the exponents of 22 and 33 are sorted in opposite directions. This means that the numbers would be
21002100299299298298251251250250249249324832483224732234934935035035135135235235339931003100. \begin{array}{ccccccccccc} 2^{100} & 2^{100} & 2^{99} & 2^{99} & 2^{98} & 2^{98} & \dots & 2^{51} & 2^{51} & 2^{50} \\ 2^{50} & 2^{49} & 2^{49} \cdot 3 & 2^{48} \cdot 3 & 2^{48} \cdot 3^2 & 2^{47} \cdot 3^2 & \dots & 2 \cdot 3^{49} & 3^{49} & 3^{50} \\ 3^{50} & 3^{51} & 3^{51} & 3^{52} & 3^{52} & 3^{53} & \dots & 3^{99} & 3^{100} & 3^{100}. \end{array}
Using the formula for the sum of a geometric series for each row, separately for numbers at odd positions and even positions, yields:
* for the first row, 21012502^{101} - 2^{50} and 21012512^{101} - 2^{51};
* for the second row, 3512513^{51} - 2^{51} and 3502503^{50} - 2^{50};
* for the third row, 12(3101350)\frac{1}{2}(3^{101} - 3^{50}) and 12(3101351)\frac{1}{2}(3^{101} - 3^{51}).

Thus the sum of all the numbers is 21023251+2350+31012^{102} - 3 \cdot 2^{51} + 2 \cdot 3^{50} + 3^{101}. This is indeed achievable. For this, we will pair the first desired number with the last one, the second first number with the second last one, etc. The least common multiples of the pairs are 6100,6100,,626,626,6256^{100}, 6^{100}, \dots, 6^{26}, 6^{26}, 6^{25} and the greatest common divisors are 1,1,,1103 copies;6,6,62,62,,624,624\underbrace{1, 1, \dots, 1}_{103 \text{ copies}}; 6, 6, 6^2, 6^2, \dots, 6^{24}, 6^{24}. Finally, 6256^{25} is left over. This means that we can use steps of the second kind to achieve the desired numbers from the situation with the maximal sum.

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 and solution reproduced as published; topic and difficulty added by this site.