Maths Olympiad Prep

Library / /25 of 27

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Austria

The numbers 1,2,,20201, 2, \dots, 2020 and 20212021 are written on a blackboard. The following operation is executed:
Two numbers are chosen, both are erased and replaced by the absolute value of their difference.
This operation is repeated until there is only one number left on the blackboard.

a) Show that 20212021 can be the final number on the blackboard.

b) Show that 20202020 cannot be the final number on the blackboard.

Solution

(a) Let us first choose the following 10101010 pairs of numbers:
(1,2);(3,4);;(2019,2020)(1, 2); (3, 4); \ldots; (2019, 2020).
The absolute value of the difference within each of these pairs is 11. After applying the operation for each of these pairs, the number 20212021 and 10101010 times the number 11 remain on the blackboard. Now we execute the given operation 505505 times with pairs of the form (1,1)(1, 1). Then the number 20212021 and 505505 times the number 00 remain on the blackboard. As 20210=20212021 - 0 = 2021 and 00=00 - 0 = 0, we end up with 20212021 as the final number on the board after additional 505505 operations, regardless of the pairs we pick at each step.

(b) We prove a more general statement: The final remaining number on the blackboard cannot be even.
As
aba+b(mod2), a - b \equiv a + b \pmod{2},
we obtain that the parity of the sum of all numbers on the board is an invariant throughout the game. At the beginning, the sum of the numbers on the blackboard is
202120222=20211011, \frac{2021 \cdot 2022}{2} = 2021 \cdot 1011,
an odd number. Therefore, the final number on the board must be odd as well. In particular, 20202020 cannot be the final number on the blackboard.

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.