Aller au contenu

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é

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

\[m_a \leq \frac{N}{p} < \frac{p^2 - 1}{4} \quad \text{pour tout } a = 1, 2, \ldots, p-1. \tag{1}\]

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

\[m_b \geq \frac{a}{b}\, m_a \quad \text{et} \quad m_b \geq \frac{p-a}{p-b}\, m_a.\]

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\)),

\[m_{p-1} \geq \frac{p - a}{p - (p-1)}\, m_a \geq (p - q)\,q = \frac{p^2 - 1}{4},\]

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)\)) :

\[\begin{aligned} m_k &\geq \frac{p-1}{k}\, m_{p-1} \geq \frac{p-1}{k} \cdot \frac{p - a}{p - (p-1)}\, m_a \\ &\geq \frac{p-1}{k} \cdot (p - k + 1)(k - 1) \geq \frac{k-1}{k} \cdot (p-1)(p-q) \geq \frac{1}{2} \cdot \frac{p^2 - 1}{2}, \end{aligned}\]

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

\[(m_1, m_2) = (1, 2), \quad (m_1, m_2, m_3, m_4) = (1, 2, 3, 6), \quad (m_1, \ldots, m_6) = (1, 2, 3, 4, 6, 12).\]

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\).