Shortlist 2020, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Netherlands
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 36 (page 38 du PDF)
Énoncé¶
Soit \(p\) un nombre premier impair, et posons \(N = \frac{1}{4}(p^3 - p) - 1\). Les nombres \(1, 2, \ldots, N\) sont coloriés de façon quelconque en deux couleurs, rouge et bleu. Pour tout entier \(n\) strictement positif avec \(n \leq N\), on note \(r(n)\) la proportion d'entiers rouges dans \(\{1, 2, \ldots, n\}\).
Montrer qu'il existe un entier \(a \in \{1, 2, \ldots, p - 1\}\) strictement positif tel que \(r(n) \neq a/p\) pour tout \(n = 1, 2, \ldots, N\).
Énoncé original (anglais)
Let \(p\) be an odd prime, and put \(N = \frac{1}{4}(p^3 - p) - 1\). The numbers \(1, 2, \ldots, N\) are painted arbitrarily in two colors, red and blue. For any positive integer \(n \leq N\), denote by \(r(n)\) the fraction of integers in \(\{1, 2, \ldots, n\}\) that are red.
Prove that there exists a positive integer \(a \in \{1, 2, \ldots, p - 1\}\) such that \(r(n) \neq a/p\) for all \(n = 1, 2, \ldots, N\).
Indices : les idées clés
- Raisonnement par l'absurde et symétrie des couleurs : on suppose que chaque fraction \(a/p\) est atteinte en un \(n_a = p\,m_a\), et l'on peut échanger les couleurs, ce qui remplace \(a\) par \(p - a\).
- Divisibilité : \(R(n_a) = a n_a / p\) est entier et \(p \nmid a\), donc \(p \mid n_a\).
- Monotonie du nombre de rouges : si \(m_a < m_b\), alors \(b\,m_b \geq a\,m_a\) et, en échangeant les couleurs, \((p-b)\,m_b \geq (p-a)\,m_a\).
- Principe extrémal : on considère le plus grand des \(m_a\) pour \(a \leq q\) (ou \(a \leq k - 1\)) et le plus petit indice \(k\) avec \(m_k > m_{p-1}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (une solution et deux remarques).
Solution¶
Notons \(R(n)\) le nombre d'entiers rouges dans \(\{1, 2, \ldots, n\}\), c'est-à-dire \(R(n) = n\,r(n)\). De même, notons \(B(n)\) et \(b(n) = B(n)/n\) le nombre et la proportion d'entiers bleus dans \(\{1, 2, \ldots, n\}\). Comme \(B(n) + R(n) = n\) et \(b(n) + r(n) = 1\), l'énoncé ne change pas quand on échange les couleurs.
Raisonnons par l'absurde : pour tout \(a \in \{1, 2, \ldots, p-1\}\), choisissons un entier \(n_a\) tel que \(r(n_a) = a/p\), donc \(R(n_a) = a n_a / p\). Comme \(R(n_a)\) est entier et que \(p\) premier ne divise pas \(a\), on a clairement \(p \mid n_a\) : \(n_a = p\,m_a\) pour un entier \(m_a \geq 1\), et \(R(n_a) = a\,m_a\). Sans perte de généralité, \(m_1 < m_{p-1}\) (sinon, on échange les couleurs). Notons que
La solution repose sur l'application répétée de l'observation simple suivante.
Affirmation. Si \(m_a < m_b\) pour certains \(a, b \in \{1, 2, \ldots, p-1\}\), alors
Preuve. La première inégalité découle de \(b\,m_b = R(n_b) \geq R(n_a) = a\,m_a\) (car \(n_b > n_a\) et \(R\) est croissante). La seconde s'obtient en échangeant les couleurs. \(\square\)
Précision ajoutée : les \(m_a\) sont deux à deux distincts, puisque \(r(n_a) = a/p\) prend des valeurs distinctes.
Soit \(q = \frac{p-1}{2}\). On distingue deux cas.
Cas 1 : les \(q\) nombres \(m_1, m_2, \ldots, m_q\) sont tous plus petits que \(m_{p-1}\). Soit \(m_a\) le plus grand des nombres \(m_1, \ldots, m_q\) ; comme ce sont \(q\) entiers strictement positifs distincts, \(m_a \geq q \geq a\). D'après l'affirmation (seconde inégalité, avec \(b = p - 1\)),
ce qui contredit (1).
Cas 2 : il existe \(k \leq q\) tel que \(m_k > m_{p-1}\). Choisissons pour \(k\) le plus petit indice tel que \(m_k > m_{p-1}\) ; comme \(m_1 < m_{p-1}\), on a \(1 < k \leq q < p - 1\).
Soit \(m_a\) le plus grand des nombres \(m_1, \ldots, m_{k-1}\) ; alors \(a \leq k - 1 \leq m_a < m_{p-1}\). En appliquant l'affirmation deux fois (la première inégalité avec \((p-1, k)\), puis la seconde avec \((a, p-1)\)) :
ce qui contredit encore (1).
Dans les deux cas on aboutit à une contradiction, ce qui démontre l'énoncé. \(\blacksquare\)
Remarques¶
Remarque 1. L'argument du cas 2, après une légère modification des estimations finales, s'applique dès qu'il existe \(k < \frac{3(p+1)}{4}\) avec \(m_k > m_{p-1}\). Il ne semble cependant pas fonctionner s'il n'existe pas de tel \(k\). (Le livret écrit \(a_k < a_{p-1}\) ; vu les notations de la solution, il faut lire \(m_k > m_{p-1}\).)
Remarque 2. Pour \(p\) petit, on peut colorier \(\{1, 2, \ldots, N+1\}\) de sorte qu'il existe des nombres \(m_1, \ldots, m_{p-1}\) avec \(r(p\,m_a) = a/p\). Pour \(p = 3, 5, 7\), on trouve des coloriages donnant respectivement
Ainsi, pour les petites valeurs de \(p\), le nombre \(N\) de l'énoncé ne peut pas être augmenté. Une analyse fine des estimations montre cependant qu'on peut l'augmenter légèrement pour \(p \geq 11\).
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2020 N3 ★★☆☆☆ · OIM P5 : Une suite non constante peut-elle avoir chaque moyenne arithmétique de deux termes égale à une moyenne géométrique de termes ?
- 2011 N5 ★★★☆☆ · OIM P5 : Si \(f(m - n)\) divise \(f(m) - f(n)\), alors les valeurs de \(f\) se divisent les unes les autres par ordre de taille.
- 2008 C3 ★★★☆☆ : Deux points entiers sont amis s'ils forment avec un troisième un triangle d'aire \(k\) : quel \(k\) permet plus de \(200\) amis mutuels ?
- 2021 N7 ★★★★☆ : Si \(a_{n+2m}\) divise \(a_n + a_{n+m}\), la suite finit par être périodique.