Track / Stage 6 / 256 of 400 #1736 of 2444

Problem 1736

National Olympiad, first round

Combinatorics Difficulty 6.6 Prove it Croatian Mathematical Competitions · Croatia

There are some integers written on the blackboard. In each step two numbers $a$ and $b$ are chosen and replaced with the numbers $3a - b$ and $13a - 3b$ . If there are numbers $1$ , $2$ , $3$ , $4$ , $\ldots$ , $2011$ , $2012$ on the blackboard at the beginning, is it possible to get numbers $2$ , $4$ , $6$ , $8$ , $\ldots$ , $4022$ , $4024$ on the blackboard after a finite number of steps?

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

In each step the sum of all numbers on the blackboard changes by
$((3a - b) + (13a - 3b)) - (a + b) = 15a - 5b = 5(3a - b).$
This difference is divisible by $5$ , i.e. the sum of all numbers written on the board in each step gives the same remainder when divided by $5$ .
At the beginning, the sum of all numbers on the board is
$1 + 2 + 3 + \dots + 2012 = \frac{2012 \cdot 2013}{2} = 1006 \cdot 2013$
and we have
$1006 \cdot 2013 \equiv 1 \cdot 3 \equiv 3 \pmod{5}.$
On the other hand,
$2 + 4 + 6 + \dots + 4024 = 2 \cdot (1 + 2 + 3 + \dots + 2012) \equiv 2 \cdot 3 \equiv 1 \pmod{5}.$
In conclusion, it is impossible to get the numbers $2$ , $4$ , $6$ , $\ldots$ , $4024$ .

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