Competition problem — Combinatorics

Library / /71 of 82

Combinatorics Difficulty 6.6 National olympiad Prove it 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?

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$ .

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.