2023 Chinese IMO National Team Selection Test

Proof 1. For any $(x_i)$ and $(y_j)$ satisfying the given conditions, we define $$X_k=\sum _{i,j=1}^n{a}_{ijk}{x}_i{y}_j.$$ Since we can always choose $z_k$ with the same sign as $X_k$, we have $$\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n{a}_{ijk}{x}_i{y}_j{z}_k=\sum _{k=1}^n|X_k|.$$ Note that (summing over all possible $(x_i)$ and $(y_j)$) $$\begin{array}{rl}\sum _{(x_i),(y_j)}|X_k{|}^2& =\sum _{(x_i),(y_j)}\sum _{i_1,i_2}\sum _{j_1,j_2}{a}_{i_1{j}_{1}k}{a}_{i_2{j}_{2}k}{x}_{i_1}{x}_{i_2}{y}_{j_1}{y}_{j_2}\\ & =\sum _{i_1,i_2}\sum _{j_1,j_2}{a}_{i_1{j}_{1}k}{a}_{i_2{j}_{2}k}\sum _{(x_i),(y_j)}{x}_{i_1}{x}_{i_2}{y}_{j_1}{y}_{j_2},\end{array}$$ and the last line has non-zero value only when $i_1=i_2$ and $j_1=j_2$, so $$\sum _{(x_i),(y_j)}|X_k{|}^2=(2^n{)}^2\sum _{i,j=1}^n{a}_{ijk}^2=2^{2n}{n}^2.$$ (To obtain a lower bound estimate for ${\sum }_{(x_i),(y_j)}|X_k|$, we need to estimate ${\sum }_{(x_i),(y_j)}|X_k{|}^n$ for some large $n$ greater than 2.) Similarly, we have $$\sum _{(x_i),(y_j)}|X_k{|}^4=\sum _{i_1,i_2,i_3,i_4}\sum _{j_1,j_2,j_3,j_4}{a}_{i_1{j}_{1}k}{a}_{i_2{j}_{2}k}{a}_{i_3{j}_{3}k}{a}_{i_4{j}_{4}k}\sum _{(x_i),(y_j)}{x}_{i_1}{x}_{i_2}{x}_{i_3}{x}_{i_4}{y}_{j_1}{y}_{j_2}{y}_{j_3}{y}_{j_4}.$$ In the last summation, it is non-zero only when $(i_1,i_2,i_3,i_4)$ and $(j_1,j_2,j_3,j_4)$ are paired up in pairs, and each term is repeated when all 4 items are the same, so we have $$\sum _{i_1,i_2,i_3,i_4}\sum _{j_1,j_2,j_3,j_4}{a}_{i_1{j}_{1}k}{a}_{i_2{j}_{2}k}{a}_{i_3{j}_{3}k}{a}_{i_4{j}_{4}k}\sum _{(x_i),(y_j)}{x}_{i_1}{x}_{i_2}{x}_{i_3}{x}_{i_4}{y}_{j_1}{y}_{j_2}{y}_{j_3}{y}_{j_4}<9n^4(2^n{)}^2.$$ Now, by Hölder's inequality, $${\left(\sum _{(x_i),(y_j)}{\left(|X_k{|}^{2/3}\right)}^{3/2}\right)}^{2/3}{\left(\sum _{(x_i),(y_j)}{\left(|X_k{|}^{4/3}\right)}^3\right)}^{1/3}\ge \sum _{(x_i),(y_j)}|X_k{|}^2=2^{2n}{n}^2,$$ so $${\left(\sum _{(x_i),(y_j)}|X_k|\right)}^{2/3}\cdot (2^{2n}\cdot 9n^4{)}^{1/3}>2^{2n}{n}^2.$$ Hence, $$\sum _{(x_i),(y_j)}|X_k|>{\left((2^{2n}{)}^{2/3}\frac{n^{2/3}}{3^{2/3}}\right)}^{3/2}=2^{2n}\cdot \frac{n}{3},$$ summing over $k$ yields $$(\ast )\sum _{(x_i),(y_j)}\sum _k|X_k|>2^{2n}\cdot \frac{n^2}{3},$$ which implies the existence of $(x_i,y_j)$ such that ${\sum }_k|X_k|>\frac{n^2}{3}$. The proposition holds. $\square$

Note: The last part using Hölder's inequality can also be proved using the lemma. When $X\ge 0$, $(X-3{)}^2(X+6)X=X^4-27X^2+54X\ge 0$. Hence, we have $X^4-27n^2{X}^2+54n^{3}X\ge 0$. Thus, $$\sum _{(x_i),(y_j)}|X_k{|}^4-27n^2\sum _{(x_i),(y_j)}|X_k{|}^2+54n^3\sum _{(x_i),(y_j)}|X_k|\ge 0.$$ Therefore, $$\sum _{(x_i),(y_j)}|X_k|\ge \frac{1}{54}\cdot 2^{2n}\cdot \frac{(27n^2\cdot n^2-9n^4)}{n^3}=\frac{1}{3}\cdot 2^{2n}n.$$ Summing over $k$ yields $(\ast )$.

Proof 2. We first prove two lemmas. Lemma 1: Let $n$ be a positive integer, and let $a_1,a_2,\dots ,a_n$ be real numbers. Then we have $$\sum _{x_1,x_2,\dots ,x_n\in \{-1,1\}}\left|\sum _{i=1}^n{a}_i{x}_i\right|\ge 2\left(\genfrac{}{}{0ex}{}{n-1}{\lfloor \frac{n-1}{2}\rfloor }\right)\sum _{i=1}^n|a_i|.$$ Proof of Lemma 1: Since each $x_i$ takes values from $-1,1$, replacing $a_i$ with $|a_i|$ does not change the original expression. Therefore, without loss of generality, we can assume that $a_i\ge 0$ for $i=1,2,\dots ,n$. Notice that when all $x_i$ simultaneously change sign, the value of $|{\sum }_{i=1}^n{a}_i{x}_i|$ remains the same. Thus, we have: $$\begin{array}{rl}\sum _{x_1,x_2,\dots ,x_n\in \{-1,1\}}\left|\sum _{i=1}^n{a}_i{x}_i\right|& \ge \sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_n\in \{-1,1\}\\ x_1+x_2+\cdots +x_n\ne 0\end{array}}\left|\sum _{i=1}^n{a}_i{x}_i\right|\\ & =2\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_n\in \{-1,1\}\\ x_1+x_2+\cdots +x_n>0\end{array}}\left|\sum _{i=1}^n{a}_i{x}_i\right|\\ & \ge 2\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_n\in \{-1,1\}\\ x_1+x_2+\cdots +x_n>0\end{array}}\sum _{i=1}^n{a}_i{x}_i\\ & =2\sum _{i=1}^n\left(\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_n\in \{-1,1\}\\ x_1+x_2+\cdots +x_n>0\end{array}}{x}_i\right)a_i.\end{array}$$ Furthermore, notice that due to symmetry, the value of $$\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_n\in \{-1,1\}\\ x_1+x_2+\cdots +x_n>0\end{array}}{x}_i$$ does not depend on $i$. Let's consider the case when $i=n$. The value of this sum is given by $$\begin{array}{rl}\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_n\in \{-1,1\}\\ x_1+x_2+\cdots +x_n>0\end{array}}{x}_n& =\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_{n-1}\in \{-1,1\}\\ x_1+x_2+\cdots +x_{n-1}>-1\end{array}}1+\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_{n-1}\in \{-1,1\}\\ x_1+x_2+\cdots +x_{n-1}>1\end{array}}(-1)\\ & =\sum _{\begin{array}{c}{x}_1,x_2,\dots ,x_{n-1}\in \{-1,1\}\\ x_1+x_2+\cdots +x_{n-1}\in \{0,1\}\end{array}}1\\ & =\left(\genfrac{}{}{0ex}{}{n-1}{\lfloor \frac{n-1}{2}\rfloor }\right).\end{array}$$ The final step is due to the fact that $x_1,x_2,\dots ,x_{n-1}\in -1,1$ satisfy $x_1+x_2+\cdots +x_{n-1}\in 0,1$ if and only if exactly $\lfloor \frac{n-1}{2}\rfloor$ numbers among $x_1,x_2,\dots ,x_{n-1}$ take the value 1 and exactly $\lfloor \frac{n-1}{2}\rfloor$ numbers take the value -1. Thus, Lemma 1 is proven.

Lemma 2: For any positive integer $n$, we have $$\left(\genfrac{}{}{0ex}{}{n-1}{\lfloor \frac{n-1}{2}\rfloor }\right)\ge \frac{2^{n-1}}{\sqrt{2n}}.$$ Proof of Lemma 2: It can be easily verified that the inequality holds for $n=1,2,3$ (with equality holding for $n=2$). For even $n=2m\ge 4$, the inequality is equivalent to $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)\ge \frac{2^{2m}}{\sqrt{4m+2}}$; for odd $n=2m+1\ge 5$, the inequality is equivalent to $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)\ge \frac{2^{2m}}{\sqrt{4m+2}}$. Thus, it suffices to prove that for any integer $m\ge 2$, we have $$\left(\genfrac{}{}{0ex}{}{2m}{m}\right)\ge \frac{2^{2m-1}}{\sqrt{m}}.$$ Indeed, note that $$\left(\genfrac{}{}{0ex}{}{2m}{m}\right)=\prod _{k=1}^m\frac{2k(2k-1)}{k^2}=2^{2m}\prod _{k=1}^m\frac{2k-1}{2k}.$$ Let $$A=\prod _{k=2}^m\frac{2k-1}{2k},B=\prod _{k=2}^m\frac{2k-2}{2k-1},$$ then $A>B$ and $AB=\frac{2}{2m}=\frac{1}{m}$. Hence, $A>\frac{1}{\sqrt{m}}$, which implies $$\left(\genfrac{}{}{0ex}{}{2m}{m}\right)=2^{2m}\cdot \frac{1}{2}A>2^{2m}\cdot \frac{1}{2\sqrt{m}}=\frac{2^{2m-1}}{\sqrt{m}}.$$ Lemma 2 is proven.

From the two lemmas above, we immediately obtain the following result: for any $n$ real numbers $a_1,a_2,\dots ,a_n$, we have $$\sum _{x_1,x_2,\dots ,x_n\in \{-1,1\}}\left|\sum _{i=1}^n{a}_i{x}_i\right|\ge \frac{2^{2n}}{\sqrt{2n}}\sum _{i=1}^n|a_i|.$$ By applying this result twice, we can conclude that for any $n^2$ real numbers $a_{ij}$, ($i,j=1,2,\dots ,n$), we have (*) \qquad \sum_{x_1, \dots, x_n, y_1, \dots, y_n \in \{-1, 1\}} \left| \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} x_i y_j \right| &= \sum_{x_1, \dots, x_n \in \{-1, 1\}} \left( \sum_{y_1, \dots, y_n \in \{-1, 1\}} \left| \sum_{j=1}^{n} \left( \sum_{i=1}^{n} a_{ij} x_i \right) y_j \right| \right) \\ &\geq \sum_{x_1, \dots, x_n \in \{-1, 1\}} \left( \frac{2^n}{\sqrt{2n}} \sum_{j=1}^{n} \left| \sum_{i=1}^{n} a_{ij} x_i \right| \right) \\ &= \frac{2^n}{\sqrt{2n}} \sum_{j=1}^{n} \sum_{x_1, \dots, x_n \in \{-1, 1\}} \left| \sum_{i=1}^{n} a_{ij} x_i \right| \\ &\geq \frac{2^n}{\sqrt{2n}} \sum_{j=1}^{n} \frac{2^n}{\sqrt{2n}} \sum_{i=1}^{n} |a_{ij}| \\ &= \frac{2^{2n}}{2n} \sum_{i=1}^{n} \sum_{j=1}^{n} |a_{ij}|. Back to the original question, for a fixed set of $x_1,\dots ,x_n,y_1,\dots ,y_n$, we can choose $z_k\in \{-1,1\}$ such that $z_k{\sum }_{i=1}^n{\sum }_{j=1}^n{a}_{ijk}{x}_i{y}_j\ge 0$ for $k=1,2,\dots ,n$. In this case, $$\left|\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n{a}_{ijk}{x}_i{y}_j{z}_k\right|=\sum _{k=1}^n\left|\sum _{i=1}^n\sum _{j=1}^n{a}_{ijk}{x}_i{y}_j\right|\stackrel{\text{denoted as}}{=}{T}_{x_1,\dots ,x_n,y_1,\dots ,y_n}.$$ According to (*), we have $$\sum _{x_1,\dots ,x_n,y_1,\dots ,y_n\in \{-1,1\}}{T}_{x_1,\dots ,x_n,y_1,\dots ,y_n}\ge \sum _{k=1}^n\frac{2^{2n}}{2n}\sum _{i=1}^n\sum _{j=1}^n|a_{ijk}|=2^{2n}\cdot \frac{n^2}{2}.$$ Thus, by the principle of averages, there exists a set of $x_1,\dots ,x_n,y_1,\dots ,y_n\in \{-1,1\}$ such that $$T_{x_1,\dots ,x_n,y_1,\dots ,y_n}\ge \frac{n^2}{2}.$$ Therefore, the original problem is proved. $\square$