62nd Ukrainian National Mathematical Olympiad, Third Round, Second Tour

Question

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, 3^1, 3^2, ..., 3^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?

Accepted Answer

In one operation the product of all written numbers increases in

3^{5}

times. At the beginning, this product equals

3^{0 + 1 + 2 + ... + 19} = 3^{190}

. So, after using it

n

times, the product will be equal to

3^{190 + 5 n}

. By that time all numbers would have to become equal, and therefore at least

3^{19}

, so in the end the product is at least

3^{20 p}

, where

p \geq 19

. Then

3^{20 p} = 3^{190 + 5 n}

,

5 n + 190 = 20 p

and

n + 38 = 4 p

, and as

p \geq 19

, we get

n \geq 38

. Now let's show how to achieve this by using the program 38 times.

3^{0}, 3^{1}, 3^{2}, 3^{3}, 3^{4} (15) 3^{5}, 3^{6}, 3^{7}, 3^{8}, 3^{9} (10) 3^{10}, 3^{11}, 3^{12}, 3^{13}, 3^{14} (5) \to 3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}; \to 3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}; \to 3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19} .

So after 30 uses we have 4 of each of

3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}

.

3^{15}, 3^{16}, 3^{17}, 3^{18} (3) 3^{16}, 3^{17}, 3^{18}, 3^{19} (2) 3^{17}, 3^{18}, 3^{19}, 3^{20} (1) \to 3^{18}, 3^{19}, 3^{19}, 3^{19}; \to 3^{18}, 3^{19}, 3^{19}, 3^{19}; \to 3^{18}, 3^{19}, 3^{20}, 3^{20} .

So after 36 uses we have 10 of

3^{18}, 3^{19}

. In the last two moves we make them all equal to

3^{19}

.