Let $n$ be a positive integer, $x_1,x_2,\ldots,x_{2n}$ be non-negative real numbers with sum $4$. Prove that there exist integer $p$ and $q$, with $0 \le q \le n-1$, such that \[ \sum_{i=1}^q x_{p+2i-1} \le 1 \mbox{ and } \sum_{i=q+1}^{n-1} x_{p+2i} \le 1, \]where the indices are take modulo $2n$. Note: If $q=0$, then $\sum_{i=1}^q x_{p+2i-1}=0$; if $q=n-1$, then $\sum_{i=q+1}^{n-1} x_{p+2i}=0$.
Problem
Source: 2022 China TST, Test 4 P5
Tags: algebra, Inequality, combinatorics
01.05.2022 11:18
Sketch and unLaTeXed since I am on mobile: Let S be the sum of x_i where i is even. Similarly let T be the sum of x_i where i is odd. WLOG S>=T. Consider a function f:1,...,n->R such that f(i)=S*x_(2i+1)-T*x_(2i). Then sum f(i)=0 so by gas station lemma, there exists an index a such that f(a),f(a+1),...,f(a+n-1) are all nonnegative. Pick a maximal nonnegative integer b such that x_(2a)+x_(2a+1)+...+x_(2a+2b-1)<=1+T/S. Since 1+T/S<=2 it follows that b<n. It follows that x_(2a)+x_(2a+2)+...+x_(2a+2b-2)<=1. Then prove that x_(2a+2b+1)+x_(2a+2b+3)+...+x_(2a+2n-1)<=(3-T/S)*T/(S+T) Since S+T=4 this boils down to (T-2)^2>=0. So (p,q)=(2a+2b,n-1-b)$ works.
02.05.2022 13:21
The indices in the previous post are not accuate. However, it is easy to fix the solution.
03.05.2022 08:08
03.05.2022 09:58
I think this should be "or" according to De Morgan rules, so this makes the solution incorrect.
03.05.2022 18:31
The index is shifted by 1 though.. Ok, since $q$ is the largest integer st $\sum_{j=1}^q x_{p+2j-1}\le 1$ it follows that $\sum_{i=1}^{q+1} x_{p+2j-1}>1$. If $\sum_{i=q+1}^{n-1} x_{p+2j}\le 1$, we are done because this pair (p,q) works. Therefore, for each p there exists q such that $\sum_{i=1}^{q+1} x_{p+2j-1}>1$ AND $\sum_{i=q+1}^{n-1} x_{p+2j}\le 1$ Yes, it is AND not or
04.05.2022 10:59
Here is another version of my proof above, which is simpler in my opinion. Moreover the gas station lemma is proved for completeness.
01.06.2024 11:52
Now, for my third solution, which is in my opinion a more readable version of my second solution.