Problem 1738

We divide the set $A = \{0, 1, 2\}^n$ into: $A = A_0 \cup A_1 \cup \cdots \cup A_{2n}$, where
$$A_k = \{\beta = (i_1, i_2, \dots, i_n) \in A : i_1 + i_2 + \dots + i_n = k\}, \quad k = 0, 1, \dots, 2n.$$
Let $a_k$ denote the number of elements in $A_k$. Then
$$(1 + t + t^2)^n = a_0 + a_1 t + \cdots + a_n t^n + \cdots + a_{2n} t^{2n}, \quad a_{2n-k} = a_k.$$
Set $X = (x_1, \dots, x_n)$ and $y = (x_1 + \dots + x_n)/n$. Then $f(X) = \sum_{k=0}^{2n} \sum_{\beta \in A_k} |\beta \cdot X - 1|$. Removing the absolute value signs and summing them in groups, we consider
$$B_k = \sum_{\beta \in A_k} (\beta \cdot X - 1) = \frac{k|A_k|}{n}(x_1 + \dots + x_n) - |A_k| = k a_k y - a_k.$$
We estimate $\sum_{k=0}^{2n} |B_k|$, by canceling appropriate terms. Consider the sizes of $k a_k$ and note that
$$\sum_{k=0}^{2n} k a_k t^{k-1} = \frac{d}{dt}[(1+t+t^2)^n] = n(1+2t)(1+t+t^2)^{n-1}$$
and that the coefficients of $(1+t+t^2)^{n-1} = \sum_{k=0}^{2n-2} c_k t^k$ $(c_0, c_1, \dots, c_{n-1}, \dots, c_{2n-2})$ is palindromic. Since $k a_k = c_{k-1} + 2c_{k-2}$, we have
$$(n+1)a_{n+1} \ge n a_n \ge (n+2)a_{n+2} \ge (n-1)a_{n-1} \ge (n+3)a_{n+3} \ge \dots \ge 2a_2 \ge 2n a_{2n} \ge 1a_1.$$
This shows that $U_1 := \sum_{k=0}^n k a_k < \sum_{k=n+1}^{2n} k a_k$ and $U_2 := \sum_{k=n+2}^{2n} k a_k < \sum_{k=0}^{n+1} k a_k$. Choose $\lambda = \frac{U_1 - U_2}{(n+1)a_{n+1}} \in (-1, 1)$, we have
$$f(X) \ge \sum_{k=0}^{2n} |B_k| \ge \left[ \sum_{k=0}^n (-B_k) + \lambda B_{n+1} + \sum_{k=n+2}^{2n} B_k \right] + (1 - |\lambda|) |B_{n+1}|.$$
The coefficient of $y$ in the above square bracket is $-U_1 + \lambda(n+1)a_{n+1} + U_2 = 0$. So the expression in the square bracket is a constant $C = \sum_{k=0}^n a_k - \lambda a_{n+1} + \sum_{k=n+2}^{2n} a_k$. Therefore, $f(X) \ge C$ is always true, and when $x_1 = \dots = x_n = \frac{1}{n+1}$, the equality holds. Moreover, the equality holds precisely when $a_{n+1}$ terms in the formula above are all zero, i.e. the inner product of $X = (x_1, \dots, x_n)$ with an arbitrary vector in $A_{n+1}$ is 1. The only such $X$ is when $x_1 = \dots = x_n = \frac{1}{n+1}$.