Maths Olympiad Prep

Library / /2 of 4

Combinatorics Difficulty 6.3 National Olympiad Prove it Austria

On a circle 2018 points are marked.
Each of these points is labeled with an integer. Let each number be larger than the sum of the preceding two numbers in clockwise order.
Determine the maximal number of positive integers that can occur in such a configuration of 2018 integers.

Solution

Let the points be labeled a0,a1,,a2017a_0, a_1, \dots, a_{2017} clockwise with cyclical notation, i.e., ak+2018=aka_{k+2018} = a_k for all integers kk.

Lemma. In a valid configuration, no two neighbouring numbers can be both non-negative.

Proof. Assume that there exist neighbouring numbers ak1a_{k-1} and aka_k which are both non-negative. We get ak+1>ak+ak1aka_{k+1} > a_k + a_{k-1} \ge a_k, with the first inequality following from the problem statement and the second from ak10a_{k-1} \ge 0. Since now also aka_k and ak+1a_{k+1} are both non-negative, we analogously get ak+2>ak+1a_{k+2} > a_{k+1}, then ak+3>ak+2a_{k+3} > a_{k+2}, and so on, until we have ak+2018>ak+2017>>ak+1>ak=ak+2018a_{k+2018} > a_{k+2017} > \dots > a_{k+1} > a_k = a_{k+2018}, a contradiction. ■

Therefore at most every second number can be non-negative. Next we will show that these are still too many non-negative numbers.

Lemma. In a valid configuration, it is not possible that every second number is non-negative.

Proof. Assume that this is the case, so w.l.o.g. a2k0a_{2k} \ge 0 and a2k+1<0a_{2k+1} < 0 for all integers kk. Then we get a3>a2+a1a1a_3 > a_2 + a_1 \ge a_1, where again the first inequality follows from the problem statement and the second from a20a_2 \ge 0. Analogously we get a5>a3a_5 > a_3, then a7>a5a_7 > a_5, etcetera, until we have a1=a2019>a2017>a2015>>a3>a1a_1 = a_{2019} > a_{2017} > a_{2015} > \dots > a_3 > a_1, a contradiction. ■

We can therefore summarize: A configuration with more than 1009 non-negative numbers is not possible because otherwise by the pigeonhole principle we would have two neighbouring non-negative numbers, which is not allowed according to the first lemma. A configuration with exactly 1009 non-negative numbers contradicts either the first or the second lemma.

With 1008 positive and 1010 negative numbers we find for example the configuration

4035,1,4033,1,4031,1,4029,,1,2021,1,2019,2017,-4035, 1, -4033, 1, -4031, 1, -4029, \dots, 1, -2021, 1, -2019, -2017,

which we can easily check for correctness.

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.