Let be given $r_1,r_2,\ldots,r_n \in \mathbb R$. Show that there exists a subset $I$ of $\{1,2,\ldots,n \}$ which which has one or two elements in common with the sets $\{i,i + 1,i + 2\} , (1 \leq i \leq n- 2)$ such that \[\left| {\mathop \sum \limits_{i \in I} {r_i}} \right| \geqslant \frac{1}{6}\mathop \sum \limits_{i = 1}^n \left| {{r_i}} \right|.\]
Problem
Source: Iran Third Round MO 1998, Exam 4, P4
Tags: combinatorics, combinatorics proposed
lyukhson
16.06.2017 09:41
Anyone with solution?
TLP.39
26.08.2017 13:16
TROLLLLLLOLOLOLOLOOLOLLLLL THIS IS NOT INEQUALITY NOR NT(Anyway,beautiful problem. )
Since $\left| {\mathop \sum \limits_{i \in I} {r_i}} \right|\ge {\mathop \sum \limits_{i \in I} {r_i}},\left| {\mathop \sum \limits_{i \in I} {r_i}} \right|\ge -{\mathop \sum \limits_{i \in I} {r_i}}$,if we can choose set $I_1,I_2,I_3,I_4,I_5,I_6$ that satisfied the condition and for all $i$ s.t. $r_i\ge 0,i$ appears in at least $2$ sets from $I_1,I_2,I_3$ and at most $1$ set from $I_4,I_5,I_6$ and for all $i$ s.t. $r_i<0,i$ appears in at least $2$ sets from $I_4,I_5,I_6$ and at most $1$ set from $I_1,I_2,I_3$ then $\sum_{j=1}^6\left| {\mathop \sum \limits_{i \in I_j} {r_i}} \right|\ge \sum_{j=1}^3{\mathop \sum \limits_{i \in I_j} {r_i}}-\sum_{j=4}^6{\mathop \sum \limits_{i \in I_j} {r_i}}$ and in the expression of $R.S.H.$,if $r_i\ge 0,r_i$ will be count at least one time,but if $r_i<0,r_i$ will be count at most $-1$ time (that is,$|r_i|=-r_i$ will be count at least one time).Hence $\sum_{j=1}^6\left| {\mathop \sum \limits_{i \in I_j} {r_i}} \right|\ge \sum_{j=1}^3{\mathop \sum \limits_{i \in I_j} {r_i}}-\sum_{j=4}^6{\mathop \sum \limits_{i \in I_j} {r_i}}\ge \mathop \sum \limits_{i = 1}^n |{{r_i}}|$ and we are done.So it's enough to prove that the construction above is possible.
Now we will show that the construction is possible.
It's trivial that for $n=1,2$ this is possible,so let $n\ge 3$
For easier explanation,transfer $r_1,r_2,...,r_n$ into the sequence of consecutive grids where $i^{th}$ grid is white if $r_i\ge 0$ and black otherwise and let $K_j=\{r_i|i\in I_j\}$ for $j=1,2,3$
Now,define the singleton to be a grid that all its neighbors have different color from it.
And define $\text{toilet region}$ to be an interval with only black grids and singleton white grids,and if it's range from $a^{th}\rightarrow b^{th}$ grids,then $a=1$ or the $(a-1)^{th}$ grid must be non-singleton white grid and $b=n$ or the $(b+1)^{th}$ grid must be non-singleton white grid.[asy][asy]
draw((0,0)--(0,1)--(1,1)--(1,0)--cycle);
filldraw((0,0)--(0,1)--(1,1)--(1,0)--cycle,black,green+linewidth(1));
draw((1,0)--(1,1)--(2,1)--(2,0)--cycle);
filldraw((1,0)--(1,1)--(2,1)--(2,0)--cycle,black,green+linewidth(1));
draw((2,0)--(2,1)--(3,1)--(3,0)--cycle);
filldraw((2,0)--(2,1)--(3,1)--(3,0)--cycle,white,green+linewidth(1));
draw((3,0)--(3,1)--(4,1)--(4,0)--cycle);
filldraw((3,0)--(3,1)--(4,1)--(4,0)--cycle,black,green+linewidth(1));
label("$\underbrace {_{\, \, \, \, \quad \quad \qquad \qquad \qquad \qquad \qquad}}_{\; toilet \; region}$",(2,0),S);
[/asy][/asy]
Let $a_1^{th},a_2^{th},...,a_m^{th}$ grids be all the grids that aren't in any $\text{toilet region}$ in that order.
And let
$\{a_i|i\equiv 1,2 \pmod 3\}\subset K_1$
$\{a_i|i\equiv 2,3 \pmod 3\}\subset K_2$
$\{a_i|i\equiv 3,1 \pmod 3\}\subset K_3$
$\{r_i|r_i \text{ is a white singleton}\}\subset K_1,K_2,K_3$
$\{r_i|r_i \text{ is a black singleton}\}\cap (K_1\cup K_2\cup K_3)=\phi$
For the non-singleton grids in $\text{toilet region}$,we have three case:
$(I)$The $\text{toilet region}$ have length $3m \, \exists m\in\mathbb{Z}$
Let this $\text{toilet region}$ be ranged from $r_{h+1}\rightarrow r_{h+3m}$ and $r_h=a_l$
Then $\{r_{h+i}|i\equiv 2\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l\bmod 3}$
$\{r_{h+i}|i\equiv 1\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l+1\bmod 3}$
$\{r_{h+i}|i\equiv 3\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l+2\bmod 3}$.
$(II)$The $\text{toilet region}$ have length $3m+1 \, \exists m\in\mathbb{Z}$
Let this $\text{toilet region}$ be ranged from $r_{h+1}\rightarrow r_{h+3m+1}$ and $r_h=a_l$
Then $\{r_{h+i}|i\equiv 1\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l\bmod 3}$
$\{r_{h+i}|i\equiv 2\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l+1\bmod 3}$
$\{r_{h+i}|i\equiv 3\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l+2\bmod 3}$.
$(III)$The $\text{toilet region}$ have length $3m+2 \, \exists m\in\mathbb{Z}$
Let this $\text{toilet region}$ be ranged from $r_{h+1}\rightarrow r_{h+3m+2}$ and $r_h=a_l$
Then $\{r_{h+i}|i\equiv 3\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l\bmod 3}$
$\{r_{h+i}|i\equiv 1\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l+1\bmod 3}$
$\{r_{h+i}|i\equiv 2\pmod 3\}-\{r_i|r_i\text{ is a singleton}\}\subset K_{l+2\bmod 3}$.
Combine all condition above give $K_1,K_2,K_3$ and thus give $I_1,I_2,I_3$.
One can check that this satisfied the condition in part 1 and the hypothesis,so we can did the similar think to choose $I_4,I_5,I_6$ and we are done.
1.Equality can be obtain by $r_1=r_2=r_3=1,r_4=r_5=r_6=-1$
2.Don't mind about toilet,it just remind me about my school's urinal LOL.
3.Yay $100^{th}$ post!
Gems98
31.08.2017 22:09
Let $N=\{1,2,...,n\}$ WLOG, $\sum _{i=1}^{n} r_i \ge 0$ Let $P=\{i|r_i \ge 0\}$ $Q=\{i|r_i < 0\}$ $p= \sum _{i\in P} r_i$ $q= \sum _{i\in Q} r_i$ From the condition above, $p+q\ge0$ Consider $A=\{i | i \equiv 1 (mod3), i \in N \vee i \equiv 2 (mod3), i \in P\}$ $B=\{i | i \equiv 2 (mod3), i \in N \vee i \equiv 0 (mod3), i \in P\}$ $C=\{i | i \equiv 0 (mod3), i \in N \vee i \equiv 1 (mod3), i \in P\}$ It is easy to see that all of $A,B,C$ satisfy the condition. Consider $|\sum_ {i \in A} r_i|+|\sum_ {i \in B} r_i|+|\sum _{i \in C} r_i|\ge\sum_ {i \in A} r_i+\sum_ {i \in B} r_i+\sum _{i \in C} r_i$ $=\ge 2p+q$ $=\ge \frac{p-q}{2}$ $= \frac{\sum _{i=1}^{n} |r_i|}{2}$ Thus, there exists $I \in \{A,B,C\}$ such that $I$ satisfy the condition and $|\sum _{i \in I} r_i| \ge \frac{\sum _{i=1}^{n} |r_i|}{6}$
tastymath75025
03.09.2017 05:55
The above doesn't work because there can be a "gap" in each of $A,B,C$ of size at least three, which would contradict the condition $| I \cap \{i,i+1,i+2\}|\ge 1$. Let $A_1$ be the set of indices $i$ with $r_i \ge 0$, $i\equiv 1$ mod $3$ and define $A_2,A_3$ similarly. Also let $B_1$ be the set of indices $i$ with $r_i <0$, $i\equiv 1$ mod $3$ and define $B_2,B_3$ similarly. Let $a_1 = \displaystyle\sum_{i\in A_1} r_i$ and define $a_2,a_3,b_1,b_2,b_3$ similarly and let $s = \displaystyle\sum_i |r_i|$. Clearly $s = a_1+a_2+a_3-b_1-b_2-b_3$. WLOG suppose $a_1+a_2+a_3+b_1+b_2+b_3 \ge 0$. Then $a_1+a_2+a_3 \ge 0.5s$, hence for some two distinct $i,j$ we have $a_i+a_j \ge \dfrac{s}{3}$. Now suppose $a_i+a_j+b_i+b_j \ge 0$. Then note that $(a_i+a_j + b_i) + (a_i+a_j+b_j) \ge a_i+a_j \ge \dfrac{s}{3}$, so one of $a_i+a_j+b_i, a_i+a_j+b_i$ is at least $\dfrac{s}{6}$. WLOG suppose the first sum is; then setting $I = A_i\cup A_j\cup B_i$ works. Similarly if $a_i+a_j+b_i+b_j \le 0$ we consider $(a_i + b_i + b_j) + (a_j + b_i + b_j) \le -\dfrac{s}{3}$ to get another working set $I$.