Shortlist 2016, A3¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Récurrence et constructions récursives · Principe des tiroirs
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 14 (page 17 du PDF)
Énoncé¶
Trouver tous les entiers \(n \geq 3\) ayant la propriété suivante : pour tous nombres réels \(a_1, a_2, \ldots, a_n\) et \(b_1, b_2, \ldots, b_n\) vérifiant \(|a_k| + |b_k| = 1\) pour \(1 \leq k \leq n\), il existe \(x_1, x_2, \ldots, x_n\), chacun égal à \(-1\) ou à \(1\), tels que
Énoncé original (anglais)
Find all integers \(n \geq 3\) with the following property: for all real numbers \(a_1, a_2, \ldots, a_n\) and \(b_1, b_2, \ldots, b_n\) satisfying \(|a_k| + |b_k| = 1\) for \(1 \leq k \leq n\), there exist \(x_1, x_2, \ldots, x_n\), each of which is either \(-1\) or \(1\), such that
Indices : les idées clés
- Contre-exemple par parité pour \(n\) pair : avec des \(a_k, b_k \in \{0, 1\}\) bien choisis, les deux sommes sont des entiers impairs, donc chacune vaut au moins \(1\) en valeur absolue.
- Signes alternés après tri (solution 1) : on trie les \(a_k\) et on prend \(x_k = (-1)^{k+1}\) ; les sommes alternées d'une suite monotone sont encadrées.
- Récurrence et constructions récursives (solution 2) : récurrence de \(n-2\) à \(n\) sur les entiers impairs, en choisissant \(x_1, x_2\) en dernier.
- Principe des tiroirs (solution 2) : trois indices de même type, puis deux \(a_k\) distants d'au plus \(\frac{1}{2}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (deux solutions).
Réponse. Les entiers cherchés sont exactement les entiers impairs \(n \geq 3\).
Solution 1¶
On note (1) l'inégalité \(\left| \sum x_k a_k \right| + \left| \sum x_k b_k \right| \leq 1\) à obtenir.
Cas \(n\) pair (\(n \geq 4\)) : la propriété est fausse. Prenons
On a bien \(|a_k| + |b_k| = 1\) pour tout \(k\). Quel que soit le choix des \(x_k \in \{-1, 1\}\), la somme \(\sum_{k=1}^n x_k a_k = x_n\) est un entier impair, et \(\sum_{k=1}^n x_k b_k = x_1 + \cdots + x_{n-1}\) est une somme d'un nombre impair de termes \(\pm 1\), donc aussi un entier impair. Ainsi les deux valeurs absolues valent au moins \(1\), et (1) ne peut pas être vérifiée.
Cas \(n\) impair (\(n \geq 3\)) : la propriété est vraie. Quitte à remplacer le couple \((a_k, b_k)\) par \((-a_k, -b_k)\) et \(x_k\) par \(-x_k\), on peut supposer \(b_k \geq 0\) pour tout \(k\). Quitte à renuméroter, on peut aussi supposer
Montrons que le choix \(x_k = (-1)^{k+1}\) pour \(1 \leq k \leq n\) convient. Posons
On a
puisque \(a_1 \geq a_2 \geq \cdots \geq a_m\) (si \(m\) est impair, il reste un terme isolé \(a_m\) à la fin, lui aussi positif). D'autre part,
De même (comme \(n\) est impair, \(x_n = 1\), et les signes alternent en remontant à partir de \(a_n\)),
et
Par hypothèse, \(a_k + b_k = 1\) pour \(1 \leq k \leq m\) et \(-a_k + b_k = 1\) pour \(m+1 \leq k \leq n\). On en déduit
car \(\sum_{k=1}^n x_k = 1\) (\(n\) impair). Il reste donc à prouver
Par symétrie, on peut supposer \(s \geq t\). Si \(1 - s - t \geq 0\), alors
Si \(1 - s - t \leq 0\), alors
L'inégalité est vraie dans les deux cas.
Les entiers cherchés sont donc exactement les entiers impairs \(n \geq 3\). \(\blacksquare\)
Solution 2¶
Le cas pair se traite comme dans la solution 1. Pour le cas impair, on raisonne par récurrence sur \(n\) (de \(n - 2\) à \(n\)).
Initialisation : \(n = 3\). Quitte à changer \((a_k, b_k)\) en \((-a_k, -b_k)\) et à renuméroter, on peut supposer \(a_1 \geq a_2 \geq a_3 \geq 0\) ; chaque \(b_k\) vaut alors \(a_k - 1\) ou \(1 - a_k\). Quitte à remplacer tous les \(b_k\) par \(-b_k\), on peut supposer \(b_1 = a_1 - 1\).
- Cas 1 : \(b_2 = a_2 - 1\) et \(b_3 = a_3 - 1\). On prend \((x_1, x_2, x_3) = (1, -1, 1)\). Soit \(c = a_1 - a_2 + a_3\), de sorte que \(0 \leq c \leq 1\). Alors \(|b_1 - b_2 + b_3| = |a_1 - a_2 + a_3 - 1| = 1 - c\), donc \(|c| + |b_1 - b_2 + b_3| = 1\).
-
Cas 2 : \(b_2 = 1 - a_2\) et \(b_3 = 1 - a_3\). On prend \((x_1, x_2, x_3) = (1, -1, 1)\) et \(c = a_1 - a_2 + a_3 \in [0, 1]\). Comme \(a_3 \leq a_2\) et \(a_1 \leq 1\),
\[c - 1 \leq b_1 - b_2 + b_3 = a_1 + a_2 - a_3 - 1 \leq 1 - c.\]Donc \(|b_1 - b_2 + b_3| \leq 1 - c\) et \(|c| + |b_1 - b_2 + b_3| \leq 1\).
-
Cas 3 : \(b_2 = a_2 - 1\) et \(b_3 = 1 - a_3\). On prend \((x_1, x_2, x_3) = (-1, 1, 1)\) et \(c = -a_1 + a_2 + a_3\). Si \(c \geq 0\), alors \(a_3 \leq 1\) et \(a_2 \leq a_1\) donnent
\[c - 1 \leq -b_1 + b_2 + b_3 = -a_1 + a_2 - a_3 + 1 \leq 1 - c.\]Si \(c < 0\), alors \(a_1 \leq a_2 + 1\) et \(a_3 \geq 0\) donnent
\[-c - 1 \leq -b_1 + b_2 + b_3 = -a_1 + a_2 - a_3 + 1 \leq 1 + c.\]Dans les deux cas \(|-b_1 + b_2 + b_3| \leq 1 - |c|\), d'où \(|c| + |-b_1 + b_2 + b_3| \leq 1\).
-
Cas 4 : \(b_2 = 1 - a_2\) et \(b_3 = a_3 - 1\). On prend \((x_1, x_2, x_3) = (-1, 1, 1)\) et \(c = -a_1 + a_2 + a_3\). Si \(c \geq 0\), alors \(a_2 \leq 1\) et \(a_3 \leq a_1\) donnent
\[c - 1 \leq -b_1 + b_2 + b_3 = -a_1 - a_2 + a_3 + 1 \leq 1 - c.\]Si \(c < 0\), alors \(a_1 \leq a_3 + 1\) et \(a_2 \geq 0\) donnent
\[-c - 1 \leq -b_1 + b_2 + b_3 = -a_1 - a_2 + a_3 + 1 \leq 1 + c.\]Dans les deux cas \(|-b_1 + b_2 + b_3| \leq 1 - |c|\), d'où \(|c| + |-b_1 + b_2 + b_3| \leq 1\).
On a trouvé \(x_1, x_2, x_3\) convenables dans chaque cas.
Hérédité. Soit \(n \geq 5\) impair, et supposons le résultat vrai pour les entiers impairs plus petits. On peut encore supposer \(a_k \geq 0\) pour tout \(k\), et chaque \(b_k\) vaut \(a_k - 1\) ou \(1 - a_k\). Par le principe des tiroirs, il y a au moins trois indices \(k\) de même type ; quitte à changer tous les \(b_k\) en \(-b_k\) et à renuméroter, \(b_k = a_k - 1\) pour \(k = 1, 2, 3\). Encore par le principe des tiroirs, comme \(a_1, a_2, a_3\) sont dans \([0, 1]\), deux d'entre eux diffèrent d'au plus \(\frac{1}{2}\) ; quitte à renuméroter, on peut supposer
Par hypothèse de récurrence (appliquée aux \(n - 2\) couples d'indices \(3, \ldots, n\)), on peut choisir \(x_3, \ldots, x_n\) tels que \(a' = \sum_{k=3}^n x_k a_k\) et \(b' = \sum_{k=3}^n x_k b_k\) vérifient \(|a'| + |b'| \leq 1\). Quitte à changer tous ces \(x_k\) de signe, on peut supposer \(a' \geq 0\).
-
Cas 1 : \(b' \geq 0\). On prend \((x_1, x_2) = (-1, 1)\). Alors
\[|-a_1 + a_2 + a'| + |-(a_1 - 1) + (a_2 - 1) + b'| = |a' - d| + |b' - d| \leq \max\{a' + b' - 2d,\ a' - b',\ b' - a',\ 2d - a' - b'\} \leq 1,\]car \(0 \leq a', b'\), \(a' + b' \leq 1\) et \(0 \leq d \leq \frac{1}{2}\).
-
Cas 2 : \(0 > b' \geq -a'\). On prend \((x_1, x_2) = (-1, 1)\) ; la quantité vaut encore \(|a' - d| + |b' - d|\). Si \(a' - d \geq 0\), elle vaut \(a' - b' = |a'| + |b'| \leq 1\). Si \(a' - d < 0\), elle vaut \(2d - a' - b' \leq 2d \leq 1\) (car \(a' + b' \geq 0\)).
-
Cas 3 : \(b' < -a'\). On prend \((x_1, x_2) = (1, -1)\). Alors
\[|a_1 - a_2 + a'| + |(a_1 - 1) - (a_2 - 1) + b'| = |d + a'| + |d + b'|.\]Si \(d + b' \geq 0\), cela vaut \(2d + a' + b' < 2d \leq 1\). Si \(d + b' < 0\), cela vaut \(a' - b' = |a'| + |b'| \leq 1\).
On a donc trouvé \(x_1, \ldots, x_n\) vérifiant (1) dans tous les cas, et par récurrence la propriété est vraie pour tout entier impair \(n \geq 3\). \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2023 C2 ★☆☆☆☆ : Quelle longueur maximale pour une suite d'entiers bornés sans bloc consécutif annulé par un choix de signes ?
- 2020 C2 ★☆☆☆☆ : \(41\) sommets noirs et \(59\) blancs d'un \(100\)-gone : \(24\) quadrilatères disjoints ont chacun trois sommets d'une couleur et un de l'autre.
- 2023 C3 ★★☆☆☆ · OIM P5 : Un cercle rouge par ligne d'un triangle : quel nombre de cercles rouges un chemin descendant est-il sûr de rencontrer ?
- 2020 N7 ★★★★★ : Un ensemble sans somme de deux éléments se range de sorte qu'aucun terme ne divise la somme de ses voisins.