Maths Olympiad Prep

Library / /8 of 18

Algebra Difficulty 8.1 Shortlist Prove it Romania

Given a positive integer number nn, determine the minimum of
max{x11+x1,x21+x1+x2,,xn1+x1+x2++xn}, \max \left\{ \frac{x_1}{1+x_1}, \frac{x_2}{1+x_1+x_2}, \dots, \frac{x_n}{1+x_1+x_2+\dots+x_n} \right\},
as x1,x2,,xnx_1, x_2, \dots, x_n run through all non-negative real numbers which add up to 1.

Solution

Let
f(x1,x2,,xn)=max{xk1+x1+x2++xk:k=1,2,,n}, f(x_1, x_2, \dots, x_n) = \max \left\{ \frac{x_k}{1 + x_1 + x_2 + \dots + x_k} : k = 1, 2, \dots, n \right\},
where x10,x20,,xn0x_1 \ge 0, x_2 \ge 0, \dots, x_n \ge 0 and x1+x2++xn=1x_1 + x_2 + \dots + x_n = 1, and notice that
a11+a1=a21+a1+a2==an1+a1+a2++an \frac{a_1}{1+a_1} = \frac{a_2}{1+a_1+a_2} = \dots = \frac{a_n}{1+a_1+a_2+\dots+a_n}
for a unique nn-tuple (a1,a2,,an)(a_1, a_2, \ldots, a_n) of non-negative real numbers which add up to 1,
namely, ak=2k/n2(k1)/na_k = 2^{k/n} - 2^{(k-1)/n}, k=1,2,,nk = 1, 2, \ldots, n, in which case $f(a_1, a_2, \ldots, a_n) =
1 - 2^{-1/n}.Nowlet. Now let (x_1, x_2, \ldots, x_n) \neq (a_1, a_2, \ldots, a_n),wherethe, where the x_i$ are non-
negative real numbers which add up to 1. Since x1+x2++xn=a1+a2++anx_1+x_2+\cdots+x_n = a_1+a_2+\cdots+a_n,
it follows that xk>akx_k > a_k for some index kk. Let m=min{k:xk>ak}m = \min\{k : x_k > a_k\}. Then xkakx_k \le a_k,
k<mk < m, so
f(x1,x2,,xn)xm1+x1+x2++xm>am1+a1+a2++am=f(a1,a2,,an). f(x_1, x_2, \dots, x_n) \ge \frac{x_m}{1 + x_1 + x_2 + \dots + x_m} \\ \qquad > \frac{a_m}{1 + a_1 + a_2 + \dots + a_m} = f(a_1, a_2, \dots, a_n).
Consequently, the required minimum is 121/n1 - 2^{-1/n}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.