Shortlist 2013, A2¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Lithuania
Concepts : Principe des tiroirs · Principe extrémal
Solution officielle : Shortlist officielle 2013 (avec solutions), p. 11 (page 11 du PDF)
Énoncé¶
Montrer que, dans tout ensemble de \(2000\) nombres réels distincts, il existe deux couples \(a > b\) et \(c > d\), avec \(a \neq c\) ou \(b \neq d\), tels que
Énoncé original (anglais)
Prove that in any set of \(2000\) distinct real numbers there exist two pairs \(a > b\) and \(c > d\) with \(a \neq c\) or \(b \neq d\), such that
Indices : les idées clés
- Ranger les distances \(D_1 \leq D_2 \leq \cdots \leq D_m\) (\(m = \binom{2000}{2}\)) et normaliser \(D_1 = 1\) ; si deux distances consécutives ont un rapport \(< 1 + 10^{-5}\), c'est fini (tiroirs multiplicatifs).
- Sinon : \(D_m \geq (1 + 10^{-5})^{m-1} > 2 \cdot 10^5\), avec \(\left(1 + \frac{1}{n}\right)^n \geq 2\).
- Principe extrémal : avec \(y - x = D_1 = 1\) et \(z\) l'extrémité de \(S\) la plus éloignée de \(x\), les paires \((z, y)\) et \((z, x)\) (ou \((y, z)\) et \((x, z)\)) conviennent.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2013 (une solution et une remarque).
Solution¶
Pour un ensemble \(S\) de \(n = 2000\) réels distincts, soient \(D_1 \leq D_2 \leq \cdots \leq D_m\) les distances entre ses éléments, comptées avec multiplicité ; on a \(m = \frac{n(n-1)}{2}\). Quitte à changer d'échelle, on peut supposer que la plus petite distance entre deux éléments de \(S\) est \(D_1 = 1\). Soient \(x, y \in S\) avec \(D_1 = 1 = y - x\). Évidemment, \(D_m = v - u\) est la différence entre le plus grand élément \(v\) et le plus petit élément \(u\) de \(S\).
Si \(\frac{D_{i+1}}{D_i} < 1 + 10^{-5}\) pour un \(i = 1, 2, \ldots, m - 1\), l'inégalité voulue est vérifiée, car \(0 \leq \frac{D_{i+1}}{D_i} - 1 < 10^{-5}\). Sinon, l'inégalité inverse
est vraie pour tout \(i = 1, 2, \ldots, m - 1\), et donc
Comme \(m - 1 = \frac{n(n-1)}{2} - 1 = 1000 \cdot 1999 - 1 > 19 \cdot 10^5\), et comme \(\left(1 + \frac{1}{n}\right)^n \geq 1 + \binom{n}{1} \cdot \frac{1}{n} = 2\) pour tout \(n \geq 1\), on obtient
donc \(v - u = D_m > 2 \cdot 10^5\).
La distance de \(x\) à au moins l'un des nombres \(u\), \(v\) est au moins \(\frac{v - u}{2} > 10^5\) ; on a donc \(\lvert x - z \rvert > 10^5\) pour un \(z \in \{u, v\}\). Comme \(y - x = 1\), on a soit \(z > y > x\) (si \(z = v\)), soit \(y > x > z\) (si \(z = u\)).
Si \(z > y > x\), en prenant \(a = z\), \(b = y\), \(c = z\) et \(d = x\) (de sorte que \(b \neq d\)), on obtient
Sinon, si \(y > x > z\), on peut prendre \(a = y\), \(b = z\), \(c = x\) et \(d = z\) (de sorte que \(a \neq c\)), et l'on obtient
Le résultat suit. \(\blacksquare\)
Remarque¶
Comme le montre la solution, on peut remplacer les nombres \(2000\) et \(\frac{1}{100000}\) de l'énoncé par n'importe quels \(n \in \mathbb{Z}_{>0}\) et \(\delta > 0\) tels que
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2021 A1 ★☆☆☆☆ : Parmi \(4n + 2\) entiers de \(\{0, \ldots, 5^n\}\), trois vérifient \(c + 2a > 3b\).
- 2025 A4 ★★☆☆☆ : Une fonction non bornée, additive dès que \(f(m + n)\) est un record, est affine sur une progression arithmétique.
- 2020 C3 ★★☆☆☆ · OIM P4 : Deux compagnies de téléphériques desservent \(n^2\) stations : combien de lignes faut-il pour que deux stations soient reliées par les deux ?
- 2013 C4 ★★★☆☆ : Écrire \(n\) comme somme d'éléments de \(A\) avec le moins de termes possible n'utilise jamais plus de \(\sqrt[3]{6n}\) valeurs différentes.