Given a positive integer number $n$, determine the minimum of \[\max \left\{\dfrac{x_1}{1 + x_1},\, \dfrac{x_2}{1 + x_1 + x_2},\, \cdots,\, \dfrac{x_n}{1 + x_1 + x_2 + \cdots + x_n}\right\},\] as $x_1, x_2, \ldots, x_n$ run through all non-negative real numbers which add up to $1$. Kvant Magazine
Problem
Source: Romania TST 2 2010, Problem 1
Tags: induction, strong induction, inequalities proposed, inequalities
ACCCGS8
28.08.2012 15:12
The answer is $1-2^{-\frac{1}{n}}$. $x_m = 2^{\frac{m}{n}} - 2^{\frac{m-1}{n}}$ for all $1 \le m \le n$ gives this value. To show that values less than $1-2^{-\frac{1}{n}}$ cannot be attained, assume for a contradiction that $\frac{x_1}{1+x_1}, \frac{x_2}{1+x_1+x_2}, \cdots, \frac{x_{n}}{1+x_{1}+x_{2}+\cdots+x_{n}}\} < 1-2^{-\frac{1}{n}}$. It is quite easy to prove by strong induction on $k$ that for all $1 \le k \le n$, $x_k < 2^{\frac{k}{n}} - 2^{\frac{k-1}{n}}$. Then $x_1 + x_2 + \cdots + x_n < 1$, yielding a contradiction. Thus the minimum value of \[ \max\{\frac{x_{1}}{1+x_{1}},\,\frac{x_{2}}{1+x_{1}+x_{2}},\,\cdots,\,\frac{x_{n}}{1+x_{1}+x_{2}+\cdots+x_{n}}\} \] is $1-2^{-\frac{1}{n}}$. I'm very interested to see the official solution to this problem. mavropnevma, could you please post the official solution? And thanks for posting the official solution to some of the other Romanian TST 2010 problems.
mavropnevma
28.08.2012 15:33
Let
\[f(x_1, x_2, \ldots, x_n) = \max \left\{\dfrac{x_k}{1 + x_1 + x_2 + \cdots + x_k} : k = 1, 2, \ldots, n\right\},\]
where $x_1 \geq 0$, $x_2 \geq 0$, $\ldots$, $x_n \geq 0$ and $x_1 + x_2 + \cdots + x_n = 1$, and notice that
\[\dfrac{a_1}{1 + a_1} = \dfrac{a_2}{1 + a_1 + a_2} = \cdots = \dfrac{a_n}{1 + a_1 + a_2 + \cdots + a_n}\]
for a unique $n$-tuple $(a_1, a_2, \ldots, a_n)$ of non-negative real numbers which add up to $1$, namely, $a_k = 2{k/n} - 2^{(k-1)/n}$, $k = 1, 2, \ldots, n$, in which case $f(a_1, a_2, \ldots, a_n) = 1 - 2^{-1/n}$. Now let $(x_1, x_2, \ldots, x_n) \neq (a_1, a_2, \ldots, a_n)$, where the $x_i$ are non-negative real numbers which add up to $1$. Since $x_1 + x_2 + \cdots + x_n = a_1 + a_2 + \cdots + a_n$, it follows that $x_k > a_k$ for some index $k$. Let $m = \min\{k : x_k > a_k\}$. Then $x_k \leq a_k$, $k < m$, so
\[\begin{aligned}f(x_1, x_2, \ldots, x_n) & \geq \dfrac{x_m}{1 + x_1 + x_2 + \cdots + x_m} \\ & > \dfrac{a_m}{1 + a_1 + a_2 + \cdots + a_m} = f(a_1, a_2, \ldots, a_n). \end{aligned}
\]
Consequently, the required minimum is $1 - 2^{-1/n}$.
subham1729
09.09.2012 14:47
Let $y_k=1+x_1+...+x_k$ now call maximum as $m$. So now note $\frac {y_{k-1}}{y_k}\geq 1-m$ Now by telescoping product $s\geq 1-2^{\frac {-1}{n}}$ so min at $x_k=2^{\frac {k}{n}}-2^{\frac {k-1}{n}}$
euclides05
11.02.2023 13:02
Suppose that $\frac{x_1}{1+x_1}< 1-\frac{1}{\sqrt[n]{2}}, \frac{x_2}{1+x_1+x_2}< 1-\frac{1}{\sqrt[n]{2}},..., \frac{x_n}{1+x_1+...+x_n}< 1-\frac{1}{\sqrt[n]{2}}$ Multiplying each of these inequalities by $-1$ and adding $1$ to each side yields $\frac{1}{1+x_1}>\frac{1}{\sqrt[n]{2}}, \frac{1+x_1}{1+x_1+x_2}>\frac{1}{\sqrt[n]{2}},..., \frac{1+x_1+...+x_{n-1}}{1+x_1+...+x_n}>\frac{1}{\sqrt[n]{2}}$ so by telescoping we get $\frac{1}{1+x_1+...+x_n}= \frac {1}{2}>(\frac{1}{\sqrt[n]{2}})^n$, which is clearly absurd. Therefore, we proved that $ max\{ \frac{x_1}{1+x_1}, \frac{x_2}{1+x_1+x_2},...,\frac{x_n}{1+x_1+...+x_n} \}\ge 1-\frac{1}{\sqrt[n]{2}}$ which is the minimum desired value since equality holds for $x_i= 2^{\frac{i}{n}}-2^{\frac{i-1}{n}}, i=1,..,n$.