Let Z be the expression to be maximized. Since this expression is linear in every variable xi and −1⩽xi⩽1, the maximum of Z will be achieved when xi=−1 or 1. Therefore, it suffices to consider only the case when xi∈{−1,1} for all i=1,2,…,2n. For i=1,2,…,2n, we introduce auxiliary variables
yi=r=1∑ixr−r=i+1∑2nxr
Taking squares of both sides, we have
yi2=r=1∑2nxr2+r<s⩽i∑2xrxs+i<r<s∑2xrxs−r⩽i<s∑2xrxs=2n+r<s⩽i∑2xrxs+i<r<s∑2xrxs−r⩽i<s∑2xrxs,
where the last equality follows from the fact that xr∈{−1,1}. Notice that for every r<s, the coefficient of xrxs in (1) is 2 for each i=1,…,r−1,s,…,2n, and this coefficient is -2 for each i=r,…,s−1. This implies that the coefficient of xrxs in ∑i=12nyi2 is 2(2n−s+r)−2(s−r)= 4(n−s+r). Therefore, summing (1) for i=1,2,…,2n yields
i=1∑2nyi2=4n2+1⩽r<s⩽2n∑4(n−s+r)xrxs=4n2−4Z
Hence, it suffices to find the minimum of the left-hand side. Since xr∈{−1,1}, we see that yi is an even integer. In addition, yi−yi−1=2xi=±2, and so yi−1 and yi are consecutive even integers for every i=2,3,…,2n. It follows that yi−12+yi2⩾4, which implies
i=1∑2nyi2=j=1∑n(y2j−12+y2j2)⩾4n
Combining (2) and (3), we get
4n⩽i=1∑2nyi2=4n2−4Z
Hence, Z⩽n(n−1). If we set xi=1 for odd indices i and xi=−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.
Comment 1. Z=n(n−1) can be achieved by several other examples. In particular, xi needs not be ±1. For instance, setting xi=(−1)i for all 2⩽i⩽2n, we find that the coefficient of x1 in Z is 0. Therefore, x1 can be chosen arbitrarily in the interval [−1,1]. Nevertheless, if xi∈{−1,1} for all i=1,2,…,2n, then the equality Z=n(n−1) holds only when (y1,y2,…,y2n)=(0,±2,0,±2,…,0,±2) or (±2,0,±2,0,…,±2,0). In each case, we can reconstruct xi accordingly. The sum ∑i=12nxi in the optimal cases needs not be 0, but it must equal 0 or ±2.
Comment 2. Several variations in setting up the auxiliary variables are possible. For instance, one may let x2n+i=−xi and yi′=xi+xi+1+⋯+xi+n−1 for any 1⩽i⩽2n. Similarly to Solution 1, we obtain Y:=y1′2+y2′2+⋯+y2n′2=2n2−2Z. Then, it suffices to show that Y⩾2n. If n is odd, then each yi′ is odd, and so yi′2⩾1. If n is even, then each yi′ is even. We can check that at least one of yi′,yi+1′,yn+i′, and yn+i+1′ is nonzero, so that yi′2+yi+1′2+yn+i′2+yn+i+1′2⩾4; summing these up for i=1,3,…,n−1 yields Y⩾2n.