Kvant Math Problem 121
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m39s
Source on kvant.digital
Problem
Prove that for any $n$ real numbers $a_1$, $a_2$, ..., $a_n$, there exists a natural number $k \leq n$ such that each of the $k$ numbers $a_k$, $\dfrac{a_{k-1}+a_k}{2}$, $\dfrac{a_{k-2} + a_{k-1}+a_k}{3}$, ..., $\dfrac{a_1 + a_2+\ldots +a_k}{k}$ does not exceed $\dfrac{a_1 + a_2+\ldots +a_n}{n}$.
Exploration
Let
$$A=\frac{a_1+\cdots+a_n}{n}$$
be the average of all given numbers. The statement asks for an index $k$ such that every average of a terminal block ending at $k$ is at most $A$:
$$\frac{a_k}{1},\quad \frac{a_{k-1}+a_k}{2},\quad \dots,\quad \frac{a_1+\cdots+a_k}{k}.$$
For $n=1$ the claim is immediate.
For $n=2$, if $a_2\le A$, then $k=2$ works because the two required averages are $a_2$ and $A$. If $a_2>A$, then $a_1<A$, so $k=1$ works.
The condition resembles a statement about partial sums. Write
$$s_m=a_1+\cdots+a_m, \qquad s_0=0.$$
Then
$$\frac{a_{j}+\cdots+a_k}{k-j+1} \le A$$
is equivalent to
$$s_k-s_{j-1}\le (k-j+1)A.$$
Introducing
$$t_m=s_m-mA,$$
this becomes
$$t_k\le t_{j-1}.$$
Thus, for a fixed $k$, all the required inequalities hold exactly when
$$t_k\le t_0,t_1,\dots,t_{k-1}.$$
That means $t_k$ must be a minimum among the numbers $t_0,t_1,\dots,t_k$.
Now
$$t_n=s_n-nA=0.$$
Since the finite set ${t_0,t_1,\dots,t_n}$ has a minimum, choose $k$ to be the first index at which this minimum is attained. Then $t_k\le t_i$ for every $i<k$, which is precisely the condition above.
The crucial point is the equivalence between the required averages and the inequalities $t_k\le t_{j-1}$. Once this translation is made, the problem becomes a simple minimum principle for a finite sequence.
Problem Understanding
We are given real numbers $a_1,\dots,a_n$ and their overall average
$$A=\frac{a_1+\cdots+a_n}{n}.$$
We must prove that there exists an index $k\le n$ such that every average of a consecutive block ending at $k$ and beginning somewhere between $1$ and $k$ is at most $A$.
This is a Type B problem. The claim is already stated, and the task is to prove it.
The core difficulty is to reformulate the family of average inequalities into a single structural property of a sequence of modified partial sums.
Proof Architecture
Define partial sums $s_m=a_1+\cdots+a_m$ and modified sums $t_m=s_m-mA$.
The first lemma is that, for any $j\le k$, the inequality
$$\frac{a_j+\cdots+a_k}{k-j+1}\le A$$
is equivalent to
$$t_k\le t_{j-1}.$$
This follows by expressing the block sum as $s_k-s_{j-1}$ and rearranging.
The second lemma is that if $k$ is an index where $t_m$ attains its minimum on ${0,1,\dots,n}$, then $t_k\le t_i$ for every $i<k$.
This is the definition of a minimum.
The final step is to combine the two lemmas. Since the finite set ${t_0,\dots,t_n}$ has a minimum, choosing an index where it is attained yields all required inequalities.
The lemma most likely to fail under scrutiny is the first one, because every subsequent step depends on the exact algebraic equivalence.
Solution
Let
$$A=\frac{a_1+\cdots+a_n}{n}.$$
For $m=0,1,\dots,n$, define
$$s_m=a_1+\cdots+a_m,$$
with $s_0=0$, and then define
$$t_m=s_m-mA.$$
Since
$$s_n=a_1+\cdots+a_n=nA,$$
we have
$$t_n=0.$$
Consider any indices $j$ and $k$ with $1\le j\le k\le n$. The inequality
$$\frac{a_j+\cdots+a_k}{k-j+1}\le A$$
is equivalent to
$$a_j+\cdots+a_k\le (k-j+1)A.$$
Using partial sums,
$$s_k-s_{j-1}\le (k-j+1)A.$$
Rearranging gives
$$s_k-kA\le s_{j-1}-(j-1)A,$$
that is,
$$t_k\le t_{j-1}.$$
Hence, for a fixed index $k$, all inequalities
$$a_k\le A,$$
$$\frac{a_{k-1}+a_k}{2}\le A,$$
$$\dots,$$
$$\frac{a_1+\cdots+a_k}{k}\le A$$
hold simultaneously if and only if
$$t_k\le t_0,t_1,\dots,t_{k-1}.$$
Now choose $k$ such that $t_k$ is a minimum of the finite set
$${t_0,t_1,\dots,t_n}.$$
Then
$$t_k\le t_i$$
for every $i<k$. Taking $i=j-1$, where $1\le j\le k$, we obtain
$$t_k\le t_{j-1}.$$
By the equivalence established above,
$$\frac{a_j+\cdots+a_k}{k-j+1}\le A$$
for every $j=1,2,\dots,k$.
These are exactly the inequalities required in the statement. Thus such an index $k$ exists.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the passage from averages to modified partial sums. Starting from
$$\frac{a_j+\cdots+a_k}{k-j+1}\le A,$$
multiplication by the positive number $k-j+1$ gives
$$s_k-s_{j-1}\le (k-j+1)A.$$
Moving the terms involving $A$ to opposite sides yields
$$s_k-kA\le s_{j-1}-(j-1)A.$$
No inequality direction changes occur because only addition and subtraction are used. This establishes the exact equivalence
$$\frac{a_j+\cdots+a_k}{k-j+1}\le A \iff t_k\le t_{j-1}.$$
A common error is to replace $(k-j+1)A$ by $(k-j)A$, which destroys the correspondence.
The second delicate step is the choice of $k$. The proof requires an index where $t_m$ attains a minimum on the entire set ${0,\dots,n}$. Since the set is finite, such an index exists. From minimality,
$$t_k\le t_i$$
for every $i<k$. This is precisely the condition needed after substituting $i=j-1$.
Another possible mistake is to choose a local minimum rather than a global minimum. A local minimum does not guarantee $t_k\le t_{j-1}$ for every earlier index.
Alternative Approaches
A geometrical interpretation is available. Plot the points
$$(m,s_m),\qquad m=0,1,\dots,n.$$
The line joining $(0,0)$ and $(n,s_n)$ has slope $A$. The quantity $t_m=s_m-mA$ is the vertical displacement of the point $(m,s_m)$ from this line. Choose a point with minimal displacement. Every earlier point lies on or above the line through this chosen point that is parallel to the average line. Translating this slope condition back into coordinates gives exactly the required inequalities for all terminal blocks ending at that index.
The modified partial sum method is preferable because it converts the problem directly into a minimum principle for a finite sequence and avoids introducing geometric language that must later be translated back into algebra.