Shortlist 2019, A4¶

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

Concepts : Double comptage

Solution officielle : Shortlist officielle 2019 (avec solutions), section A4 (livret PDF)

Énoncé¶

Let \(n \geq 2\) be a positive integer and \(a_1, a_2, \ldots, a_n\) be real numbers such that

\[a_1 + a_2 + \cdots + a_n = 0.\]

Define the set \(A\) by

\[A = \big\{(i, j) \;\big|\; 1 \leq i < j \leq n,\ |a_i - a_j| \geq 1\big\}.\]

Prove that, if \(A\) is not empty, then

\[\sum_{(i,j) \in A} a_i a_j < 0.\]

Indices : les idées clés

Passer au complémentaire (solution 1) : comme \(\sum_{i,j} a_i a_j = \left(\sum a_i\right)^2 = 0\), la somme sur les couples « éloignés » vaut l'opposé de la somme sur les couples « proches », qu'il suffit de montrer strictement positive.
Découper selon la position par rapport à \(-1, 0, 1\) : les ensembles \(P, Q, R, S\) d'indices avec \(a_i \leq -1\), \(-1 < a_i \leq 0\), \(0 < a_i < 1\), \(a_i \geq 1\) déterminent quels couples sont forcément proches ou éloignés.
Faire apparaître un carré : la somme se minore par \(\sum_{P \cup S} a_i^2 + \left(\sum_{Q \cup R} a_i\right)^2\) (solution 1), ou se majore par \(-\frac{(q + r)^2}{2}\) (solution 2).
Étudier les cas d'égalité pour obtenir l'inégalité stricte quand \(A\) n'est pas vide.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions et une remarque).

Solution 1¶

On définit

\[B = \big\{(i, j) \;\big|\; 1 \leq i, j \leq n,\ |a_i - a_j| \geq 1\big\}, \qquad C = \big\{(i, j) \;\big|\; 1 \leq i, j \leq n,\ |a_i - a_j| < 1\big\}\]

(couples ordonnés). On a

\[\sum_{(i,j) \in A} a_i a_j = \frac{1}{2} \sum_{(i,j) \in B} a_i a_j \quad\text{et}\quad \sum_{(i,j) \in B} a_i a_j = \sum_{1 \leq i, j \leq n} a_i a_j - \sum_{(i,j) \notin B} a_i a_j = 0 - \sum_{(i,j) \in C} a_i a_j,\]

car \(\sum_{i,j} a_i a_j = (a_1 + \cdots + a_n)^2 = 0\). Il suffit donc de montrer que si \(A\) (et donc \(B\)) n'est pas vide, alors

\[\sum_{(i,j) \in C} a_i a_j > 0.\]

On partage les indices en quatre ensembles :

\[P = \{i \mid a_i \leq -1\}, \quad Q = \{i \mid -1 < a_i \leq 0\}, \quad R = \{i \mid 0 < a_i < 1\}, \quad S = \{i \mid 1 \leq a_i\}.\]

Alors

\[\sum_{(i,j) \in C} a_i a_j \geq \sum_{i \in P \cup S} a_i^2 + \sum_{i, j \in Q \cup R} a_i a_j = \sum_{i \in P \cup S} a_i^2 + \Big(\sum_{i \in Q \cup R} a_i\Big)^2 \geq 0.\]

La première inégalité vient de ce que tous les termes positifs du membre de droite figurent dans celui de gauche (les couples \((i, i)\), et les couples de \(Q \times Q\) ou de \(R \times R\), dont l'écart est \(< 1\)), et que tous les termes négatifs du membre de gauche figurent dans celui de droite (un couple proche de signes opposés est forcément dans \((Q \cup R)^2\)). Il n'y a égalité dans la première inégalité que si les deux membres ont les mêmes termes négatifs, ce qui impose \(|a_i - a_j| < 1\) pour tous \(i, j \in Q \cup R\) ; il n'y a égalité dans la seconde que si \(P = S = \varnothing\). Mais alors \(A\) serait vide. Donc, si \(A\) n'est pas vide, l'inégalité est stricte, comme voulu. \(\blacksquare\)

Solution 2¶

On reprend \(P, Q, R, S\) comme dans la solution 1, et on pose

\[p = \sum_{i \in P} a_i, \quad q = \sum_{i \in Q} a_i, \quad r = \sum_{i \in R} a_i, \quad s = \sum_{i \in S} a_i,\]

\[t^+ = \sum_{(i,j) \in A,\ a_i a_j \geq 0} a_i a_j, \qquad t^- = \sum_{(i,j) \in A,\ a_i a_j \leq 0} a_i a_j.\]

On sait que \(p + q + r + s = 0\), et il faut montrer que \(t^+ + t^- < 0\).

On a \(t^+ \leq \frac{p^2}{2} + pq + rs + \frac{s^2}{2}\) (avec égalité seulement si \(p = s = 0\)) : les termes positifs proviennent de couples dans \(P\), dans \(P \times Q\), dans \(R \times S\) ou dans \(S\) (deux éléments de \(Q\), ou de \(R\), sont à distance \(< 1\)). Et \(t^- \leq pr + ps + qs\) (avec égalité seulement s'il n'existe pas \(i \in Q\) et \(j \in R\) avec \(a_j - a_i \geq 1\)) : les couples de \(P \times R\), \(P \times S\) et \(Q \times S\) sont tous dans \(A\), et ceux de \(Q \times R\) qui sont dans \(A\) ne font que diminuer \(t^-\). Par conséquent

\[t^+ + t^- \leq \frac{p^2 + s^2}{2} + pq + rs + pr + ps + qs = \frac{(p + q + r + s)^2}{2} - \frac{(q + r)^2}{2} = -\frac{(q + r)^2}{2} \leq 0.\]

Si \(A\) n'est pas vide et \(p = s = 0\), il existe forcément \(i \in Q\) et \(j \in R\) avec \(|a_i - a_j| \geq 1\), et les deux cas d'égalité ne peuvent donc pas avoir lieu simultanément. Ainsi \(t^+ + t^- < 0\). \(\blacksquare\)

Le texte du livret écrit \(a_j - a_i > 1\) et \(|a_i - a_j| > 1\) dans les conditions d'égalité ; il faut lire \(\geq 1\) (un couple avec un écart exactement \(1\) est dans \(A\)). Les justifications des majorations de \(t^+\) et \(t^-\) ont été ajoutées.

Remarques¶

Remarque. Le membre de droite \(0\) de l'inégalité ne peut pas être remplacé par une constante \(c < 0\) indépendante de \(n\). En effet, avec

\[a_1 = -\frac{n}{n + 2}, \qquad a_2 = \cdots = a_{n-1} = \frac{1}{n + 2}, \qquad a_n = \frac{2}{n + 2},\]

on a \(\sum_{(i,j) \in A} a_i a_j = -\frac{2n}{(n + 2)^2}\), qui tend vers \(0\) quand \(n \to \infty\).