Let $x_1$, $x_2$, ..., $x_n$ be real numbers with arithmetic mean $X$. Prove that there is a positive integer $K$ such that for any integer $i$ satisfying $0\leq i<K$, we have $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j \leq X$. (In other words, prove that there is a positive integer $K$ such that the arithmetic mean of each of the lists $\left\{x_1,x_2,...,x_K\right\}$, $\left\{x_2,x_3,...,x_K\right\}$, $\left\{x_3,...,x_K\right\}$, ..., $\left\{x_{K-1},x_K\right\}$, $\left\{x_K\right\}$ is not greater than $X$.)
Problem
Source: Baltic Way 2004 Problem 4
Tags: inequalities, inequalities proposed
20.11.2004 14:06
yeah, it's my solution as well; however, all the things with shifting may be left out, just shoose the minimal $S_k$. then the $S_k$ is the weighted arithmetic mean of $S_l$ and $s_{l+1}+...+s_k$ for all $1\leq l<k$, and since $S_l\geq S_l$ we must have $s_{l+1}+...+s_k\leq S_l$ giving the desired inequality. [Edit: This post refers to Darij's solution in #3.]
25.10.2005 20:19
By "shifting" the numbers $x_1$, $x_2$, ..., $x_n$ (i. e. adding one and the same real number to each of them), we can make the arithmetic mean X of these numbers become 0. Then, we have to prove that there is a positive integer K such that for any natural number i satisfying $1\leq i<K$, we have $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j \leq 0$. But clearly, since K - i > 0, the inequality $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j \leq 0$ is equivalent to $\sum_{j=i+1}^{K} x_j \leq 0$. And now everything is clear: Choose K in such a way that among all possible sums $S_k = \sum_{j=1}^{k} x_j$, for $1\leq k\leq n$, the sum $S_K$ is the minimal one. Then, for any natural number i satisfying $1\leq i<K$, we have $S_K \leq S_i$, and thus $\sum_{j=i+1}^{K} x_j = \sum_{j=1}^{K} x_j - \sum_{j=1}^{i} x_j = S_K - S_i \leq 0$, so that the number K satisfies the condition of the problem. PS This is actually Darij's solution, re-posted.
01.08.2011 22:11
My solution, in a corrected version: By "shifting" the numbers $x_1$, $x_2$, ..., $x_n$ (i. e. adding one and the same real number to each of them), we can make the arithmetic mean $X$ of these numbers become $0$. So let us WLOG assume that $X=0$. Then, we have to prove that there is a positive integer $K$ such that for any integer $i$ satisfying $0\leq i<K$, we have $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j \leq 0$. But this is easy: For every $k\in\left\{1,2,...,n\right\}$, define a real number $S_k$ by $S_k = \sum_{j=1}^{k} x_j$. Choose an integer $K\in\left\{1,2,...,n\right\}$ in such a way that among all possible numbers $S_k$ for $1\leq k\leq n$, the number $S_K$ is the minimal one. Then, (1) any $i\in\left\{1,2,...,n\right\}$ satisfies $S_K\leq S_i$. In particular, this yields $S_K\leq S_n$. Since $S_n = \sum_{j=1}^{n} x_j = nX$ (because $X$ is the arithmetic mean of the numbers $x_1$, $x_2$, ..., $x_n$), this rewrites as $S_K\leq nX = 0$ (since $X=0$) (2) $=S_0$ (since $S_0 = \sum_{j=1}^0 x_j = 0$). Now, for any integer $i$ satisfying $0\leq i<K$, we have $S_K \leq S_i$ (in fact, this follows from (1) if $i>0$, and from (2) if $i=0$). In other words, for any integer $i$ satisfying $0\leq i<K$, we have $S_K - S_i \leq 0$. Thus, for any integer $i$ satisfying $0\leq i<K$, we have $\sum_{j=i+1}^{K} x_j = \underbrace{\sum_{j=1}^{K} x_j}_{=S_K} - \underbrace{\sum_{j=1}^{i} x_j}_{=S_i} = S_K - S_i$, so that $\frac{1}{K-i}\sum_{j=i+1}^{K} x_j = \underbrace{\frac{1}{K-i}}_{>0\text{ (since }K-i>0\text{)}}\underbrace{\left(S_K-S_i\right)}_{\leq 0}\leq 0$. Hence, the number $K$ satisfies the condition of the problem.
13.11.2011 07:21
my solution is quite different. we consider the opposite side,assuming that for any $k$,there exists $1\le f(k)\le k$ such that $\sum_{j=f(k)}^{k}x_j>x(k-f(k)+1)$(1) define a sequence $a_t$ as follows: $a_0=n,a_{t+1}=f(a_t)-1$ tricially,since $a_t$ is decreasing,there exists $l$,$a_l=1$ by letting $k=a_0,a_1,...,a_l$ in (1) and adding them,we get $x_1+x_2+...+x_n>nX$ contradiction!