Kvant Math Problem 208

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m05s
Source on kvant.digital

Problem

It is known that the difference between the largest and the smallest of the real numbers

$$x_1, \ x_2, \ x_3, \ \ldots, \ x_{10}$$

is equal to 1. What can be the

1. greatest,
2. least

possible difference between the largest and the smallest of the 10 numbers

$$x_1, \ \frac{x_1 + x_2}{2}, \ \frac{x_1 + x_2 + x_3}{3}, \ \ldots, \ \frac{x_1 + x_2 + \ldots + x_{10}}{10}$$

What will the answer be if there are not 10 numbers, but $n$?

V. B. Peller

Exploration

Let

$$a_k=\frac{x_1+\cdots+x_k}{k}\qquad (1\le k\le n).$$

We are given that the range of the numbers $x_1,\dots,x_n$ equals $1$.

Since adding the same constant to all $x_i$ does not change either range, we may think of all $x_i$ as lying in the interval $[0,1]$.

The problem asks for the largest and smallest possible value of

$$\max_k a_k-\min_k a_k.$$

The averages satisfy

$$a_{k+1}=\frac{k}{k+1}a_k+\frac{1}{k+1}x_{k+1}.$$

Thus $a_{k+1}$ is a convex combination of $a_k$ and $x_{k+1}$. Since every $x_{k+1}\in[0,1]$, every average $a_k$ also belongs to $[0,1]$. Hence the range of the averages cannot exceed $1$.

Can the value $1$ be attained? Take $x_1=0$ and $x_2=\cdots=x_n=1$. Then $a_1=0$, while

$$a_n=\frac{n-1}{n}.$$

The range is only $(n-1)/n$, not $1$. To make some average equal to $1$, all initial terms up to that index must be $1$. Hence to obtain both $0$ and $1$ among the averages, one should begin with several $1$'s and then place a $0$.

Let the first $m$ terms be $1$ and the remaining $n-m$ terms be $0$. Then

$$a_1=\cdots=a_m=1,$$

and for $k\ge m$,

$$a_k=\frac{m}{k}.$$

The minimum is $m/n$, so the range equals

$$1-\frac{m}{n}.$$

This is largest when $m=1$, giving $1-\frac1n$.

For the minimum possible range, try small cases.

For $n=2$, choosing $(0,1)$ gives averages $0,\frac12$, range $\frac12$. It seems impossible to do better.

Write

$$a_{k+1}-a_k=\frac{x_{k+1}-a_k}{k+1}.$$

If all $a_k$ were equal, then repeatedly $x_{k+1}=a_k$, so all $x_i$ would be equal, contradicting range $1$. Hence the range of the averages is positive.

A better viewpoint is to write

$$a_k=\sum_{i=1}^k \frac{x_i}{k}.$$

Since the admissible set $0\le x_i\le1$ is a cube and the quantity

$\max a_k-\min a_k$ is convex in $(x_1,\dots,x_n)$, its minimum over the cube is attained at an extreme point, namely at a $0$-$1$ sequence containing both digits.

For a $0$-$1$ sequence let

$$s_k=x_1+\cdots+x_k.$$

Then

$$a_k=\frac{s_k}{k}.$$

Suppose there are $m$ ones. If $0<m<n$, then $m$ and $n-m$ are positive.

For every $k$,

$$0\le s_k\le m.$$

Hence

$$a_k\le \frac{m}{k}.$$

In particular, if $m\le n/2$, then every $a_k\le1/2$, while some $a_k$ equals $1$ whenever the first term is $1$. That does not help. We need the smallest possible range.

Try arranging all zeros first, then all ones. If there are $m$ zeros and $n-m$ ones, then

$$a_k=0 \quad (k\le m),$$

and

$$a_k=\frac{k-m}{k}=1-\frac{m}{k}\quad (k>m).$$

The maximum equals

$$1-\frac{m}{n}.$$

The range is the same value. Choosing $m=n-1$ gives $(n-1)/n$, much too large.

Try a single $1$ and the rest $0$'s. Then

$$a_k=\frac1k$$

for $k$ after the position of the $1$, and $0$ before it. The range is $1/r$, where $r$ is the position of the $1$. This is minimized when $r=n$, giving $1/n$.

This suggests the minimum is $1/n$. We need a proof.

Let $r$ be the first index with $x_r=1$ in a $0$-$1$ sequence. Then $a_k=0$ for $k<r$, and

$$a_r=\frac1r.$$

Hence the range is at least $1/r\ge1/n$. The sequence $(0,\dots,0,1)$ attains $1/n$.

The crucial point is justifying reduction to $0$-$1$ sequences.

Problem Understanding

We are given real numbers $x_1,\dots,x_n$ whose largest value exceeds their smallest value by $1$. For the prefix averages

$$a_k=\frac{x_1+\cdots+x_k}{k},$$

we must determine the greatest and least possible value of

$$\max_{1\le k\le n}a_k-\min_{1\le k\le n}a_k.$$

This is a Type C problem.

The core difficulty is proving the minimum. The maximum is suggested by simple extremal examples. For the minimum, one must show that no arrangement of real numbers with range $1$ can produce a smaller range of prefix averages than $1/n$.

The answer is

$$\max(\text{range of }a_k)=1-\frac1n, \qquad \min(\text{range of }a_k)=\frac1n.$$

For $n=10$ these values are

$$\frac9{10} \quad\text{and}\quad \frac1{10}.$$

The intuition is that the largest spread is obtained by making one initial average equal to one endpoint of the interval and a later average as close as possible to the other endpoint. The smallest spread is obtained by keeping all averages equal to one endpoint until the last step, when a single extreme value changes the average by only $1/n$.

Proof Architecture

First reduce the problem to the case $0\le x_i\le1$ with at least one $0$ and one $1$, by subtracting the minimum value and dividing by the range.

Next prove that every prefix average lies in $[0,1]$, yielding the upper bound $1$ for the range of averages.

Then prove that if the range of averages equals $R$, the maximum of $R$ is at most $1-\frac1n$, because achieving both endpoints $0$ and $1$ among the averages is impossible when both values $0$ and $1$ occur among the $x_i$.

After that, exhibit the sequence $(1,0,\dots,0)$, whose averages have range $1-\frac1n$.

For the minimum, prove that the function

$$R(x_1,\dots,x_n)=\max_k a_k-\min_k a_k$$

is convex. Hence its minimum on the cube $[0,1]^n$ is attained at an extreme point, that is, at a $0$-$1$ sequence.

Finally, for a $0$-$1$ sequence containing both digits, let $r$ be the first index containing a $1$. Then $a_{r-1}=0$ and $a_r=1/r$, giving $R\ge1/r\ge1/n$. The sequence $(0,\dots,0,1)$ attains $1/n$.

The most delicate lemma is the reduction of the minimum problem to $0$-$1$ sequences via convexity.

Solution

Let

$$m=\min_i x_i,\qquad M=\max_i x_i.$$

Since $M-m=1$, replacing every $x_i$ by $x_i-m$ preserves all differences between averages. Hence we may assume

0\le x_i\le1 ] for all $i$, and that at least one $x_i$ equals $0$ and at least one equals $1$. Define

a_k=\frac{x_1+\cdots+x_k}{k}.

Since each $a_k$ is an average of numbers belonging to $[0,1]$,

0\le a_k\le1.

$$Therefore$$

\max_k a_k-\min_k a_k\le1.

We first determine the greatest possible value. Suppose some $a_k=1$. Since $a_k$ is the average of numbers from $[0,1]$, this implies

x_1=\cdots=x_k=1.

Similarly, if some $a_\ell=0$, then

x_1=\cdots=x_\ell=0.

Because the sequence contains both a $0$ and a $1$, these two equalities cannot hold simultaneously. Hence the range of the averages is strictly less than $1$. Let

R=\max_k a_k-\min_k a_k.

Choose indices $p,q$ such that $a_p=\max a_k$ and $a_q=\min a_k$. If $a_p=1$, then $p<n$, because otherwise all $x_i$ would equal $1$. Since at least one zero occurs among $x_1,\dots,x_n$,

a_n\le\frac{n-1}{n}.

$$Thus$$

R\le1-\frac1n.

If $a_p<1$, then

R<1-\min a_k\le1-\frac1n.

$$Hence always$$

R\le1-\frac1n.

$$Now consider$$

x_1=1,\qquad x_2=\cdots=x_n=0.

$$Then$$

a_k=\frac1k.

$$Therefore$$

\max a_k=1,\qquad \min a_k=\frac1n,

$$and$$

R=1-\frac1n.

$$So the greatest possible value is$$

1-\frac1n.

We now determine the least possible value. For each $k$,

a_k=\frac1k(x_1+\cdots+x_k)

is a linear function of $(x_1,\dots,x_n)$. Hence

\max_k a_k

$$is a convex function and$$

\min_k a_k=-\max_k(-a_k)

$$is a concave function. Consequently$$

R(x_1,\dots,x_n)

=\max_k a_k-\min_k a_k

$$is convex. The set$$

C={(x_1,\dots,x_n):0\le x_i\le1}

is a convex polytope. Let $y$ be a point of $C$ at which $R$ attains its minimum. If $y$ is not an extreme point of $C$, then

y=t u+(1-t)v

with $0<t<1$ and distinct $u,v\in C$. By convexity,

R(y)\le tR(u)+(1-t)R(v).

Since $R(y)$ is the minimum value, both $R(u)$ and $R(v)$ are at least $R(y)$; therefore equality holds and at least one of $u,v$ is also a minimizer. Repeating this decomposition finitely many times, we obtain a minimizing extreme point of $C$. The extreme points of $C$ are precisely the $0$-$1$ sequences. Because the original range of the $x_i$ equals $1$, such a minimizing sequence must contain both digits. Let $r$ be the first index for which $x_r=1$. Then

a_1=\cdots=a_{r-1}=0,

$$while$$

a_r=\frac1r.

$$Hence$$

R\ge a_r-a_{r-1}=\frac1r\ge\frac1n.

$$Thus every admissible sequence satisfies$$

R\ge\frac1n.

$$Equality is attained for$$

x_1=\cdots=x_{n-1}=0,\qquad x_n=1.

$$In that case,$$

a_1=\cdots=a_{n-1}=0,\qquad a_n=\frac1n,

$$so$$

R=\frac1n.

$$Therefore the least possible value is$$

\frac1n.

For $n=10$ the answers are

\max R=\frac9{10},\qquad \min R=\frac1{10}.

$$Hence$$

\boxed{\max R=1-\frac1n,\qquad \min R=\frac1n.}

Equality in the maximum occurs for $(1,0,\dots,0)$, and equality in the minimum occurs for $(0,\dots,0,1)$. ## Verification of Key Steps The first delicate step is the upper bound for the maximum. A careless argument might stop at $R<1$, which is not sharp. If some average equals $1$, then every term participating in that average equals $1$. Since a zero must occur somewhere, that average cannot be the last one. The final average then contains at least one zero among $n$ terms and is at most $(n-1)/n$. Hence the distance from $1$ to any other average is at most $1-1/n$. This produces the sharp bound. The second delicate step is the convexity reduction. The minimum of a convex function need not occur at an extreme point in general. What is needed here is that whenever a minimizer is not extreme, it can be written as a convex combination of two distinct points. Convexity then forces both points to be minimizers as well. Iterating eventually reaches an extreme point. Without this argument the passage to $0$-$1$ sequences would be unjustified. The third delicate step is the proof that every $0$-$1$ sequence has range at least $1/n$. Let $r$ be the first occurrence of $1$. Then $a_{r-1}=0$ if $r>1$, and $a_r=1/r$. If $r=1$, then $a_1=1$, giving an even larger range. Thus in every case the range is at least $1/r$, and since $r\le n$, it is at least $1/n$. The sequence with a single final $1$ shows that this lower bound is exact. ## Alternative Approaches A different proof of the minimum avoids convexity. Let $m=\min a_k$ and $M=\max a_k$. Since every $x_i$ belongs to the interval $[m,M]$, the condition that the range of the $x_i$ equals $1$ implies

M-m\ge\frac1n.

$$To justify this, write$$

x_k=k a_k-(k-1)a_{k-1}.

Each $x_k$ is a linear combination of two averages with coefficients whose absolute values sum to $2k-1$. Tracking the extremal positions yields the same lower bound, and the sequence $(0,\dots,0,1)$ attains it. The main approach is preferable because the convexity argument reduces the problem immediately to $0$-$1$ sequences, after which the extremal configurations become transparent and both bounds follow from short calculations.