Shortlist 2020, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : Ukraine
Concepts : Récurrence et constructions récursives · Principe des tiroirs
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 85 (page 87 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(S\) be a set consisting of \(n \geq 3\) positive integers, none of which is a sum of two other distinct members of \(S\). Prove that the elements of \(S\) may be ordered as \(a_1, a_2, \ldots, a_n\) so that \(a_i\) does not divide \(a_{i-1} + a_{i+1}\) for all \(i = 2, 3, \ldots, n - 1\).
Indices : les idées clés
- Observation A : dans un ensemble « bon », le plus grand de trois éléments distincts ne divise pas la somme des deux autres.
- Récurrence et constructions récursives : on renforce l'énoncé pour pouvoir insérer le maximum dans un bon ordre de \(S \setminus \{\max S\}\) (solution 1), ou retirer le plus petit élément (solution 2).
- Principe des tiroirs (solution 1) : \(n\) positions d'insertion pour \(n - 1\) « coupables » : l'un d'eux sert deux fois, ce qui contredit l'hypothèse de récurrence.
- Combinatoriser le problème (solution 2) : on remplace la divisibilité par une fonction \(f(a, b)\) arbitraire et on cherche un ordre unimodal qui l'évite.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (deux solutions et une remarque).
Dans toutes les solutions, on appelle bon un ensemble \(S\) d'entiers strictement positifs dont aucun élément n'est la somme de deux autres éléments distincts de \(S\). On utilise l'observation simple suivante.
Observation A. Si \(a\), \(b\), \(c\) sont trois éléments distincts d'un bon ensemble \(S\), avec \(b > a\) et \(b > c\), alors \(b \nmid a + c\). Sinon, comme \(b \neq a + c\), on aurait \(a + c \geq 2b\), c'est-à-dire \(b \leq \frac{a + c}{2} < \max\{a, c\}\), absurde.
Solution 1¶
On démontre l'énoncé plus fort suivant.
Affirmation. Soit \(S\) un bon ensemble de \(n \geq 2\) entiers strictement positifs. On peut ordonner ses éléments en \(a_1, a_2, \ldots, a_n\) de sorte que \(a_i \nmid a_{i-1} + a_{i+1}\) et \(a_i \nmid a_{i-1} - a_{i+1}\) pour tout \(i = 2, 3, \ldots, n - 1\).
Preuve. Disons qu'un ordre \(a_1, \ldots, a_n\) de \(S\) est joli s'il vérifie cette propriété. On raisonne par récurrence sur \(n\). Le cas \(n = 2\) est trivial : il n'y a aucune contrainte.
Soit \(n \geq 3\). Posons \(a = \max S\) et \(T = S \setminus \{a\}\) (encore bon). Par hypothèse de récurrence, \(T\) admet un ordre joli \(b_1, \ldots, b_{n-1}\). Montrons qu'on peut insérer \(a\) dans cette suite pour obtenir un ordre joli de \(S\), c'est-à-dire qu'il existe \(j \in \{1, 2, \ldots, n\}\) tel que l'ordre
soit joli.
Supposons que pour un certain \(j\), l'ordre \(N_j\) ne soit pas joli : un élément \(x\) divise la somme ou la différence de ses deux voisins. Cela n'arrivait pas dans l'ordre de \(T\), donc \(x \in \{b_{j-1}, a, b_j\}\) (si, par exemple, \(b_{j-1}\) n'existe pas, alors \(x \in \{a, b_j\}\) ; même convention dans la suite). Le cas \(x = a\) est impossible : \(a\) ne divise pas \(b_{j-1} - b_j\), car \(0 < |b_{j-1} - b_j| < a\), et \(a \nmid b_{j-1} + b_j\) par l'observation A. Donc \(x \in \{b_{j-1}, b_j\}\) ; dans ce cas, on attribue le nombre \(x\) à l'indice \(j\).
Supposons maintenant qu'aucun \(N_j\) ne soit joli. Il y a \(n\) indices \(j\) possibles et seulement \(n - 1\) éléments dans \(T\) ; par le principe des tiroirs, l'un de ces éléments, disons \(b_k\), est attribué à deux indices différents, qui sont alors nécessairement \(k\) et \(k + 1\). Cela signifie que \(b_k\) divise \(b_{k-1} + \varepsilon_1 a\) et \(a + \varepsilon_2 b_{k+1}\) pour certains signes \(\varepsilon_1, \varepsilon_2 \in \{-1, 1\}\). Mais alors
donc \(b_k \mid b_{k-1} - \varepsilon_1 \varepsilon_2 b_{k+1}\) : l'ordre de \(T\) n'était pas joli. Cette contradiction achève la récurrence. \(\blacksquare\)
Solution 2¶
On démontre à nouveau un énoncé plus fort.
Affirmation. Soit \(S\) un ensemble quelconque de \(n \geq 3\) entiers strictement positifs. On peut ordonner ses éléments en \(a_1, \ldots, a_n\) de sorte que, si \(a_i \mid a_{i-1} + a_{i+1}\), alors \(a_i = \max S\).
D'après l'observation A, cette affirmation entraîne le résultat voulu.
Pour la démontrer, introduisons la fonction \(f\) qui, à deux éléments \(a < b\) de \(S\), associe l'unique entier \(f(a, b) \in \{1, 2, \ldots, a\}\) tel que \(a \mid b + f(a, b)\). Ainsi, si \(b \mid a + c\) pour des éléments \(a < b < c\) de \(S\), alors \(a = f(b, c)\). L'affirmation découle donc du lemme combinatoire suivant.
Précision ajoutée : dans un ordre unimodal, un élément \(a_i\) intérieur autre que le maximum a un voisin plus petit \(a'\) et un voisin plus grand \(c\) ; si \(a_i \mid a' + c\), alors \(a' = f(a_i, c)\) serait voisin de \(a_i\), ce que la condition (ii) ci-dessous interdit.
Lemme. Soit \(S\) un ensemble de \(n \geq 3\) entiers strictement positifs, et \(f\) une fonction qui associe à tous \(a, b \in S\) avec \(a < b\) un entier de \(\{1, \ldots, a\}\). On peut ordonner les éléments de \(S\) en \(a_1, a_2, \ldots, a_n\) de sorte que les deux conditions suivantes soient satisfaites simultanément :
(i) unimodalité : il existe \(j \in \{1, 2, \ldots, n\}\) tel que \(a_1 < a_2 < \cdots < a_j > a_{j+1} > \cdots > a_n\) ;
(ii) évitement de \(f\) : si \(a < b\) sont deux éléments de \(S\) adjacents dans l'ordre, alors \(f(a, b)\) n'est pas adjacent à \(a\).
Preuve. Un ordre de \(S\) vérifiant (i) et (ii) est dit \(f\)-joli. On convient que \(f(x, y) = x\) pour \(x \geq y\) ; cette convention n'ajoute aucune contrainte.
On raisonne par récurrence. Pour le cas \(n = 3\), il suffit de placer le plus grand élément de \(S\) au milieu.
Pour l'hérédité, soient \(p < q\) les deux plus petits éléments de \(S\), et \(T = S \setminus \{p\}\). On définit une fonction \(g\) en associant à tous éléments \(a < b\) de \(T\) la valeur
On a bien \(g(a, b) \leq a\) pour tous \(a, b \in T\) (car \(q\) est le plus petit élément de \(T\)).
Par hypothèse de récurrence, \(T\) admet un ordre \(g\)-joli \(b_1, b_2, \ldots, b_{n-1}\). Par unimodalité, \(b_1\) ou \(b_{n-1}\) est égal à \(q\) ; ces deux cas ne diffèrent que par un renversement de l'ordre, et l'on suppose \(b_1 = q\).
D'après (1), le nombre \(f(b_2, b_3)\) est différent de \(p\) et de \(q\) (sinon \(g(b_2, b_3) = q = b_1\) serait adjacent à \(b_2\)). D'autre part, le nombre \(f(b_{n-1}, b_{n-2})\) est différent de l'un au moins de \(p\) et \(q\) ; appelons-le \(r\), et posons \(s = p + q - r\), de sorte que \(\{r, s\} = \{p, q\}\). On ordonne alors \(S\) en
Par hypothèse de récurrence et par les choix ci-dessus, cet ordre est \(f\)-joli. \(\square\)
Précision ajoutée : l'ordre est unimodal car \(s\) et \(r\) sont les deux plus petits éléments, placés aux extrémités ; pour une paire adjacente intérieure, \(f\) et \(g\) coïncident sauf si \(f = p\), et \(p\) n'est voisin que de \(b_2\) ou de \(b_{n-1}\), cas réglés par le choix de \(s\) et \(r\).
Ceci démontre le lemme, donc l'affirmation et le problème. \(\blacksquare\)
Remarques¶
Remarque 1. Dans la proposition originale, les nombres étaient supposés impairs (ce qui entraîne qu'aucun n'est somme de deux autres), et on demandait de ranger en ligne tous les nombres sauf un. La solution 2 montre que l'hypothèse « \(S\) bon » peut être affaiblie en : le plus grand élément de \(S\) n'est pas la somme de deux autres éléments de \(S\). En revanche, l'ensemble \(\{1, 2, 3\}\) montre qu'on ne peut pas simplement supprimer la condition. Le comité de sélection a examiné plusieurs versions et a retenu celle qui lui semblait la meilleure.