Aller au contenu

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é

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

\[\left\lvert \frac{a - b}{c - d} - 1 \right\rvert < \frac{1}{100000}.\]
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

\[\frac{D_{i+1}}{D_i} \geq 1 + \frac{1}{10^5}\]

est vraie pour tout \(i = 1, 2, \ldots, m - 1\), et donc

\[v - u = D_m = \frac{D_m}{D_1} = \frac{D_m}{D_{m-1}} \cdots \frac{D_3}{D_2} \cdot \frac{D_2}{D_1} \geq \left(1 + \frac{1}{10^5}\right)^{m-1}.\]

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

\[\left(1 + \frac{1}{10^5}\right)^{19 \cdot 10^5} = \left(\left(1 + \frac{1}{10^5}\right)^{10^5}\right)^{19} \geq 2^{19} = 2^9 \cdot 2^{10} > 500 \cdot 1000 > 2 \cdot 10^5,\]

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

\[\left\lvert \frac{a - b}{c - d} - 1 \right\rvert = \left\lvert \frac{z - y}{z - x} - 1 \right\rvert = \left\lvert \frac{x - y}{z - x} \right\rvert = \frac{1}{z - x} < 10^{-5}.\]

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

\[\left\lvert \frac{a - b}{c - d} - 1 \right\rvert = \left\lvert \frac{y - z}{x - z} - 1 \right\rvert = \left\lvert \frac{y - x}{x - z} \right\rvert = \frac{1}{x - z} < 10^{-5}.\]

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

\[\delta (1 + \delta)^{n(n-1)/2 - 1} > 2.\]