Maths Olympiad Prep

Library / /23 of 27

Algebra Difficulty 7.0 National olympiad Prove it Romania

For each positive integer nn, find the largest real number CnC_n with the following property. Given any nn real-valued functions f1(x),f2(x),,fn(x)f_1(x), f_2(x), \dots, f_n(x) defined on the closed interval 0x10 \le x \le 1, one can find numbers x1,x2,,xnx_1, x_2, \dots, x_n, such that 0xi10 \le x_i \le 1, satisfying
f1(x1)+f2(x2)++fn(xn)x1x2xnCn. |f_1(x_1) + f_2(x_2) + \dots + f_n(x_n) - x_1x_2\dots x_n| \ge C_n.

Solution

First we will prove that Cnn12nC_n \ge \frac{n-1}{2n}, i.e. that for any nn functions f1,f2,,fn:[0,1]Rf_1, f_2, \dots, f_n : [0, 1] \to \mathbb{R}, there exist numbers x1,x2,,xnx_1, x_2, \dots, x_n in [0,1][0, 1] such that
f1(x1)+f2(x2)++fn(xn)x1x2xnn12n. |f_1(x_1) + f_2(x_2) + \dots + f_n(x_n) - x_1x_2\dots x_n| \ge \frac{n-1}{2n}.
For n=1n=1 this is trivial. For n2n \ge 2 suppose, contrariwise, that for all x1,x2,,xnx_1, x_2, \dots, x_n in [0,1][0, 1] we have
f1(x1)+f2(x2)++fn(xn)x1x2xn<n12n. |f_1(x_1) + f_2(x_2) + \dots + f_n(x_n) - x_1x_2\dots x_n| < \frac{n-1}{2n}.
Plugging in xi=1x_i = 1 for 1in1 \le i \le n, we get i=1nfi(1)1<n12n\left| \sum_{i=1}^{n} f_i(1) - 1 \right| < \frac{n-1}{2n}.
Plugging in xi=0x_i = 0 for 1in1 \le i \le n, we get i=1nfi(0)<n12n\left| \sum_{i=1}^{n} f_i(0) \right| < \frac{n-1}{2n}.
Plugging in (for every 1in1 \le i \le n) xi=0x_i = 0 and xj=1x_j = 1 for all jij \ne i, we get
fi(0)+jifj(1)<n12n. \left| f_i(0) + \sum_{j \ne i} f_j(1) \right| < \frac{n-1}{2n}.
Since
(n1)i=1nfi(1)=i=1n(fi(0)+jifj(1))i=1nfi(0), (n-1) \sum_{i=1}^{n} f_i(1) = \sum_{i=1}^{n} \left( f_i(0) + \sum_{j \ne i} f_j(1) \right) - \sum_{i=1}^{n} f_i(0),
by the triangle inequality we have
(n1)i=1nfi(1)<(n+1)n12n. (n-1) \left| \sum_{i=1}^{n} f_i(1) \right| < (n+1) \frac{n-1}{2n}.
On the other hand, by again the triangle inequality we have
1i=1nfi(1)+i=1nfi(1)1<n+12n+n12n=1, 1 \le \left| \sum_{i=1}^{n} f_i(1) \right| + \left| \sum_{i=1}^{n} f_i(1) - 1 \right| < \frac{n+1}{2n} + \frac{n-1}{2n} = 1,
which is a contradiction.

To prove that
Cn=n12n C_n = \frac{n-1}{2n}
is the largest constant, it will be sufficient to prove that for the nn (equal) functions
fi(x)=f(x):=xnnn12n2,1in, f_i(x) = f(x) := \frac{x^n}{n} - \frac{n-1}{2n^2}, \quad 1 \le i \le n,
and any nn numbers x1,x2,,xnx_1, x_2, \dots, x_n in [0,1][0, 1], we have
f(x1)+f(x2)++f(xn)x1x2xnn12n, \left| f(x_1) + f(x_2) + \cdots + f(x_n) - x_1 x_2 \cdots x_n \right| \le \frac{n-1}{2n},
equivalent to
n12n1ni=1nxini=1nxin12nn12n. -\frac{n-1}{2n} \le \frac{1}{n} \sum_{i=1}^{n} x_i^n - \prod_{i=1}^{n} x_i - \frac{n-1}{2n} \le \frac{n-1}{2n}.
The LHS inequality follows from the AM-GM inequality.

The RHS inequality is equivalent to
F(x)=F(x1,x2,,xn):=1ni=1nxini=1nxin1n F(\mathbf{x}) = F(x_1, x_2, \dots, x_n) := \frac{1}{n} \sum_{i=1}^{n} x_i^n - \prod_{i=1}^{n} x_i \le \frac{n-1}{n}
at all points x=(x1,x2,,xn)\mathbf{x} = (x_1, x_2, \dots, x_n) of the hypercube [0,1]n[0, 1]^n. Since FF is convex in every variable, its maximum is reached at some vertex v\mathbf{v} of the hypercube (point with xi=0x_i = 0 or xi=1x_i = 1, for all 1in1 \le i \le n). It is easy to see that for all such points we have F(v)n1nF(\mathbf{v}) \le \frac{n-1}{n}, which completes the proof.

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.