Maths Olympiad Prep

Library / /21 of 34

Combinatorics Difficulty 5.9 AIME, harder Prove it Mongolia

51 distinct integers are placed on a circle in such a way that each number is greater than the sum of the next three numbers in clockwise direction. What is the maximal number of numbers greater than or equal to 1?

Solution

If there are three consecutive positive numbers aia_i, ai+1a_{i+1} and ai+2a_{i+2}, then ai1>0a_{i-1} > 0. Hence we conclude that all the numbers are positive. But for the smallest number on the circle it is impossible to be greater than the sum of the next three numbers. Therefore for any three consecutive numbers, at least one of them is negative. Hence there are at least 51/3=1751/3 = 17 negative numbers on the circle. Suppose that there are exactly 17 negative numbers. Then for any three consecutive numbers only one of them is negative. Suppose that aia_i, ai+3a_{i+3}, ai+6a_{i+6}, ai+9a_{i+9}, ..., where (i=123)(i = 1 \vee 2 \vee 3), are negative. Observe that
ai>ai+1+ai+2+ai+3>ai+3. a_i > a_{i+1} + a_{i+2} + a_{i+3} > a_{i+3}.

Hence ai>ai+3>ai+6>>aia_i > a_{i+3} > a_{i+6} > \cdots > a_i, which gives a contradiction. Therefore there are at most 5118=3351 - 18 = 33 positive numbers on the circle. Let us give an example below.

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.