Aller au contenu

Shortlist 2021, A1

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

Concepts : Principe des tiroirs · Principe extrémal

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

Énoncé

Let \(n\) be an integer, and let \(A\) be a subset of \(\{0, 1, 2, 3, \ldots, 5^n\}\) consisting of \(4n + 2\) numbers. Prove that there exist \(a, b, c \in A\) such that \(a < b < c\) and \(c + 2a > 3b\).

Indices : les idées clés
  • Distances au maximum (solution 1) : si aucun triplet ne convient, la distance \(c - x_i\) au plus grand élément est multipliée par au moins \(\frac{3}{2}\) à chaque pas vers la gauche, d'où une croissance géométrique incompatible avec \(c \leq 5^n\).
  • \(\left(\frac{3}{2}\right)^4 = \frac{81}{16} > 5\) : c'est pourquoi \(4n + 2\) éléments suffisent dans \(\{0, \ldots, 5^n\}\).
  • Principe des tiroirs (solution 2) : on découpe \([0, c)\) en \(4n\) tranches géométriques \(A_k\) ; deux éléments tombent dans la même tranche.
  • Principe extrémal : on prend toujours pour \(c\) le plus grand élément de \(A\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (deux solutions).

Solution 1

On raisonne par l'absurde. Supposons qu'il existe \(4n + 2\) entiers positifs ou nuls \(x_0 < x_1 < \cdots < x_{4n+1}\) (avec \(x_{4n+1} \leq 5^n\)) qui contredisent l'énoncé. En particulier, en prenant comme \(c\) le plus grand élément \(x_{4n+1}\), on a \(x_{4n+1} + 2x_i \leq 3x_{i+1}\) pour tout \(i = 0, \ldots, 4n - 1\), ce qui donne

\[x_{4n+1} - x_i \geq \frac{3}{2}\left(x_{4n+1} - x_{i+1}\right).\]

Par une récurrence immédiate, on obtient

\[x_{4n+1} - x_i \geq \left(\frac{3}{2}\right)^{4n-i}\left(x_{4n+1} - x_{4n}\right),\]

ce qui, pour \(i = 0\), donne la contradiction

\[x_{4n+1} - x_0 \geq \left(\frac{3}{2}\right)^{4n}\left(x_{4n+1} - x_{4n}\right) = \left(\frac{81}{16}\right)^n\left(x_{4n+1} - x_{4n}\right) > 5^n \cdot 1,\]

alors que \(x_{4n+1} - x_0 \leq 5^n\). \(\blacksquare\)

Solution 2

Notons \(c\) le plus grand élément de \(A\). Pour \(k = 0, \ldots, 4n - 1\), posons

\[A_k = \left\{x \in A : \left(1 - (2/3)^k\right)c \leq x < \left(1 - (2/3)^{k+1}\right)c\right\}.\]

Remarquons que

\[\left(1 - (2/3)^{4n}\right)c = c - (16/81)^nc > c - (1/5)^nc \geq c - 1,\]

car \(c \leq 5^n\). Comme les éléments de \(A \setminus \{c\}\) sont des entiers compris entre \(0\) et \(c - 1\), les ensembles \(A_0, A_1, \ldots, A_{4n-1}\) forment une partition de \(A \setminus \{c\}\). Puisque \(A \setminus \{c\}\) a \(4n + 1\) éléments, le principe des tiroirs fournit un ensemble \(A_k\) contenant au moins deux éléments de \(A \setminus \{c\}\). Notons-les \(a\) et \(b\) avec \(a < b\), de sorte que \(a < b < c\). Alors

\[c + 2a \geq c + 2\left(1 - (2/3)^k\right)c = \left(3 - 2(2/3)^k\right)c = 3\left(1 - (2/3)^{k+1}\right)c > 3b,\]

comme voulu. \(\blacksquare\)