Track / Stage 5 / 292 of 400 #1372 of 2444

Problem 1372

AIME late

Combinatorics Difficulty 5.7 Prove it UkraineMO · Ukraine

There are four numbers on the board: $1$ , $3$ , $6$ and $10$ . Each time we can erase any two numbers $a$ , $b$ written on the board and write numbers $a+b$ , $ab$ instead. Can we obtain such four numbers

a) $2015$ , $2016$ , $2017$ , $2018$ ; after several moves?

b) $2016$ , $2017$ , $2019$ , $2022$

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

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

a) Let us look at the numbers modulo $3$ . Obviously, the amount of numbers divisible by $3$ cannot decrease. Because if both $a$ , $b$ are divisible by $3$ , then both $a+b$ , $ab$ are also divisible by $3$ . If one of the numbers is divisible by $3$ , then $ab$ is also divisible by $3$ . Thus, at the beginning we had only one number divisible by $3$ , 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 $3$ . Thus those numbers equal $0$ , $0$ , $0$ , $k$ , where $k \in \{1, 2\}$ modulo $3$ . Thus these four numbers will never change. Let us check now when the amount of numbers divisible by $3$ can increase. Then $a$ , $b$ should be $1$ , $2$ modulo $3$ . However, then numbers $0$ , $2$ appear. Thus in the situation where exactly three numbers are divisible by $3$ , they should equal $0$ , $0$ , $0$ , $2$ , and four numbers from condition equal $0$ , $0$ , $0$ , $1$ . Thus we get a contradiction.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.