Shortlist 2015, A3¶

Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Austria

Concepts : Convexité, inégalité de Jensen, lissage

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 13 (page 14 du PDF)

Énoncé¶

Let \(n\) be a fixed positive integer. Find the maximum possible value of

\[\sum_{1 \leq r < s \leq 2n} (s - r - n)\, x_r x_s,\]

where \(-1 \leq x_i \leq 1\) for all \(i = 1, 2, \ldots, 2n\).

Indices : les idées clés

Convexité, inégalité de Jensen, lissage : l'expression est affine en chaque variable, donc son maximum est atteint en des points où chaque \(x_i\) vaut \(\pm 1\).
Sommes partielles signées (solution 1) : avec \(y_i = (x_1 + \cdots + x_i) - (x_{i+1} + \cdots + x_{2n})\), on a \(\sum y_i^2 = 4n^2 - 4Z\), et deux \(y_i\) consécutifs sont des entiers pairs consécutifs.
Inégalité de réordonnement (solution 2) : après avoir séparé les indices où \(x_i = 1\) et où \(x_i = -1\), on majore une somme pondérée d'une permutation de \(1, \ldots, 2n\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et deux remarques).

Réponse. Le maximum vaut \(n(n-1)\).

Solution 1¶

Notons \(Z\) l'expression à maximiser. Elle est affine en chaque variable \(x_i\) (les autres étant fixées), et \(-1 \leq x_i \leq 1\) ; une fonction affine sur un segment atteint son maximum en une extrémité. On peut donc remplacer successivement chaque \(x_i\) par \(-1\) ou \(1\) sans diminuer \(Z\) : il suffit de traiter le cas où \(x_i \in \{-1, 1\}\) pour tout \(i\).

Pour \(i = 1, 2, \ldots, 2n\), posons

\[y_i = \sum_{r=1}^{i} x_r - \sum_{r=i+1}^{2n} x_r.\]

En élevant au carré, et comme \(x_r^2 = 1\) :

\[y_i^2 = \sum_{r=1}^{2n} x_r^2 + \sum_{r<s\leq i} 2x_r x_s + \sum_{i<r<s} 2x_r x_s - \sum_{r\leq i<s} 2x_r x_s = 2n + \sum_{r<s\leq i} 2x_r x_s + \sum_{i<r<s} 2x_r x_s - \sum_{r\leq i<s} 2x_r x_s. \tag{1}\]

Pour \(r < s\) fixés, le coefficient de \(x_r x_s\) dans (1) vaut \(2\) pour \(i = 1, \ldots, r-1\) et pour \(i = s, \ldots, 2n\), et vaut \(-2\) pour \(i = r, \ldots, s-1\). Dans \(\sum_{i=1}^{2n} y_i^2\), ce coefficient vaut donc \(2(2n - s + r) - 2(s - r) = 4(n - s + r)\). En sommant (1) pour \(i = 1, \ldots, 2n\) :

\[\sum_{i=1}^{2n} y_i^2 = 4n^2 + \sum_{1\leq r<s\leq 2n} 4(n - s + r)\, x_r x_s = 4n^2 - 4Z. \tag{2}\]

Il suffit donc de minorer le membre de gauche.

Comme les \(x_r\) valent \(\pm 1\), chaque \(y_i\) est un entier pair (somme de \(2n\) termes impairs). De plus \(y_i - y_{i-1} = 2x_i = \pm 2\), donc \(y_{i-1}\) et \(y_i\) sont des entiers pairs consécutifs pour \(i = 2, \ldots, 2n\) ; l'un d'eux est non nul, d'où \(y_{i-1}^2 + y_i^2 \geq 4\). Ainsi

\[\sum_{i=1}^{2n} y_i^2 = \sum_{j=1}^{n} \left(y_{2j-1}^2 + y_{2j}^2\right) \geq 4n. \tag{3}\]

Avec (2), on obtient \(4n \leq 4n^2 - 4Z\), c'est-à-dire \(Z \leq n(n-1)\).

En prenant \(x_i = 1\) pour \(i\) impair et \(x_i = -1\) pour \(i\) pair, on a \(y_i = 0\) pour \(i\) pair et \(y_i = 2\) pour \(i\) impair : il y a égalité dans (3), donc \(Z = n(n-1)\). Le maximum cherché est \(n(n-1)\). \(\blacksquare\)

Solution 2¶

On obtient autrement la majoration \(Z \leq n(n-1)\). Comme dans la solution 1, on se ramène au cas \(x_i \in \{-1, 1\}\). Notons \([2n] = \{1, 2, \ldots, 2n\}\) et

\[A = \{i \in [2n] : x_i = 1\}, \qquad B = \{i \in [2n] : x_i = -1\}.\]

Pour deux parties \(X, Y\) de \([2n]\), posons

\[e(X, Y) = \sum_{r<s,\ r\in X,\ s\in Y} (s - r - n).\]

On a

\[e(A,A) + e(A,B) + e(B,A) + e(B,B) = e([2n],[2n]) = \sum_{1\leq r<s\leq 2n} (s - r - n) = -\frac{(n-1)n(2n-1)}{3},\]

donc

\[Z = e(A,A) - e(A,B) - e(B,A) + e(B,B) = 2\big(e(A,A) + e(B,B)\big) + \frac{(n-1)n(2n-1)}{3}. \tag{5}\]

Il s'agit donc de maximiser \(e(A,A) + e(B,B)\) lorsque \(A, B\) forment une partition de \([2n]\).

Par symétrie (\(x \mapsto -x\) échange \(A\) et \(B\)), on peut supposer \(|A| = n - p\) et \(|B| = n + p\) avec \(0 \leq p \leq n\). On fixe \(p\) et on majore \(Z\) en fonction de \(n\) et \(p\). Soient \(a_1 < \cdots < a_{n-p}\) les éléments de \(A\) et \(b_1 < \cdots < b_{n+p}\) ceux de \(B\). Alors

\[e(A,A) = \sum_{1\leq i<j\leq n-p} (a_j - a_i - n) = \sum_{i=1}^{n-p} (2i - 1 - n + p)\, a_i - \binom{n-p}{2} n \tag{6}\]

et de même

\[e(B,B) = \sum_{i=1}^{n+p} (2i - 1 - n - p)\, b_i - \binom{n+p}{2} n. \tag{7}\]

Il suffit donc de maximiser

\[M = \sum_{i=1}^{n-p} (2i - 1 - n + p)\, a_i + \sum_{i=1}^{n+p} (2i - 1 - n - p)\, b_i. \tag{8}\]

On applique l'inégalité de réordonnement à la suite \(a_1, \ldots, a_{n-p}, b_1, \ldots, b_{n+p}\) (qui est une permutation de \(1, 2, \ldots, 2n\)) et à la suite des coefficients dans (8). Les coefficients des \(a_i\) sont \(n-p-1, n-p-3, \ldots, 1-n+p\), et ceux des \(b_i\) sont \(n+p-1, n+p-3, \ldots, 1-n-p\). Rangés par ordre décroissant, ce sont :

\(n + p + 1 - 2i\) pour \(i = 1, \ldots, p\) ;
\(n - p + 1 - 2i\), deux fois chacun, pour \(i = 1, \ldots, n-p\) ;
\(-(n + p + 1 - 2i)\) pour \(i = p, p-1, \ldots, 1\).

Le réordonnement (les plus grands coefficients avec les plus grands nombres) donne

\[M \leq \sum_{i=1}^{p} (n+p+1-2i)(2n+1-i) + \sum_{i=1}^{n-p} (n-p+1-2i)\big((2n+2-p-2i) + (2n+1-p-2i)\big) - \sum_{i=1}^{p} (n+p+1-2i)\, i. \tag{9}\]

En combinant (5), (6), (7) et (9) :

\[Z \leq \frac{(n-1)n(2n-1)}{3} - 2n\left(\binom{n-p}{2} + \binom{n+p}{2}\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),\]

ce qui se simplifie en

\[Z \leq n(n-1) - \frac{2}{3}\, p(p-1)(p+1).\]

Comme \(p\) est un entier positif ou nul, \(p(p-1)(p+1) \geq 0\) et donc \(Z \leq n(n-1)\). L'exemple de la solution 1 montre que cette valeur est atteinte. \(\blacksquare\)

Remarques¶

Remarque 1 (autres cas d'égalité). La valeur \(n(n-1)\) est atteinte par d'autres exemples, et les \(x_i\) ne sont pas forcément \(\pm 1\) : avec \(x_i = (-1)^i\) pour \(2 \leq i \leq 2n\), le coefficient de \(x_1\) dans \(Z\) est nul, et \(x_1\) peut être choisi librement dans \([-1, 1]\). En revanche, si tous les \(x_i\) valent \(\pm 1\), l'égalité n'a lieu que lorsque \((y_1, \ldots, y_{2n}) = (0, \pm 2, 0, \pm 2, \ldots, 0, \pm 2)\) ou \((\pm 2, 0, \pm 2, 0, \ldots, \pm 2, 0)\), d'où l'on reconstruit les \(x_i\). La somme \(\sum x_i\) n'est alors pas forcément nulle, mais vaut \(0\) ou \(\pm 2\).

Remarque 2 (autres variables auxiliaires). On peut poser \(x_{2n+i} = -x_i\) et \(y'_i = x_i + x_{i+1} + \cdots + x_{i+n-1}\) pour \(1 \leq i \leq 2n\). Comme dans la solution 1, on obtient \(Y := y_1'^2 + \cdots + y_{2n}'^2 = 2n^2 - 2Z\), et il suffit de montrer \(Y \geq 2n\). Si \(n\) est impair, chaque \(y'_i\) est impair, donc \(y_i'^2 \geq 1\). Si \(n\) est pair, chaque \(y'_i\) est pair, et l'un au moins de \(y'_i, y'_{i+1}, y'_{n+i}, y'_{n+i+1}\) est non nul, d'où \(y_i'^2 + y_{i+1}'^2 + y_{n+i}'^2 + y_{n+i+1}'^2 \geq 4\) ; en sommant pour \(i = 1, 3, \ldots, n-1\), on obtient \(Y \geq 2n\).