56th International Mathematical Olympiad Shortlisted Problems

Let $Z$ be the expression to be maximized. Since this expression is linear in every variable $x_i$ and $-1⩽x_i⩽1$, the maximum of $Z$ will be achieved when $x_i=-1$ or $1$. Therefore, it suffices to consider only the case when $x_i\in \{-1,1\}$ for all $i=1,2,\dots ,2n$. For $i=1,2,\dots ,2n$, we introduce auxiliary variables $$y_i=\sum _{r=1}^i{x}_r-\sum _{r=i+1}^{2n}{x}_r.$$ Taking squares of both sides, we have $$\begin{array}{rl}{y}_i^2& =\sum _{r=1}^{2n}{x}_r^2+\sum _{r<s⩽i}2x_r{x}_s+\sum _{i<r<s}2x_r{x}_s-\sum _{r⩽i<s}2x_r{x}_s\\ & =2n+\sum _{r<s⩽i}2x_r{x}_s+\sum _{i<r<s}2x_r{x}_s-\sum _{r⩽i<s}2x_r{x}_s\end{array}\text{\hspace{1em}(1)}$$ where the last equality follows from the fact that $x_r\in \{-1,1\}$. Notice that for every $r<s$, the coefficient of $x_r{x}_s$ in (1) is $2$ for each $i=1,\dots ,r-1,s,\dots ,2n$, and this coefficient is $-2$ for each $i=r,\dots ,s-1$. This implies that the coefficient of $x_r{x}_s$ in ${\sum }_{i=1}^{2n}{y}_i^2$ is $2(2n-s+r)-2(s-r)=4(n-s+r)$. Therefore, summing (1) for $i=1,2,\dots ,2n$ yields $$\begin{array}{c}\sum _{i=1}^{2n}{y}_i^2=4n^2+\sum _{1⩽r<s⩽2n}4(n-s+r)x_r{x}_s=4n^2-4Z.\end{array}\text{\hspace{1em}(2)}$$ Hence, it suffices to find the minimum of the left-hand side. Since $x_r\in \{-1,1\}$, we see that $y_i$ is an even integer. In addition, $y_i-y_{i-1}=2x_i=\pm 2$, and so $y_{i-1}$ and $y_i$ are consecutive even integers for every $i=2,3,\dots ,2n$. It follows that $y_{i-1}^2+y_i^2⩾4$, which implies $$\begin{array}{c}\sum _{i=1}^{2n}{y}_i^2=\sum _{j=1}^n\left(y_{2j-1}^2+y_{2j}^2\right)⩾4n.\end{array}\text{\hspace{1em}(3)}$$ Combining (2) and (3), we get $$\begin{array}{c}4n⩽\sum _{i=1}^{2n}{y}_i^2=4n^2-4Z\end{array}\text{\hspace{1em}(4)}$$ Hence, $Z⩽n(n-1)$. If we set $x_i=1$ for odd indices $i$ and $x_i=-1$ for even indices $i$, then we obtain equality in (3) (and thus in (4)). Therefore, the maximum possible value of $Z$ is $n(n-1)$, as desired.

---

Alternative solution.

We present a different method of obtaining the bound $Z⩽n(n-1)$. As in the previous solution, we reduce the problem to the case $x_i\in \{-1,1\}$. For brevity, we use the notation $[2n]=\{1,2,\dots ,2n\}$. Consider any $x_1,x_2,\dots ,x_{2n}\in \{-1,1\}$. Let $$A=\left\{i\in [2n]:x_i=1\right\}\text{ and }B=\left\{i\in [2n]:x_i=-1\right\}.$$ For any subsets $X$ and $Y$ of $[2n]$ we define $$e(X,Y)=\sum _{r<s,r\in X,s\in Y}(s-r-n).$$ One may observe that $e(A,A)+e(A,B)+e(B,A)+e(B,B)=e([2n],[2n])={\sum }_{1⩽r<s⩽2n}(s-r-n)=-\frac{(n-1)n(2n-1)}{3}$. Therefore, we have $$\begin{array}{c}Z=e(A,A)-e(A,B)-e(B,A)+e(B,B)=2(e(A,A)+e(B,B))+\frac{(n-1)n(2n-1)}{3}.\end{array}\text{\hspace{1em}(5)}$$ Thus, we need to maximize $e(A,A)+e(B,B)$, where $A$ and $B$ form a partition of $[2n]$. Due to the symmetry, we may assume that $|A|=n-p$ and $|B|=n+p$, where $0⩽p⩽n$. From now on, we fix the value of $p$ and find an upper bound for $Z$ in terms of $n$ and $p$. Let $a_1<a_2<\cdots <a_{n-p}$ and $b_1<b_2<\cdots <b_{n+p}$ list all elements of $A$ and $B$, respectively. Then $$\begin{array}{c}e(A,A)=\sum _{1⩽i<j⩽n-p}\left(a_j-a_i-n\right)=\sum _{i=1}^{n-p}(2i-1-n+p)a_i-\left(\genfrac{}{}{0ex}{}{n-p}{2}\right)\cdot n\end{array}\text{\hspace{1em}(6)}$$ and similarly $$\begin{array}{c}e(B,B)=\sum _{i=1}^{n+p}(2i-1-n-p)b_i-\left(\genfrac{}{}{0ex}{}{n+p}{2}\right)\cdot n.\end{array}\text{\hspace{1em}(7)}$$ Thus, now it suffices to maximize the value of $$\begin{array}{c}M=\sum _{i=1}^{n-p}(2i-1-n+p)a_i+\sum _{i=1}^{n+p}(2i-1-n-p)b_i.\end{array}\text{\hspace{1em}(8)}$$ In order to get an upper bound, we will apply the rearrangement inequality to the sequence $a_1,a_2,\dots ,a_{n-p},b_1,b_2,\dots ,b_{n+p}$ (which is a permutation of $1,2,\dots ,2n$ ), together with the sequence of coefficients of these numbers in (8). The coefficients of $a_i$ form the sequence $$n-p-1,n-p-3,\dots ,1-n+p$$ and those of $b_i$ form the sequence $$n+p-1,n+p-3,\dots ,1-n-p$$ Altogether, these coefficients are, in descending order: - $n+p+1-2i$, for $i=1,2,\dots ,p$; - $n-p+1-2i$, counted twice, for $i=1,2,\dots ,n-p$; and $-(n+p+1-2i)$, for $i=p,p-1,\dots ,1$. Thus, the rearrangement inequality yields $$\begin{array}{rl}M⩽\sum _{i=1}^p(n+& p+1-2i)(2n+1-i)\\ & +\sum _{i=1}^{n-p}(n-p+1-2i)((2n+2-p-2i)+(2n+1-p-2i))\\ & -\sum _{i=1}^p(n+p+1-2i)i\end{array}\text{\hspace{1em}(9)}$$ Finally, combining the information from (5), (6), (7), and (9), we obtain $$\begin{array}{rl}Z⩽& \frac{(n-1)n(2n-1)}{3}-2n\left(\left(\genfrac{}{}{0ex}{}{n-p}{2}\right)+\left(\genfrac{}{}{0ex}{}{n+p}{2}\right)\right)\\ & +2\sum _{i=1}^p(n+p+1-2i)(2n+1-2i)+2\sum _{i=1}^{n-p}(n-p+1-2i)(4n-2p+3-4i),\end{array}$$ which can be simplified to $$Z⩽n(n-1)-\frac{2}{3}p(p-1)(p+1).$$ Since $p$ is a nonnegative integer, this yields $Z⩽n(n-1)$.