Shortlist 2007, N3¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Netherlands
Concepts : Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs · Double comptage
Solution officielle : Shortlist officielle 2007 (avec solutions), p. 57 (page 58 du PDF)
Énoncé¶
Let \(X\) be a set of \(10\,000\) integers, none of them is divisible by \(47\). Prove that there exists a \(2007\)-element subset \(Y\) of \(X\) such that \(a - b + c - d + e\) is not divisible by \(47\) for any \(a, b, c, d, e \in Y\).
Indices : les idées clés
- Ensemble modèle : \(J = \{-9, -7, \ldots, 7, 9\}\) (dix impairs) est « bon » : \(a - b + c - d + e\) est impair et compris entre \(-45\) et \(45\), donc jamais multiple de \(47\).
- Dilatations : \(A_k = \{x \in X : kx \bmod 47 \in J\}\) est bon pour chaque \(k = 1, \ldots, 46\).
- Double comptage : chaque \(x\) appartient à exactement \(10\) ensembles \(A_k\), donc \(\sum \lvert A_k \rvert = 100\,000\) et l'un a au moins \(\frac{100\,000}{46} > 2007\) éléments (tiroirs).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution et une remarque).
Solution¶
On dit qu'un ensemble \(M\) d'entiers est bon si \(47 \nmid a - b + c - d + e\) pour tous \(a, b, c, d, e \in M\).
Considérons l'ensemble \(J = \{-9, -7, -5, -3, -1, 1, 3, 5, 7, 9\}\). Montrons que \(J\) est bon. En effet, pour tous \(a, b, c, d, e \in J\), le nombre \(a - b + c - d + e\) est impair et
Mais il n'y a aucun nombre impair divisible par \(47\) entre \(-45\) et \(45\).
Pour tout \(k = 1, \ldots, 46\), considérons l'ensemble
Si \(A_k\) n'est pas bon, alors \(47 \mid a - b + c - d + e\) pour certains \(a, b, c, d, e \in A_k\), donc \(47 \mid ka - kb + kc - kd + ke\). Mais l'ensemble \(J\) contient des nombres ayant les mêmes restes modulo \(47\), donc \(J\) ne serait pas bon non plus. C'est une contradiction ; chaque \(A_k\) est donc une partie bonne de \(X\).
Il suffit alors de prouver qu'il existe un nombre \(k\) tel que \(\lvert A_k \rvert \geq 2007\). Remarquons que chaque \(x \in X\) appartient à exactement \(10\) ensembles \(A_k\). Alors
donc, pour une certaine valeur de \(k\), on a
Cela termine la preuve. \(\blacksquare\)
Remarque¶
Pour la solution, il est essentiel de trouver un bon ensemble formé de \(10\) résidus différents. En effet, considérons un ensemble \(X\) dont la répartition des résidus non nuls est presque uniforme (chaque résidu apparaît \(217\) ou \(218\) fois). Soit \(Y \subset X\) une bonne partie à \(2007\) éléments. Alors l'ensemble \(K\) de tous les résidus apparaissant dans \(Y\) contient au moins \(10\) résidus, et cet ensemble est évidemment bon.
D'autre part, il n'existe aucun bon ensemble \(K\) formé de \(11\) résidus différents. Le théorème de Cauchy-Davenport affirme que, pour tous ensembles \(A\), \(B\) de résidus modulo un nombre premier \(p\),
Donc, si \(\lvert K \rvert \geq 11\), alors \(\lvert K + K \rvert \geq 21\), \(\lvert K + K + K \rvert \geq 31 > 47 - \lvert K + K \rvert\), donc \(\lvert K + K + K + (-K) + (-K) \rvert = 47\), et \(0 \equiv a + c + e - b - d \pmod{47}\) pour certains \(a, b, c, d, e \in K\).
Par le même raisonnement, on voit qu'un bon ensemble \(K\) de \(10\) résidus doit vérifier les égalités \(\lvert K + K \rvert = 19 = 2\lvert K \rvert - 1\) et \(\lvert K + K + K \rvert = 28 = \lvert K + K \rvert + \lvert K \rvert - 1\). On peut prouver que, dans ce cas, l'ensemble \(K\) est formé de \(10\) résidus en progression arithmétique. On en déduit facilement que l'ensemble \(K\) est de la forme \(aJ\) pour un certain résidu \(a\) non nul.