2022 China Team Selection Test for IMO

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+\cdots +i_n=k\},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},a_{2n-k}=a_k.$$ Set $X=(x_1,\dots ,x_n)$ and $y=(x_1+\cdots +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+\cdots +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 \cdots \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=\cdots =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=\cdots =x_n=\frac{1}{n+1}$.