Take f_k(x) = x^n/n for all k Then for any n-tuples {x1,..,xn} we have (x1^n +...+ xn^n) / n - x1...xn is non negative (just apply the Cauchy inequality) Hence the absolute value is equal to (x1^n +.. + xn^n)/ n - x1...xn which is always strictly less than 1 with x1,..xn belongs to [0,1] That yields Cn = 0

the answer is $\frac{n-1}{2n}$. We have \[ (n-1)|f_1(1)+...+f_n(1)-1|+\sum^n_{i=1}|f_1(1)+...+f_i(0)+...+f_n(1)|+|f_1(0)+...+f_n(0)|\geq |n-1-(n-1)(f_1(1)+...+f_n(1))+(n-1)(f_1(1)+...+f_n(1))+(f_1(0)+...+f_n(0))-(f_1(0+...+f_n(0))| =n-1 \] There are $2n$ terms, so at least one term is greater than $\frac{n-1}{2n}$, so $C_n\geq \frac{n-1}{2n}$. Now let $f_i(x)=x^n/n-\frac{n-1}{2n^2}$, then $|f_1(x_1)+...+f_n(x_n)-x_1...x_n|=|\sum^n_{i=1}x_i^n/n-x_1...x_n-\frac{n-1}{2n}|$. We claim that \[\sup_{0\leq x_1,...,x_n\leq 1} \sum^n_{i=1}x_i^n/n-x_1...x_n\leq \frac{n-1}{n}\] Indeed, for each $i$, if we fix the other $x_j,j\neq i$, then the function $g_{j\neq i}(x_i)= \sum^n_{i=1}x_i^n/n-x_1...x_n\leq \frac{n-1}{n}$, with variable $x_i$, is convex, so $\sup_{0\leq x_1,...,x_n\leq 1} \sum^n_{i=1}x_i^n/n-x_1...x_n$ is attained when $x_i, i=1,...,n$, are equals 0 or 1. Suppose there are $p$ terms equals 1 and $q$ terms equals 0, $p+q=n$, then $\sum^n_{i=1}x_i^n/n-x_1...x_n=\frac{p}{n}\leq\frac{n-1}{n}$ if $p\leq n-1$ and 0 otherwise. We have then our inequality. Now by Cauchy inequality, $\sum^n_{i=1}x_i^n/n-x_1...x_n\geq 0$, so we have \[-\frac{n-1}{2n}\leq \sum^n_{i=1}x_i^n/n-x_1...x_n-\frac{n-1}{2n}\leq\frac{n-1}{2n}\] for all $0\leq x_1,...,x_n\leq 1$, or \[| \sum^n_{i=1}x_i^n/n-x_1...x_n-\frac{n-1}{2n}\leq\frac{n-1}{2n}|\] So $C_n=\frac{n-1}{2n}$.

It doesn't really make a significant difference, but I found setting $f(x)=ax+b$ easier for the construction part (since $f$ is both convex and concave, the extrema occur when the $x_i$ are all $0$ or $1$, and we don't need to distinguish between sign changes resulting from the absolute value bars).

I'm assuming the original problem had $C_n$ real instead of integer. (For $C_n$ integer, take $f_1=...=f_n=1/2n$ constant functions. Then $|f(x_1)+...+f(x_n)-x_1...x_n| = |0.5-P| \le 0.5$ where $0 \le P=x_1...x_n \le 1$. This implies $C_n=0$). First I prove that we can always take $x_1...,x_n$ such that $| \text{ugly expression} | \ge (n-1)/2n =: C$. Assume not, then we have functions such that $| \text{ugly expression} | < (n-1)/2n = C$. Let $I_k$ be the length of the range of $f_k$ ($\text{max}(f_k)-\text{min}(f_k)$). Notice that $| \displaystyle\sum_{k=1}^{n-1} f_k(x_k) + f_n(0) | < C$ Notice that the range of the function $g(x_1,...,x_{n-1}):=\displaystyle\sum_{k=1}^{n-1} f_k(x_k)$ has length $I_1+...+I_{n-1}=I-I_n$, where $I=\sum I_k$. However, the above inequality proves that this number is $< 2C$, since $f_n(0)$ is constant. Therefore, for some $k$, $I_k < 2C/(n-1)$. However, notice that $|f_k(x)+D-x| < C$, where $D=\sum f_i(1) - f_k(1)$, for all $x$. Therefore, the range of $g(x)=f_k(x)-x$ has length at most $2C$. Since $I_k < 2C/(n-1)$, assume that $a \le f_k(x) \le a+(2C/(n-1))$ for all $x$. Then we obtain $g(1) \le a-1+(2C/(n-1))$ and $g(0) \le 1$, hence $1-(2C)/(n-1) < 2C$. From this, $(n-1)/n=2C > (n-1)/n$, contradiction. Therefore, $\boxed{C_n \le (n-1)/2n}$. The construction is easy. $f_i(x)=x^n/n - D$ for all $i$, and $D$ a constant. To prove $|\text{ugly expression}| \le C$ is an elementary inequality. The motivation for this function is not difficult. Because of the above considerations, we want ideally $I_k=1/n$, so $f(x)=g(x)/n+D$, where $D$ is a constant and $g$ is a function with range of size 1. Now, ideally we want $\text{ugly expression}$ to be heterogeneous, so $g$ should have degree $n$. From this, $f=x^n/n+D$.

We claim that $C_n=\frac{n-1}{2n}$. First, note that if $|a_0|,|a_1|,|a_2|,\ldots,|a_{n-1}|<C_n$, then certainly $\left|\frac{a_0+a_1+\cdots+a_{n-1}}n\right|<C_n$, for any reals $a_0,a_1,\ldots,a_{n-1}$. Setting $a_i=\sum_{k=1}^n f_{i+k}(x_k)$ for all $i$, where function indices are taken modulo $n$ gives that if $f=\frac{f_1+f_2+\cdots+f_n}n$ and $|f_1(x_1)+f_2(x_2)+\cdots+f_n(x_n)-x_1x_2\cdots x_n|<C_n$ for all $0\le x_1,x_2,\ldots,x_n\le1$, then $|f(x_1)+f(x_2)+\cdots+f(x_n)-x_1x_2\cdots x_n|<C_n$. Thus, it suffices to prove the problem when $f=f_1=f_2=\cdots=f_n$. This can be done by setting $x_1=x_2=\cdots=x_n=0$, $x_1=x_2=\cdots=x_n=1$, and $x_1=0,x_2=x_3=\cdots=x_n=1$, which give the inequalities $|nf(0)|<C_n$, $|nf(1)-1|<C_n$, and $|f(0)+(n-1)f(1)|<C_n$. The first two equations tell us that $f(0)>-\frac{C_n}n$ and $f(1)>\frac{1-C_n}n$, so $C_n>f(0)+(n-1)f(1)>-\frac{C_n}n+\frac{(n-1)(1-C_n)}n=\frac{n-1}n-C_n$. But for $C_n=\frac{n-1}{2n}$, this is a contradiction. In particular, the above argument gives a good motivation for the value of $C_n$ and the construction that we can't do any better. As long as we set $f$ to be a linear function with $f(0)=-\frac{C_n}n$ and $f(1)=\frac{1-C_n}n$, linearity of the term inside the absolute value tells us that the maximum value of the expression is achieved at some $(x_1,x_2,\ldots,x_n)\in\{0,1\}^n$. Indeed, if we set $f(x)=\frac{x-C_n}{n}$ then equality holds at $x_1=x_2=\cdots=x_n=1$. For the other cases, $x_1x_2\cdots x_n=0$, so the inequality becomes $\left|\frac kn-C_n\right|\le C_n$, where $0\le k\le n-1$ is the number of $1$'s among $x_1,x_2,\ldots,x_n$. It is easy to see that this is satisfied, so we are done.