Maths Olympiad Prep

Library / /28 of 46

Combinatorics Difficulty 6.4 National olympiad Prove it Russia

11 positive integers are arranged on a circle. It appears that the difference between each two neighboring numbers is not less than 20, while the sum of each two neighboring numbers is not less than 100. Find the least possible value of the sum of all 11 integers.

Solution

Consider an arrangement that satisfies the conditions, and connect each pair of neighboring numbers with an arrow from the smaller to the larger. Since the total number of arrows is odd, there must be two consecutive arrows pointing in the same direction: abca \to b \to c. Then bc20b \leq c - 20, ab20c40a \leq b - 20 \leq c - 40, so 100a+b2c60100 \leq a + b \leq 2c - 60, from which c80c \geq 80. All numbers except cc can be divided into 5 pairs of neighboring numbers; thus, the sum of all numbers is at least 80+5100=58080 + 5 \cdot 100 = 580.

One example of an arrangement where this bound is achieved is shown in Fig. 17.

Second solution. Here is another proof that the sum is at least 580. Note that in any pair of neighboring numbers, one of them is at least 60 (if the larger is less than 60, then the other number is ...). Divide the remaining numbers into pairs of neighbors (the sum in each pair is at least 100, so the sum of all these 10 numbers is at least 500). Next, in each pair, mark the number that is at least 60; also mark the number cc. We have marked 6 numbers out of 11, so two of them are neighbors. Then the larger of them is at least 60+20=8060 + 20 = 80, so c80c \geq 80. Therefore, the sum of all numbers is at least 80+500=58080 + 500 = 580.

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.