Shortlist 2024, N2¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : Netherlands
Concepts : Principe extrémal · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2024 (avec solutions), section N2 (livret PDF)
Énoncé¶
Determine all finite, nonempty sets \(S\) of positive integers such that for every \(a, b \in S\) there exists \(c \in S\) with \(a \mid b + 2c\).
Indices : les idées clés
- Réduction par homogénéité : on peut diviser tous les éléments par leur PGCD ; ils deviennent alors tous impairs.
- Principe extrémal : regarder le plus grand élément \(d\) (et le deuxième plus grand, solution 1).
- Congruences : modulo \(4\) (solution 1), ou modulo \(d\) : \(e \in S \Rightarrow \frac{d - e}{2} \in S\) (solution 2), \(-\frac{b}{2}\) et \(-2e\) « appartiennent à \(S\) modulo \(d\) » (solution 3).
- Itération d'une application (solutions 2 et 3, remarque) : \(e \mapsto d - 2e\) éloigne de \(\frac{d}{3}\), ce qui force \(e = \frac{d}{3}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (trois solutions et une remarque).
Réponse : les ensembles \(S = \{t\}\) et \(S = \{t, 3t\}\), pour tout entier \(t \geq 1\).
Solution 1¶
Réduction. On peut diviser tous les éléments de \(S\) par un facteur commun ; après cela, ils ne sont pas tous pairs. Comme \(a \nmid b + 2c\) lorsque \(a\) est pair et \(b\) impair, les éléments de \(S\) sont alors tous impairs. On distingue trois cas.
Cas 1 : \(|S| = 1\). L'ensemble \(S = \{t\}\) convient clairement.
Cas 2 : \(|S| = 2\). Soit \(S = \{r, s\}\) avec \(r < s\). Alors \(s \mid r + 2r\) ou \(s \mid r + 2s\) ; dans les deux cas \(s \mid 3r\). On ne peut pas avoir \(s = \frac{3r}{2}\) puisque \(r\) est impair, donc \(s = 3r\) et \(S = \{r, 3r\}\), qui convient (on vérifie les cas pour \(a\) et \(b\)).
Cas 3 : \(|S| \geq 3\). Comme tous les éléments sont impairs, pour tous \(b, c \in S\), \(b + 2c \not\equiv b \pmod 4\). Si \(a \mid b + 2c\) avec \(a \equiv b \pmod 4\), alors \(b + 2c = ka\) avec \(ka \equiv a + 2 \pmod 4\), donc \(k \equiv 3 \pmod 4\) et \(k \geq 3\). Si \(a\) est le plus grand élément de \(S\) (principe extrémal) et \(b < a\), on a \(b + 2c < 3a\) : contradiction. Ainsi, aucun élément \(b < a\) n'est congru au plus grand élément \(a\) modulo \(4\), et donc tous les éléments autres que le plus grand sont congrus entre eux modulo \(4\).
Soient \(d\) et \(e\) le plus grand et le deuxième plus grand élément de \(S\), et \(f \neq d, e\) un autre élément. Il existe \(c \in S\) avec \(e \mid f + 2c\) ; comme \(e \equiv f \pmod 4\), ce qui précède donne \(f + 2c \geq 3e\), donc \(c > e\). Comme \(e\) est le deuxième plus grand élément, \(c = d\) : ainsi \(e \mid f + 2d\). Ceci vaut pour tout \(f \in S\) avec \(f < e\), mais ne peut avoir lieu que pour au plus un tel \(f\) (un seul entier de \(]0, e[\) est congru à \(-2d\) modulo \(e\)). Donc \(|S| \leq 3\).
Les éléments de \(S\) sont donc \(d > e > f\), tous impairs, avec \(e \equiv f \pmod 4\), \(d \not\equiv e \pmod 4\), et \(e \mid f + 2d\). Par ailleurs, il existe \(c \in S\) avec \(d \mid f + 2c\), et \(c \neq d\) car \(d \nmid f\) (puisque \(d > f\)), donc \(c \leq e\). Comme \(d \leq f + 2c \leq f + 2e < 3e\), on a \(e > \frac{d}{3}\). Comme \(f + 2c\) est impair, multiple de \(d\) et \(< 3d\), on a \(f + 2c = d\).
Sous-cas 3.1 : \(c = f\). Alors \(d = 3f\) et \(e \mid f + 2d = 7f\). Comme \(f < e < 3f\), \(e\) est impair et \(e \equiv f \pmod 4\), on obtient \(e = \frac{7f}{3}\) : les éléments sont proportionnels à \(\{3, 7, 9\}\). Mais pour \(a = 7\) et \(b = 9\), aucun \(c\) ne convient (\(9 + 2 \cdot 3 = 15\), \(9 + 2 \cdot 7 = 23\), \(9 + 2 \cdot 9 = 27\) ne sont pas multiples de \(7\)).
Sous-cas 3.2 : \(c = e\). Alors \(d = f + 2e\) et \(e \mid f + 2d = 3f + 4e\), donc \(e \mid 3f\). Comme \(e > f\), on a \(\frac{3f}{e} \in \{1, 2\}\), donc \(e = 3f\) ou \(e = \frac{3f}{2}\) : le premier cas contredit \(e \equiv f \pmod 4\) (car \(3f - f = 2f \equiv 2 \pmod 4\)), le second contredit l'imparité de \(e\). Contradiction.
Donc \(|S| \leq 2\), et les solutions sont celles annoncées. \(\blacksquare\)
Solution 2¶
Comme dans la solution 1, on se ramène au cas où tous les éléments de \(S\) sont impairs. Les ensembles à un élément conviennent ; montrons que si \(|S| \geq 2\), alors \(|S| = 2\) et \(S = \{t, 3t\}\).
Soit \(d\) le plus grand élément. Pour tout \(e \in S\) avec \(e \neq d\), il existe \(f \in S\) tel que \(d \mid e + 2f\). Donc \(2f \equiv -e \equiv d - e \pmod d\). Or \(d - e\) est pair (tous les éléments sont impairs) et \(d\) est impair, donc \(\frac{d - e}{2}\) est entier et (congruences, \(2\) étant inversible modulo \(d\)) \(f \equiv \frac{d - e}{2} \pmod d\). De plus \(0 < \frac{d - e}{2} < d\) et \(0 < f \leq d\), donc \(f = \frac{d - e}{2}\). Conclusion : pour tout \(e \in S\) avec \(e \neq d\), l'entier \(\frac{d - e}{2}\) est aussi dans \(S\), et il est différent de \(d\).
Notons \(e_1 < e_2 < \cdots < e_k < d\) les éléments de \(S\), avec \(k \geq 1\). Les nombres \(\frac{d - e_1}{2} > \frac{d - e_2}{2} > \cdots > \frac{d - e_k}{2}\) sont \(k\) éléments distincts de \(S \setminus \{d\}\), donc ce sont exactement \(e_k > \cdots > e_1\). En particulier \(e_1 = \frac{d - e_k}{2}\) et \(e_k = \frac{d - e_1}{2}\), d'où \(2e_1 + e_k = d = 2e_k + e_1\). Donc \(e_1 = e_k\), \(k = 1\), et \(d = 2e_1 + e_1 = 3e_1\). Ainsi \(S = \{e_1, 3e_1\}\). \(\blacksquare\)
Solution 3¶
Comme dans la solution 1, on se ramène au cas où tous les éléments de \(S\) sont impairs, et l'on montre que si \(|S| \geq 2\), alors \(S = \{t, 3t\}\).
Soit \(d\) le plus grand élément et \(e \in S\) un autre élément. On écrit « \(x \in S \pmod d\) » si l'unique \(y \in \{1, \ldots, d\}\) tel que \(x \equiv y \pmod d\) appartient à \(S\). Par le choix de \(d\) maximal, si \(x \in S\) et \(x \neq d\), alors \(x \not\equiv 0 \pmod d\).
La condition implique : si \(b \in S\), alors \(-\frac{b}{2} \in S \pmod d\) (\(2\) est inversible modulo \(d\)). En itérant, \(-\frac{b}{2} \in S \Rightarrow \frac{b}{4} \in S \pmod d\), et plus généralement \(b \in S \Rightarrow \frac{b}{(-2)^k} \in S \pmod d\) pour tout \(k\). Comme \(d\) est impair, il existe \(g\) avec \((-2)^g \equiv 1 \pmod d\) (ordre de \(-2\) modulo \(d\)) ; avec \(k = g - 1\), on obtient :
Si \(e > \frac{d}{2}\), alors \(-2e \in S \pmod d\) et \(d - 2e < 0\), donc \(2d - 2e \in S\) (car \(0 < 2d - 2e < d\)), ce qui contredit l'absence d'éléments pairs. Donc \(e < \frac{d}{2}\) pour tout \(e \in S \setminus \{d\}\), et alors \(e \in S \Rightarrow d - 2e \in S\). Comme \(d - 2e \neq d\), on doit avoir \(d - 2e < \frac{d}{2}\), soit \(e > \frac{d}{4}\).
Soit \(\lambda \in (0, 1)\) et supposons avoir prouvé \(e > \lambda d\) pour tout \(e \in S \setminus \{d\}\). Alors \(d - 2e > \lambda d\) (car \(d - 2e \in S \setminus \{d\}\)), soit \(e < \frac{(1 - \lambda)d}{2}\). Alors \(d - 2e < \frac{(1 - \lambda)d}{2}\), soit \(e > \frac{(1 + \lambda)d}{4}\). Posons \(\lambda_0 = \frac{1}{4}\) et \(\lambda_i = \frac{1 + \lambda_{i-1}}{4}\) pour \(i \geq 1\) : on a montré que \(e > \lambda_i d\) pour tout \(e \in S \setminus \{d\}\) et tout \(i\). La suite \((\lambda_i)\) est croissante et majorée par \(\frac{1}{3}\), donc converge vers une limite \(\ell\) vérifiant \(\ell = \frac{1 + \ell}{4}\), soit \(\ell = \frac{1}{3}\). Donc \(e \geq \frac{d}{3}\) ; mais alors \(d - 2e \geq \frac{d}{3}\) (appliqué à l'élément \(d - 2e\)) donne \(e \leq \frac{d}{3}\). Ainsi \(e = \frac{d}{3}\), et \(S = \left\{\frac{d}{3}, d\right\}\). \(\blacksquare\)
Remarques¶
Remarque (autre fin pour la solution 3). Après avoir montré que \(e \in S \setminus \{d\}\) implique \(d - 2e \in S \setminus \{d\}\), on peut remarquer que
Considérons \(e \in S \setminus \{d\}\) qui maximise \(\left|e - \frac{d}{3}\right|\). Si \(e \neq \frac{d}{3}\), l'égalité ci-dessus donne \(\left|(d - 2e) - \frac{d}{3}\right| > \left|e - \frac{d}{3}\right|\), ce qui contredit la maximalité. Donc \(S \setminus \{d\}\) est vide ou égal à \(\left\{\frac{d}{3}\right\}\), ce qui termine la preuve.