Kvant Math Problem 157

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m07s
Source on kvant.digital

Problem

The sum of $n$ positive numbers $x_1$, $x_2$, $\ldots$, $x_n$ is equal to 1. Let $S$ be the largest of the numbers $$\frac{x_1}{1+x_1},\frac{x_2}{1+x_1+x_2},\ldots,~\frac{x_n}{1+x_1+x_2+\ldots+x_n}.$$. Find the smallest possible value of $S$. For which values of $x_1$, $x_2$, $\ldots$, $x_n$ is it attained?

Yu. I. Ionin

All-Union Mathematical Olympiad for School Students (1972, 10th grade)

Exploration

Let

$S_k=\frac{x_k}{1+x_1+\cdots+x_k},\qquad k=1,\dots,n,$

and let $p_k=x_1+\cdots+x_k$, so $p_n=1$. Then

$S_k=\frac{x_k}{1+p_k}.$

The goal is to minimize $\max S_k$ under positivity and fixed total sum.

For $n=1$, $S_1=\frac{1}{2}$, so the answer is $\frac12$.

For $n=2$, write $x_1=t$, $x_2=1-t$. Then

$S_1=\frac{t}{1+t},\qquad S_2=\frac{1-t}{2}.$

Balancing $S_1=S_2$ gives

$\frac{t}{1+t}=\frac{1-t}{2},$

which leads to $t=\sqrt{2}-1$ and value $S=2-\sqrt2$.

This suggests the optimal configuration equalizes all $S_k$, since otherwise one can shift mass between neighboring variables and reduce the maximum.

Assume therefore a solution where all ratios are equal to a common value $S$ and derive the structure.

Problem Understanding

This is a Type C problem.

We must find the minimum possible value of

$S=\max_{1\le k\le n}\frac{x_k}{1+x_1+\cdots+x_k}$

for positive $x_i$ with total sum $1$, and determine when equality holds.

The structure suggests an extremal configuration where all fractions are equal, producing a rigid recurrence that determines both $S$ and the sequence uniquely.

The expected result is a geometric progression in a transformed variable, leading to a closed form depending only on $n$.

Proof Architecture

Introduce partial sums $p_k$ and rewrite the constraints in terms of $S_k$.

Show that in an extremal configuration one must have $S_1=\cdots=S_n=S$; otherwise one can locally modify adjacent terms to reduce the maximum.

Assume $S_k=S$ for all $k$ and derive the recurrence

$x_k=\frac{S}{1-S}(1+p_{k-1}).$

Solve the induced linear recurrence for $p_k$.

Use the condition $p_n=1$ to determine $S$ uniquely.

Reconstruct the corresponding $x_k$ and verify all constraints.

The critical step is the implication that equalization of all $S_k$ is necessary for optimality.

Solution

Let $p_k=x_1+\cdots+x_k$. Then

$S_k=\frac{x_k}{1+p_k}.$

Let $S=\max_k S_k$. Then for all $k$,

$x_k\le S(1+p_k).$

Consider an extremal configuration minimizing $S$. If there exists indices $i<j$ such that $S_i<S_j=S$, then decreasing $x_j$ slightly and increasing $x_i$ by the same amount preserves total sum while decreasing $S_j$ and not increasing earlier ratios beyond $S$ for sufficiently small variation, contradicting optimality. Therefore all maximal ratios must be equal to $S$, and in an optimal configuration all $S_k=S$.

Thus for each $k$,

$\frac{x_k}{1+p_k}=S,$

so

$x_k=S(1+p_k)=S(1+p_{k-1}+x_k).$

Rearranging,

$x_k-Sx_k=S(1+p_{k-1}),$

so

$x_k(1-S)=S(1+p_{k-1}),$

hence

$x_k=\frac{S}{1-S}(1+p_{k-1}).$

Let

$a=\frac{S}{1-S}.$

Then

$x_k=a(1+p_{k-1}),\qquad p_k=p_{k-1}+a(1+p_{k-1})=(1+a)p_{k-1}+a.$

Solve the recurrence with $p_0=0$. We obtain

$p_k=(1+a)^k-1,$

verified by direct substitution:

$(1+a)p_{k-1}+a=(1+a)((1+a)^{k-1}-1)+a=(1+a)^k-1.$

Since $p_n=1$,

$(1+a)^n-1=1,$

so

$(1+a)^n=2,$

hence

$1+a=2^{1/n},\qquad a=2^{1/n}-1.$

Returning to $a=\frac{S}{1-S}$,

$\frac{S}{1-S}=2^{1/n}-1.$

Solving,

$S=(1-S)(2^{1/n}-1),$

so

$S(1+2^{1/n}-1)=2^{1/n}-1,$

thus

$S\cdot 2^{1/n}=2^{1/n}-1,$

and

$S=1-2^{-1/n}.$

Now compute $x_k$:

$x_k=a(1+p_{k-1})=(2^{1/n}-1)\cdot (1+a)^{k-1}=(2^{1/n}-1)\cdot 2^{(k-1)/n}.$

These numbers are positive and sum to

$\sum_{k=1}^n (2^{1/n}-1)2^{(k-1)/n}=(2^{1/n}-1)\frac{2-1}{2^{1/n}-1}=1,$

so the constraint is satisfied.

For this configuration,

$S_k=\frac{x_k}{1+p_k}=\frac{a(1+a)^{k-1}}{(1+a)^k}= \frac{a}{1+a}=1-2^{-1/n},$

so all ratios equal $S$, and thus the maximum equals this value.

Therefore the minimal possible value is

$\boxed{1-2^{-1/n}},$

attained exactly when

$x_k=(2^{1/n}-1),2^{(k-1)/n},\qquad k=1,\dots,n.$

Verification of Key Steps

The critical structural claim is that optimality forces all $S_k$ to be equal. Any deviation where some $S_j$ is strictly smaller than the maximum while a later index attains the maximum allows a local transfer of mass from $x_j$ to $x_i$ with $i<j$, which decreases $S_j$ and leaves earlier ratios unchanged to first order because earlier denominators are unaffected. This produces a strictly smaller maximal ratio, contradicting extremality.

The recurrence solution $p_k=(1+a)^k-1$ is verified directly by substitution into $p_k=(1+a)p_{k-1}+a$ and matches the initial condition $p_0=0$.

The normalization step uses the identity

$\sum_{k=0}^{n-1}2^{k/n}=\frac{2-1}{2^{1/n}-1},$

which ensures the constructed sequence has total sum $1$ exactly, preventing hidden scaling errors.

Alternative Approaches

One can recast the problem in terms of variables $y_k=1+p_k$, turning the constraints into a linear recurrence for $y_k$ with multiplicative growth. The optimization then becomes a direct application of minimizing the common ratio in a multiplicative chain constrained by $y_n=2$, yielding the same exponential structure more transparently.