Maths Olympiad Prep

Library / /389 of 520

Algebra Difficulty 6.9 National olympiad Find the answer

Let nn be a fixed positive integer. Find the maximum possible value of
1r<s2n(srn)xrxs, \sum_{1 \leqslant r<s \leqslant 2 n}(s-r-n) x_{r} x_{s},
where 1xi1-1 \leqslant x_{i} \leqslant 1 for all i=1,2,,2ni=1,2, \ldots, 2 n. (Austria) Answer. n(n1)n(n-1).

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let ZZ be the expression to be maximized. Since this expression is linear in every variable xix_{i} and 1xi1-1 \leqslant x_{i} \leqslant 1, the maximum of ZZ will be achieved when xi=1x_{i}=-1 or 1. Therefore, it suffices to consider only the case when xi{1,1}x_{i} \in\{-1,1\} for all i=1,2,,2ni=1,2, \ldots, 2 n. For i=1,2,,2ni=1,2, \ldots, 2 n, we introduce auxiliary variables
yi=r=1ixrr=i+12nxr y_{i}=\sum_{r=1}^{i} x_{r}-\sum_{r=i+1}^{2 n} x_{r}
Taking squares of both sides, we have
yi2=r=12nxr2+r<si2xrxs+i<r<s2xrxsri<s2xrxs=2n+r<si2xrxs+i<r<s2xrxsri<s2xrxs, \begin{aligned} y_{i}^{2} & =\sum_{r=1}^{2 n} x_{r}^{2}+\sum_{r<s \leqslant i} 2 x_{r} x_{s}+\sum_{i<r<s} 2 x_{r} x_{s}-\sum_{r \leqslant i<s} 2 x_{r} x_{s} \\ & =2 n+\sum_{r<s \leqslant i} 2 x_{r} x_{s}+\sum_{i<r<s} 2 x_{r} x_{s}-\sum_{r \leqslant i<s} 2 x_{r} x_{s}, \end{aligned}
where the last equality follows from the fact that xr{1,1}x_{r} \in\{-1,1\}. Notice that for every r<sr<s, the coefficient of xrxsx_{r} x_{s} in (1) is 2 for each i=1,,r1,s,,2ni=1, \ldots, r-1, s, \ldots, 2 n, and this coefficient is -2 for each i=r,,s1i=r, \ldots, s-1. This implies that the coefficient of xrxsx_{r} x_{s} in i=12nyi2\sum_{i=1}^{2 n} y_{i}^{2} is 2(2ns+r)2(sr)=2(2 n-s+r)-2(s-r)= 4(ns+r)4(n-s+r). Therefore, summing (1) for i=1,2,,2ni=1,2, \ldots, 2 n yields
i=12nyi2=4n2+1r<s2n4(ns+r)xrxs=4n24Z \sum_{i=1}^{2 n} y_{i}^{2}=4 n^{2}+\sum_{1 \leqslant r<s \leqslant 2 n} 4(n-s+r) x_{r} x_{s}=4 n^{2}-4 Z
Hence, it suffices to find the minimum of the left-hand side. Since xr{1,1}x_{r} \in\{-1,1\}, we see that yiy_{i} is an even integer. In addition, yiyi1=2xi=±2y_{i}-y_{i-1}=2 x_{i}= \pm 2, and so yi1y_{i-1} and yiy_{i} are consecutive even integers for every i=2,3,,2ni=2,3, \ldots, 2 n. It follows that yi12+yi24y_{i-1}^{2}+y_{i}^{2} \geqslant 4, which implies
i=12nyi2=j=1n(y2j12+y2j2)4n \sum_{i=1}^{2 n} y_{i}^{2}=\sum_{j=1}^{n}\left(y_{2 j-1}^{2}+y_{2 j}^{2}\right) \geqslant 4 n
Combining (2) and (3), we get
4ni=12nyi2=4n24Z 4 n \leqslant \sum_{i=1}^{2 n} y_{i}^{2}=4 n^{2}-4 Z
Hence, Zn(n1)Z \leqslant n(n-1). If we set xi=1x_{i}=1 for odd indices ii and xi=1x_{i}=-1 for even indices ii, then we obtain equality in (3) (and thus in (4)). Therefore, the maximum possible value of ZZ is n(n1)n(n-1), as desired.

Comment 1. Z=n(n1)Z=n(n-1) can be achieved by several other examples. In particular, xix_{i} needs not be ±1\pm 1. For instance, setting xi=(1)ix_{i}=(-1)^{i} for all 2i2n2 \leqslant i \leqslant 2 n, we find that the coefficient of x1x_{1} in ZZ is 0. Therefore, x1x_{1} can be chosen arbitrarily in the interval [1,1][-1,1]. Nevertheless, if xi{1,1}x_{i} \in\{-1,1\} for all i=1,2,,2ni=1,2, \ldots, 2 n, then the equality Z=n(n1)Z=n(n-1) holds only when (y1,y2,,y2n)=(0,±2,0,±2,,0,±2)\left(y_{1}, y_{2}, \ldots, y_{2 n}\right)=(0, \pm 2,0, \pm 2, \ldots, 0, \pm 2) or (±2,0,±2,0,,±2,0)( \pm 2,0, \pm 2,0, \ldots, \pm 2,0). In each case, we can reconstruct xix_{i} accordingly. The sum i=12nxi\sum_{i=1}^{2 n} x_{i} in the optimal cases needs not be 0, but it must equal 0 or ±2\pm 2.

Comment 2. Several variations in setting up the auxiliary variables are possible. For instance, one may let x2n+i=xix_{2 n+i}=-x_{i} and yi=xi+xi+1++xi+n1y_{i}^{\prime}=x_{i}+x_{i+1}+\cdots+x_{i+n-1} for any 1i2n1 \leqslant i \leqslant 2 n. Similarly to Solution 1, we obtain Y:=y12+y22++y2n2=2n22ZY:=y_{1}^{\prime 2}+y_{2}^{\prime 2}+\cdots+y_{2 n}^{\prime 2}=2 n^{2}-2 Z. Then, it suffices to show that Y2nY \geqslant 2 n. If nn is odd, then each yiy_{i}^{\prime} is odd, and so yi21y_{i}^{\prime 2} \geqslant 1. If nn is even, then each yiy_{i}^{\prime} is even. We can check that at least one of yi,yi+1,yn+iy_{i}^{\prime}, y_{i+1}^{\prime}, y_{n+i}^{\prime}, and yn+i+1y_{n+i+1}^{\prime} is nonzero, so that yi2+yi+12+yn+i2+yn+i+124y_{i}^{\prime 2}+y_{i+1}^{\prime 2}+y_{n+i}^{\prime 2}+y_{n+i+1}^{\prime 2} \geqslant 4; summing these up for i=1,3,,n1i=1,3, \ldots, n-1 yields Y2nY \geqslant 2 n.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.