$100$ integers are arranged in a circle. Each number is greater than the sum of the two subsequent numbers (in a clockwise order). Determine the maximal possible number of positive numbers in such circle. (S.Berlov)
Problem
Source: All Russian Grade 9 Day 2 P 1
Tags: combinatorics
12.08.2016 00:25
Label the numbers $a_1,a_2,\dotsc,a_{100}$. Then $a_i>a_{i+1}+a_{i+2}$ for all $i$, if we consider the indices $\pmod{100}$. Now assume that there are at least $50$ positive numbers on the circle. Then two positive numbers will follow a non-positive one (which contradicts the given condition) unless every other number is non-positive. Hence there are at most $50$ positive numbers on the circle, and according to the discussion above, we may assume wlog that they are $a_1,a_3,\dotsc,a_{99}$. But, adding some inequalities gives \[ a_{100}>a_1+a_2>a_1+a_3+a_4>a_1+a_3+a_5+a_6>\dotsb>\sum_{2\nmid i}a_i +a_{100} \iff 0> \sum_{2\nmid i}a_i\]so at least one of $a_1,a_2,\dotsc,a_{99}$ is negative as well, implying that at most $49$ of the numbers on the circle are positive. This is the number we are looking for: For the $98$ first $a_i$, let \[ a_i=\begin{cases} 1 &\text{if $i$ is odd,}\\ -998-i &\text{if $i$ is even,} \end{cases} \]and set $a_{99}=-700,a_{100}=-500$. This does indeed work, and we are done - the answer is $\boxed{49}$. Just a comment: This can probably be generalized for any even number of numbers on a circle satisfying the same conditions. A similar construction will do, but the negative numbers will have to have a little larger absolute value.
01.12.2017 16:51
Let $N$ be the number of positive integers. If there is part of sequence such as negative-positive-positive, it's contradiction. So $N<51$. Where $N=50$, sequence must have positve-negative in turn. In this case, let $P_{1}$ be the largest positve number in the sequence, and there are $P_{1},N_{1},P_{2},...,P_{49},N_{50}$ in clockwise. But $P_{49}>N_{50}+P_{1}$, contradiction. So $N<50$ Finding Examples where $N=49$ is not difficult.
11.04.2020 17:41
What about finding the greatest integer that can appear in the circle?
26.11.2024 16:07
roughlife wrote: Let $N$ be the number of positive integers. If there is part of sequence such as negative-positive-positive, it's contradiction. So $N<51$. Where $N=50$, sequence must have positve-negative in turn. In this case, let $P_{1}$ be the largest positve number in the sequence, and there are $P_{1},N_{1},P_{2},...,P_{49},N_{50}$ in clockwise. But $P_{49}>N_{50}+P_{1}$, contradiction. So $N<50$ Finding Examples where $N=49$ is not difficult. But I think the most difficult step is to construction......