Local Mathematical Competitions

First we will prove that $C_n\ge \frac{n-1}{2n}$, i.e. that for any $n$ functions $f_1,f_2,\dots ,f_n:[0,1]\to \mathbb{R}$, there exist numbers $x_1,x_2,\dots ,x_n$ in $[0,1]$ such that $$|f_1(x_1)+f_2(x_2)+\cdots +f_n(x_n)-x_1{x}_2\dots x_n|\ge \frac{n-1}{2n}.$$ For $n=1$ this is trivial. For $n\ge 2$ suppose, contrariwise, that for all $x_1,x_2,\dots ,x_n$ in $[0,1]$ we have $$|f_1(x_1)+f_2(x_2)+\cdots +f_n(x_n)-x_1{x}_2\dots x_n|<\frac{n-1}{2n}.$$ Plugging in $x_i=1$ for $1\le i\le n$, we get $\left|{\sum }_{i=1}^n{f}_i(1)-1\right|<\frac{n-1}{2n}$. Plugging in $x_i=0$ for $1\le i\le n$, we get $\left|{\sum }_{i=1}^n{f}_i(0)\right|<\frac{n-1}{2n}$. Plugging in (for every $1\le i\le n$) $x_i=0$ and $x_j=1$ for all $j\ne i$, we get $$\left|f_i(0)+\sum _{j\ne i}{f}_j(1)\right|<\frac{n-1}{2n}.$$ Since $$(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 $$(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 $$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 $$C_n=\frac{n-1}{2n}$$ 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}{2n^2},1\le i\le n,$$ and any $n$ numbers $x_1,x_2,\dots ,x_n$ in $[0,1]$, we have $$\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 $$-\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(\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 $\mathbf{x}=(x_1,x_2,\dots ,x_n)$ of the hypercube $[0,1{]}^n$. Since $F$ is convex in every variable, its maximum is reached at some vertex $\mathbf{v}$ of the hypercube (point with $x_i=0$ or $x_i=1$, for all $1\le i\le n$). It is easy to see that for all such points we have $F(\mathbf{v})\le \frac{n-1}{n}$, which completes the proof.