Olympiad Maths Prep

Library / /14 of 15

Combinatorics Difficulty 6.8 National olympiad Prove it Ukraine

Petrik uses the computer program "Three", which converts the numbers written on the display. For one application of this program Petrik chooses 5 numbers from the written ones, and the program increases each of these 5 numbers in 3 times. At the beginning, the following 20 numbers are written on the display: 1, 313^1, 323^2, ..., 3193^{19}. What smallest number of times does Petrik have to use the program to be able to get a set of equal numbers on the display?

Solution

In one operation the product of all written numbers increases in 353^5 times. At the beginning, this product equals 30+1+2+...+19=31903^{0+1+2+...+19} = 3^{190}. So, after using it nn times, the product will be equal to 3190+5n3^{190+5n}. By that time all numbers would have to become equal, and therefore at least 3193^{19}, so in the end the product is at least 320p3^{20p}, where p19p \ge 19. Then 320p=3190+5n3^{20p} = 3^{190+5n}, 5n+190=20p5n + 190 = 20p and n+38=4pn + 38 = 4p, and as p19p \ge 19, we get n38n \ge 38. Now let's show how to achieve this by using the program 38 times.

30,31,32,33,34(15)315,316,317,318,319;35,36,37,38,39(10)315,316,317,318,319;310,311,312,313,314(5)315,316,317,318,319. \begin{aligned} 3^0, 3^1, 3^2, 3^3, 3^4 \quad (15) &\rightarrow 3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}; \\ 3^5, 3^6, 3^7, 3^8, 3^9 \quad (10) &\rightarrow 3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}; \\ 3^{10}, 3^{11}, 3^{12}, 3^{13}, 3^{14} \quad (5) &\rightarrow 3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}. \end{aligned}
So after 30 uses we have 4 of each of 315,316,317,318,3193^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}.

315,316,317,318(3)318,319,319,319;316,317,318,319(2)318,319,319,319;317,318,319,320(1)318,319,320,320. \begin{aligned} 3^{15}, 3^{16}, 3^{17}, 3^{18} \quad (3) &\rightarrow 3^{18}, 3^{19}, 3^{19}, 3^{19}; \\ 3^{16}, 3^{17}, 3^{18}, 3^{19} \quad (2) &\rightarrow 3^{18}, 3^{19}, 3^{19}, 3^{19}; \\ 3^{17}, 3^{18}, 3^{19}, 3^{20} \quad (1) &\rightarrow 3^{18}, 3^{19}, 3^{20}, 3^{20}. \end{aligned}
So after 36 uses we have 10 of 318,3193^{18}, 3^{19}. In the last two moves we make them all equal to 3193^{19}.

Looking for a route rather than 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.