Maths Olympiad Prep

Library / /33 of 62

Combinatorics Difficulty 5.7 AIME, harder Prove it Ukraine

There are four numbers on the board: 11, 33, 66 and 1010. Each time we can erase any two numbers aa, bb written on the board and write numbers a+ba+b, abab instead. Can we obtain such four numbers

a) 20152015, 20162016, 20172017, 20182018; after several moves?

b) 20162016, 20172017, 20192019, 20222022

Solution

Answer: a), b) that is not possible.

a) Let us look at the numbers modulo 33. Obviously, the amount of numbers divisible by 33 cannot decrease. Because if both aa, bb are divisible by 33, then both a+ba+b, abab are also divisible by 33. If one of the numbers is divisible by 33, then abab is also divisible by 33. Thus, at the beginning we had only one number divisible by 33, and in the end only one, thus such situation is impossible.

b) Let us look at the situation now when exactly three numbers are divisible by 33. Thus those numbers equal 00, 00, 00, kk, where k{1,2}k \in \{1, 2\} modulo 33. Thus these four numbers will never change. Let us check now when the amount of numbers divisible by 33 can increase. Then aa, bb should be 11, 22 modulo 33. However, then numbers 00, 22 appear. Thus in the situation where exactly three numbers are divisible by 33, they should equal 00, 00, 00, 22, and four numbers from condition equal 00, 00, 00, 11. Thus we get a contradiction.

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.