Olympiad Maths Prep

Library / /5 of 6

, 2020

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Greece

On the blackboard are written in a line the numbers from 11 to 20302030 in increasing turn. We have the possibility of the “movement” KK: *We select two numbers α\alpha, β\beta from the blackboard written in successive positions and we substitute the pair (α\alpha, β\beta) with the number (αβ)2020(\alpha - \beta)^{2020}.*

We perform the movement as many times as we need in order to have on the blackboard only one number. Examine, if this number can be:

(a) 202020202020^{2020},

(b) 202120202021^{2020}.

Solution

(a) First we observe that:
At every movement KK, the numbers α+β\alpha + \beta and (αβ)2020(\alpha - \beta)^{2020} are congruent modulo 22, that is, both are even or both are odd. Therefore, after the substitution of α,β\alpha, \beta with the number (αβ)2020(\alpha - \beta)^{2020} the parity of the sum of the numbers on the blackboard remains invariant. Since

S2030=203020312=10152031 S_{2030} = \frac{2030 \cdot 2031}{2} = 1015 \cdot 2031
is odd, it follows that after the last movement the number remaining on the blackboard is odd and therefore the answer in the first question is negative.

(b) Let after performing the movement enough number of times we have on the blackboard two numbers x,yx, y. Then the only case in order no one of them is not a power of 22, is not to have taken part in any performed movement. This can happen only with the numbers 11 and 20302030. Since 11 is 120201^{2020}, it is enough to check 20302030. If x=a2020x = a^{2020} and y=2030y = 2030, then we must have (a20202030)2020=20212020(a^{2020} - 2030)^{2020} = 2021^{2020}. For a=1a = 1 there is no solution and for a2a \ge 2 we get a2020=4051a^{2020} = 4051, impossible.

In any other case we will have from the procedure that x=(a1b1)2020=m2020x = (a_1 - b_1)^{2020} = m^{2020} and y=(a2b2)2020=n2020y = (a_2 - b_2)^{2020} = n^{2020}, for some mm and nn. By performing the last movement, remains on the blackboard the number (m2020n2020)2020(m^{2020} - n^{2020})^{2020}. We have to check if it is possible to be valid the following equality:

(m2020n2020)2020=20212020. (m^{2020} - n^{2020})^{2020} = 2021^{2020}.

If m=nm = n, it is not valid. We suppose wlog m>nm > n. Then we must check if

m2020n2020=2021.(1) m^{2020} - n^{2020} = 2021. \qquad (1)

The least possible value of m2020n2020m^{2020} - n^{2020} is 11, for m=1,n=0m = 1, n = 0. From (1) we have that m>nm > n, and hence mn+1m \ge n + 1. Therefore m2020n2020(n+1)2020n2020m^{2020} - n^{2020} \ge (n+1)^{2020} - n^{2020}. By developing the last expression we observe that all coefficients of nn have positive sign and so it is increasing. Hence m2020n2020(n+1)2020n2020220201>2111=2047m^{2020} - n^{2020} \ge (n+1)^{2020} - n^{2020} \ge 2^{2020} - 1 > 2^{11} - 1 = 2047 and therefore it cannot be equal to 20212021.

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.