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é¶
Soit \(n \geq 2\) un entier, et soient \(a_1, a_2, \ldots, a_n\) des nombres réels tels que
On définit l'ensemble \(A\) par
Montrer que, si \(A\) n'est pas vide, alors
Énoncé original (anglais)
Let \(n \geq 2\) be a positive integer and \(a_1, a_2, \ldots, a_n\) be real numbers such that
Define the set \(A\) by
Prove that, if \(A\) is not empty, then
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
(couples ordonnés). On a
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
On partage les indices en quatre ensembles :
Alors
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
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
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
on a \(\sum_{(i,j) \in A} a_i a_j = -\frac{2n}{(n + 2)^2}\), qui tend vers \(0\) quand \(n \to \infty\).
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2023 A5 ★★★☆☆ : Une permutation de \(1, \ldots, 2023\) dont les écarts successifs sont tous distincts commence ou finit par au moins \(507\).
- 2018 C5 ★★★☆☆ : Un tournoi de tennis où chaque joueur paie l'hôtel de son premier à son dernier match : quel coût total minimal ?
- 2013 A4 ★★★☆☆ : Une suite périodique presque croissante vérifiant \(a_{a_i} \leq n + i - 1\) a une somme au plus \(n^2\).
- 2010 C5 ★★★☆☆ : Dans un tournoi sans un certain type de quadruplet, la somme des \((w_i - \ell_i)^3\) est positive.