Given is the positive integer $n > 2$. Real numbers $\mid x_i \mid \leq 1$ ($i = 1, 2, ..., n$) satisfying $\mid \sum_{i=1}^{n}x_i \mid > 1$. Prove that there exists positive integer $k$ such that $\mid \sum_{i=1}^{k}x_i - \sum_{i=k+1}^{n}x_i \mid \leq 1$.
Problem
Source: CWMO 2005-4
Tags: algebra unsolved, algebra
25.11.2005 22:54
It seems like this can be done as follows: suppose WLOG that $\sum_{i=1}^n x_i > 0$. Then, let $S_k = \sum_{i=1}^k x_i - \sum_{i=k+1}^n x_i$; we have $S_n = \sum_{i=1}^n x_i > 1$ and $S_0 = -\sum_{i=1}^n x_i < -1$. Suppose that we never have $-1 \le S_k \le 1$. Then let $k_0$ be the maximal value of $k$ for which $S_{k_0} < 0$; we know $k_0$ exists as $k = 0$ certainly satisfies the given property; additionally, $k_0 \ne n$ as $k = n$ does NOT satisfy the property, so $S_{k_0 + 1}$ is defined. By the assumption, we have $S_{k_0} < -1$, and as $k_0$ was the maximal value, we must have $S_{k_0 + 1} \ge 0$ and thus by the assumption $S_{k_0 + 1} > 1$. Thus $2 < S_{k_0 + 1} - S_{k_0} =$ $\left(\sum_{i=1}^{k_0+1} x_i - \sum_{i=k_0+2}^n x_i\right) - \left(\sum_{i=1}^{k_0} x_i - \sum_{i=k_0 + 1}^n x_i\right) =$ $2x_{k_0+1} \le 2|x_{k_0+1}| \le 2$ which is sort of false. Thus there exists a $k$ with the desired property, i.e. that $|S_k| \le 1$.
14.05.2008 02:31
wow beautiful problem and solution!
07.07.2022 05:28
Define $$S_k = \left|\sum_{i=1}^k x_i - \sum_{i=k+1}^n x_i\right|.$$In particular, denote $S_0 = -\sum x_i$ and $S_n = \sum x_i$. WLOG suppose that $S_n > 1$; then, we necessarily have $S_0 < -1$. Now, assume for the sake of contradiction that $|S_k| > 1$ for all $k$. Then there must exist some $k, k+1$ such that $S_k < -1$ and $S_{k+1} > 1$. But then $$2|x_{k+1}| > 1-(-1) = 2 \iff |x_{k+1}| > 1,$$which is a contradiction.