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 clockwise with cyclical notation, i.e., for all integers .
Lemma. In a valid configuration, no two neighbouring numbers can be both non-negative.
Proof. Assume that there exist neighbouring numbers and which are both non-negative. We get , with the first inequality following from the problem statement and the second from . Since now also and are both non-negative, we analogously get , then , and so on, until we have , 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. and for all integers . Then we get , where again the first inequality follows from the problem statement and the second from . Analogously we get , then , etcetera, until we have , 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
which we can easily check for correctness.