
Problem 2. For each positive integer $n$, find the largest real number $C_{n}$ with the following property. Given any $n$ real-valued functions $f_{1}(x), f_{2}(x), \ldots, f_{n}(x)$ defined on the closed interval $0 \leq x \leq 1$, one can find numbers $x_{1}, x_{2}, \ldots, x_{n}$, such that $0 \leq x_{i} \leq 1$, satisfying

$$
\left|f_{1}\left(x_{1}\right)+f_{2}\left(x_{2}\right)+\cdots+f_{n}\left(x_{n}\right)-x_{1} x_{2} \cdots x_{n}\right| \geq C_{n} .
$$

## Serbia, Marko Radovanovic


Solution. First we will prove that $C_{n} \geq \frac{n-1}{2 n}$, i.e. that for any $n$ functions $f_{1}, f_{2}, \ldots, f_{n}:[0,1] \rightarrow \mathbb{R}$, there exist numbers $x_{1}, x_{2}, \ldots, x_{n}$ in $[0,1]$ such that

$$
\left|f_{1}\left(x_{1}\right)+f_{2}\left(x_{2}\right)+\cdots+f_{n}\left(x_{n}\right)-x_{1} x_{2} \cdots x_{n}\right| \geq \frac{n-1}{2 n}
$$

For $n=1$ this is trivial. For $n \geq 2$ suppose, contrariwise, that for all $x_{1}, x_{2}, \ldots, x_{n}$ in $[0,1]$ we have

$$
\left|f_{1}\left(x_{1}\right)+f_{2}\left(x_{2}\right)+\cdots+f_{n}\left(x_{n}\right)-x_{1} x_{2} \cdots x_{n}\right|<\frac{n-1}{2 n}
$$

Plugging in $x_{i}=1$ for $1 \leq i \leq n$, we get $\left|\sum_{i=1}^{n} f_{i}(1)-1\right|<\frac{n-1}{2 n}$.

Plugging in $x_{i}=0$ for $1 \leq i \leq n$, we get $\left|\sum_{i=1}^{n} f_{i}(0)\right|<\frac{n-1}{2 n}$.

Plugging in (for every $1 \leq i \leq n$ ) $x_{i}=0$ and $x_{j}=1$ for all $j \neq i$, we get $\left|f_{i}(0)+\sum_{j \neq i} f_{j}(1)\right|<\frac{n-1}{2 n}$. Since

$$
(n-1) \sum_{i=1}^{n} f_{i}(1)=\sum_{i=1}^{n}\left(f_{i}(0)+\sum_{j \neq i} f_{j}(1)\right)-\sum_{i=1}^{n} f_{i}(0)
$$

by the triangle inequality we have

$$
(n-1)\left|\sum_{i=1}^{n} f_{i}(1)\right|<(n+1) \frac{n-1}{2 n}
$$

On the other hand, by again the triangle inequality we have

$$
1 \leq\left|\sum_{i=1}^{n} f_{i}(1)\right|+\left|\sum_{i=1}^{n} f_{i}(1)-1\right|<\frac{n+1}{2 n}+\frac{n-1}{2 n}=1
$$

which is a contradiction.

To prove that $C_{n}=\frac{n-1}{2 n}$ is the largest constant, it will be sufficient to prove that for the $n$ (equal) functions

$$
f_{i}(x)=f(x):=\frac{x^{n}}{n}-\frac{n-1}{2 n^{2}}, \quad \mathrm{l} \leq i \leq n
$$

and any $n$ numbers $x_{1}, x_{2}, \ldots, x_{n}$ in $[0,1]$, we have

$$
\left|f\left(x_{1}\right)+f\left(x_{2}\right)+\cdots+f\left(x_{n}\right)-x_{1} x_{2} \cdots x_{n}\right| \leq \frac{n-1}{2 n}
$$

equivalent to

$$
-\frac{n-1}{2 n} \leq \frac{1}{n} \sum_{i=1}^{n} x_{i}^{n}-\prod_{i=1}^{n} x_{i}-\frac{n-1}{2 n} \leq \frac{n-1}{2 n}
$$

The LHS inequality follows from the AM-GM inequality. The RHS inequality is equivalent to

$$
F(\boldsymbol{x})=F\left(x_{1}, x_{2}, \ldots, x_{n}\right):=\frac{1}{n} \sum_{i=1}^{n} x_{i}^{n}-\prod_{i=1}^{n} x_{i} \leq \frac{n-1}{n}
$$

at all points $x=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ of the hypercube $[0,1]^{n}$. Since $F$ is convex in every variable, its maximum is reached at some vertex $\boldsymbol{\nu}$ of the hypercube (point with $x_{i}=0$ or $x_{i}=1$,
for all $1 \leq i \leq n$ ). It is easy to see that for all such points we have $F(\boldsymbol{v}) \leq \frac{n-1}{n}$, which completes the proof.

Remarks. The choice of the functions

$$
f_{i}(x):=\frac{x^{n}}{n}-\frac{n-1}{2 n^{2}}, 1 \leq i \leq n
$$

could be justified by the fact that if we try all $f_{i}=f$ and all $x_{i}=x$, the relation becomes $\left|n f(x)-x^{n}\right| \geq C_{n}$, as tight as possible for some $x \in[0,1]$. Then $f(x)=\frac{x^{n}}{n}-\frac{1}{n} C_{n}$ is a potential candidate.

On a different note, RHS inequality above is equivalent to

$$
F(x)=F\left(x_{1}, x_{2}, \ldots, x_{n}\right):=\frac{1}{n} \sum_{i=1}^{n} x_{i}^{n}-\prod_{i=1}^{n} x_{i} \geq 0
$$

at all points $\boldsymbol{x}=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ of the hypercube $[0,1]^{n}$, and this again may be justified by $F$ being convex, since it can be easily seen that $F(\boldsymbol{v}) \geq 0$ at any vertex $\boldsymbol{v}$ of the hypercube, so one may use a unifying argument for both sides of that inequality.
