, 2020

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Romania

A computer program reads the numbers displayed, identifies the selected ones and does one of the following actions:
- If $A$ is pressed, every selected number is changed to its successor;
- If $B$ is pressed, every selected number is changed to its triple.

On Andrei and Bogdan's computer screens are displayed the numbers $1$ , $3$ , $3^2$ , $3^3$ , ..., $3^{19}$ .

a) Andrei will select $5$ numbers and then presses $A$ , this is a type $A$ step.
Determine if there is a succession of type $A$ steps in order to obtain the sum of all displayed numbers to be equal to $2019^{2020}$ .

b) Bogdan will select $5$ numbers and then presses $B$ , this is a type $B$ step.
What is the minimum number of type $B$ steps needed in order to obtain all the displayed numbers to be equal?

Solution

a) At every step of type $A$ , the sum of the displayed numbers increases by $5$ . The remainder modulo $5$ of the sum is invariant.
The sum of four consecutive powers of $3$ is $3^n + 3^{n+1} + 3^{n+2} + 3^{n+3} = 3^n(1 + 3 + 9 + 27) = 40 \cdot 3^n$ , therefore initially we have the remainder zero modulo $5$ and it is impossible to obtain $2019^{2020}$ .

b) At every step the product of the displayed numbers is multiplied by $3^5$ .
Initially the product is $3^{1+2+...+19} = 3^{190}$ and after $n$ type $B$ steps the product will be equal to $3^{190+5n}$ .
Suppose that in $n$ steps the numbers are equal to a power of $3$ , at least $3^{19}$ . The product of the $20$ numbers will be $3^{20p}$ , where $p \ge 19$ .
We must have $3^{20p} = 3^{190+5n}$ , so $n + 38 = 4p$ . Since $p \ge 19$ , we have $n \ge 38$ .
Next we provide a succession of $38$ type $B$ steps to display in the end equal numbers.

In $15$ steps, the numbers $1$ , $3$ , $3^2$ , $3^3$ , $3^4$ become $3^{15}$ , $3^{16}$ , $3^{17}$ , $3^{18}$ , $3^{19}$ . In the next $10$ steps $3^5$ , $3^6$ , $3^7$ , $3^8$ , $3^9$ become $3^{15}$ , $3^{16}$ , $3^{17}$ , $3^{18}$ , $3^{19}$ and the numbers $3^{10}$ , $3^{11}$ , $3^{12}$ , $3^{13}$ , $3^{14}$ become $3^{15}$ , $3^{16}$ , $3^{17}$ , $3^{18}$ , $3^{19}$ in $5$ steps.

Thus in $30$ steps numbers $3^{15}, 3^{16}, 3^{17}, 3^{18}, 3^{19}$ are displayed each $4$ times.
Numbers $3^{15}, 3^{15}, 3^{15}, 3^{15}, 3^{16}$ become $3^{18}, 3^{18}, 3^{18}, 3^{18}, 3^{19}$ after three steps.
Numbers $3^{16}, 3^{16}, 3^{16}, 3^{17}, 3^{17}$ become $3^{18}, 3^{18}, 3^{18}, 3^{19}, 3^{19}$ in $2$ steps.
Numbers $3^{17}, 3^{17}, 3^{18}, 3^{18}, 3^{18}$ become $3^{18}, 3^{18}, 3^{19}, 3^{19}, 3^{19}$ in one step.
Therefore after $36$ steps on Bogdan's computer screen are displayed $10$ of $3^{19}$ and $10$ of $3^{18}$ .
In last $2$ steps we make all numbers equal to $3^{19}$ .

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.