Let $n \geq 2$ be a positive integer and $\{x_i\}_{i=0}^n$ a sequence such that not all of its elements are zero and there is a positive constant $C_n$ for which: (i) $x_1+ \dots +x_n=0$, and (ii) for each $i$ either $x_i\leq x_{i+1}$ or $x_i\leq x_{i+1} + C_n x_{i+2}$ (all indexes are assumed modulo $n$). Prove that a) $C_n\geq 2$, and b) $C_n=2$ if and only $2 \mid n$.
Problem
Source: Serbia TST 2017, Day 2, Problem 2
Tags: algebra, inequalities, Sequence
22.05.2017 15:52
I think I didnt understand the question. If xi=0 for all i so Cn can be zero.
22.05.2017 22:24
Hello This is my first post on AoPS, so let's hope I'm doing this right and please forgive bad wording Any hint on where I can learn how to use symbols is welcome. Let N={x_i <=0}, P={x_i >0), bN={x_(i-1)/x_i is in N), and aN={x_(i+1)/x_i is in N). Let's show that aN and bN are in P, by showing there's not i such that x_k and x_(k+1) are both in N. If i exist, x_(k-1) <= max(x_k, x_k+Cx_(k+1)) where C=C_n = x_k because C>0>=x_(k+1) <= 0, so x_(k-1) is in N. So by recurrency, every x_i is in N so nonpositive, and it exist x_m =/0 so x_1+...+x_n <=x_m <0. That's impossible. With s(X) the sum of X's elements, s(N U P) =s({x_i, 0<i<=n}) =0, so s(N) = -s(P). If x_i is in bN, x_i >0>=x_(i+1) so x_i <= x_(i+1)+Cx_(i+2). By summing these expressions for all x_i in bN, we have s(bN) <= s(N)+Cs(aN) <=> Cs(aN)-s(bN) >=s(P). Let's show that Cs(aN)-s(bN)<= max(1,C-1)s(P) by showing, for each k,m such that x_(k-1) and x_(k+m+1) are in N but {x_k, x_(k+1), ... ,x_(k+m)} is in P, that Cx_k-x_(k+m) <= max(1,C-1)(x_k+x_(k+1)+...+x_(k+m)). (Note that all indexes are modulo n.) For all i between k+1 and k+m-2, x_(i+2)>=0 so x_i<=x_(i+1)+Cx_(i+2) so Cx_k <= (C-1)x_k + x_(k+1)+Cx_(k+2) <= (C-1)x_k + x_(k+1)+(C-1)x_(k+2) + x_(k+3)+Cx_(k+4) <= (C-1)(x_k+x_(k+2)+...+x_(k+2a)) + x_(k+1)+x_(k+3)+...+x_(k+2a-1) + x_(k+2a) while 2a<=m <= max(1,C-1)(x_k+x_(k+1)+...+x_(k+2a)) + x_(k+2a) If m=2b with a=b we have immediately Cx_k-x_(k+m) <= max(1,C-1)(x_k+x_(k+1)+...+x_(k+m)). If m=2b+1, with a=b we have Cx_k-x_(k+m) <= max(1,C-1)(x_k+x_(k+1)+...+x_(k+m)) +x_(k+m-1)-max(2,C)x_(k+m) <= max(1,C-1)(x_k+x_(k+1)+...+x_(k+m)) +x_(k+m-1)-x_(k+m) <= max(1,C-1)(x_k+x_(k+1)+...+x_(k+m)) because with i=k+m-1 in (ii), since x_(k+m+1)<=0 we have x_(k+m-1)<=x_(k+m). So by summing for all positive sequences of x_i, the x_k being in aN and the x_(k+m) being in bN, we have max(1,C-1)s(P) >=Cs(aN)-s(bN) >=s(P) so max(1,C-1)>=1, that is equivalent to C>=2. So a) is prooved.
22.05.2017 23:29
@pab Welcome to AoPS; check these links out for learning LATEX, Using symbols on Aops and Symobls; Commands. It hardly takes minutes to understand.
23.05.2017 21:17
Thanks dovakin !
23.05.2017 23:07
Little error in my proof : $\max (1,C-1) \geq 1 \Leftrightarrow C \geq 2$ is false. But before in my proof, we have if m=2b, \begin{align*} C \cdot x_k - x_{k+m} &\leq (C-1) \cdot (\sum^b_{i=0} x_{k+2i}) + \sum^{b-1}_{i=0} x_{k+2i+1} \\ &< \max(1,C-1) \cdot (\sum^m_{j=0} x_{k+j}) \text{if } C<2\text{, else we have only a large inequality} \end{align*}And in the case m=b+1, in $\max(1,C-1) \cdot (x_k+x_{k+1}+\cdots+x_{k+m}) +x_{k+m-1}- \max(2,C) \cdot x_{k+m} \leq \max(1,C-1) \cdot (x_k+x_{k+1}+\cdots+x_{k+m}) +x_{k+m-1}-x_{k+m}$ we can replace $\leq$ by <. So in all cases if C<2 we have $C \cdot x_k - x_{k+m} < \max(1,C-1) \cdot (\sum^m_{j=0} x_{k+j})$. The end is the same, and $\max(1,C-1)>1 \Leftrightarrow C>2$. Contradiction. So $C \geq 2$.
24.05.2017 13:57
I think b) should be if $C_n=2$ then $n$ is even. It's not hard to show that there can't exist two consecutive negative value (consider the first backward positive value, we'll get $C_n<0$.) So, the sequence must consist of blocks of non-negative values and a negative value. For convenient, we let $C_n=C$. In the sequence, let's consider $$...,n_1,a_1,a_2,...,a_i,n_2,b_1,...$$where $n_1,n_2$ are negative value, others are non-negative. We have $$a_1\leq a_2+Ca_3,a_2\leq a_3+Ca_4,...,a_{i-2}\leq a_{i-1}+Ca_i$$and $a_{i-1}\leq a_i$ and $a_i\leq n_2+Cb_1$. Summing all inequalities of the form $a_i\leq n_2+Cb_1$ give us $$-(n_1+n_2+...)\leq C\times (a_1+b_1+...)-(a_i+b_?+...).$$So, the sum of absolute value non-negative terms in the sequence $\leq C\times (a_1+b_1+...)-(a_i+b_?+...)$. We also have $$Ca_1\leq \frac{C}{2}a_1+\frac{C}{2}(a_2+Ca_3)=\frac{C}{2}a_1+\frac{C}{2}a_2+\frac{C^2}{2}a_3\leq \frac{C}{2}a_1+\frac{C}{2}a_2+\frac{C^2}{4}a_3 +\frac{C^2}{4}(a_4+Ca_5)\leq ...$$ If $i=2k$ for some $k\in \mathbb{Z}^+$, we get $Ca_1\leq \sum_{j=1}^{k-1}{\Big( \frac{C^j}{2^j}a_{2j-1}+\frac{C^j}{2^j}a_{2j}\Big)}+\frac{C^k}{2^{k-1}}a_{2k-1}$ Then we use $a_{i-1}\leq a_i$ to get $$Ca_1-a_i\leq \sum_{j=1}^{k-1}{\Big( \frac{C^j}{2^j}a_{2j-1}+\frac{C^j}{2^j}a_{2j}\Big)} +\frac{C^k}{2^{k}}a_{2k-1}+\frac{C^k}{2^{k}}a_{2k}-a_i$$If $i=2k-1$ for some $k\in \mathbb{Z}^+$, we get $$Ca_1-a_i\leq \sum_{j=1}^{k-1}{\Big( \frac{C^j}{2^j}a_{2j-1}+\frac{C^j}{2^j}a_{2j}\Big)}+\frac{C^k}{2^{k-1}}a_{2k-1}-a_i$$ Suppose that $C<2$, we get, in both case, $$Ca_1-a_i\leq a_1+a_2+...+a_i$$with equality case if and only if $a_1=a_2=...=a_i=0$. Summing this inequality for each block give us the sum of all non-negative terms $\leq$ sum of all non-negative terms. But we can't achieve all equality cases since then all of the non-negative terms will be zero and then all terms will be so. This gives us the contradiction. So $C\geq 2$. Now suppose that $C=2$, we have sum of absolute value of non-negative terms $\leq$ the sum of the terms $$(a_1+a_2+...+a_{i-1})+\alpha a_i$$where $\alpha =0$ if $i$ is even and $=1$ if $i$ is odd. If $n$ is odd, there exist a block with odd terms and, for that block, we have $2\mid i$. So, to make the inequality holds, we must have $a_i=0$. In the light of that block, suppose the sequence is $$...,z_j,n_1,a_1,a_2,...,a_i,b_1,...$$We can prove backward from $a_i$ that all non-negative terms from $a_i$ to that point must be zero. This give the sum of all non-negative terms is zero, and so every term must be zero. Contradiction. So, if $C_n=2$ then $n$ is even, done.