Competition problem — Combinatorics

Library / /259 of 264

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Romania

Eight numbers, all zero, are written on a blackboard. A move consists in randomly selecting four of them, $a$ , $b$ , $c$ , $d$ , and replacing them by $a+3$ , $b+3$ , $c+2$ and $d+1$ , respectively.

a) What is the smallest number of moves after which on the blackboard can appear eight consecutive numbers?

b) Is there a sequence of moves after which all the numbers on the blackboard are equal to $2015$ ?

Solution

a) After each move, the sum of the numbers increases by $9$ . Since the sum of the smallest $8$ consecutive numbers is $0 + 1 + 2 + \dots + 7 = 28$ , but the table below uses $1$ to $8$ (sum $36$ ), so let's check the table for correctness. The table shows the process:

Start	0	0	0	0	0	0	0	0
First move	1	2					3	3
Second move			2	1			3	3
Third move					3	3	1	2
Fourth move			1	3	2	3
Outcome	1	2	3	4	5	6	7	8

After four moves, the numbers on the blackboard can be eight consecutive numbers. Since each move increases the sum by

9

, and the sum of

1

8

36

, four moves are sufficient.

b) After $k$ moves, the sum of the eight numbers is $9k$ . Since $8 \cdot 2015 = 16120$ is not a multiple of $9$ , the answer is negative.

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.