Aller au contenu

Shortlist 2022, N5

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : United Kingdom

Concepts : Congruences, théorèmes de Fermat et d'Euler · Double comptage

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 66 (page 68 du PDF)

Énoncé

For each \(1 \leq i \leq 9\) and \(T \in \mathbb{N}\), define \(d_i(T)\) to be the total number of times the digit \(i\) appears when all the multiples of \(1829\) between \(1\) and \(T\) inclusive are written out in base \(10\).

Show that there are infinitely many \(T \in \mathbb{N}\) such that there are precisely two distinct values among \(d_1(T), d_2(T), \ldots, d_9(T)\).

Indices : les idées clés
  • Théorème d'Euler : comme \(1829\) est premier avec \(10\), il existe des \(k\) arbitrairement grands avec \(1829 \mid 10^k - 1\).
  • Invariance par permutation circulaire des chiffres : si \(n \mid 10^k - 1\), un nombre à \(k\) chiffres (zéros en tête autorisés) est multiple de \(n\) si et seulement si sa permutation circulaire l'est.
  • Double comptage : on compte les apparitions du chiffre \(i\) position par position ; chaque position donne le même nombre, celui des multiples de \(n\) commençant par \(i\).
  • Passer de \(T = 10^k - 1\) à \(T = 10^k - 2\) : retirer le multiple \(99\ldots9\) ne change que \(d_9\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution et une remarque).

Solution

Posons \(n = 1829\). Choisissons d'abord \(k\) tel que \(n \mid 10^k - 1\) ; par exemple, tout multiple de \(\varphi(n)\) convient, par le théorème d'Euler, puisque \(n\) est premier avec \(10\). Nous allons montrer que \(T = 10^k - 1\) ou \(T = 10^k - 2\) a la propriété voulue ; cela conclut, car \(k\) peut être pris arbitrairement grand.

Réduction. Il suffit de montrer que \(\#\{d_i(10^k - 1) : 1 \leq i \leq 9\} \leq 2\). En effet, si

\[\#\{d_i(10^k - 1) : 1 \leq i \leq 9\} = 1,\]

alors, puisque \(10^k - 1\), formé uniquement de \(9\), est un multiple de \(n\), on a

\[d_i(10^k - 2) = d_i(10^k - 1) \text{ pour } i \in \{1, \ldots, 8\}, \qquad d_9(10^k - 2) < d_9(10^k - 1).\]

Cela signifie que \(\#\{d_i(10^k - 2) : 1 \leq i \leq 9\} = 2\). Et si l'ensemble des \(d_i(10^k-1)\) a exactement deux éléments, \(T = 10^k - 1\) convient.

Une observation. Soit \(\overline{a_{k-1}a_{k-2}\ldots a_0}\) l'écriture décimale d'un nombre de \(\{1, \ldots, 10^k - 1\}\), éventuellement avec des zéros en tête. Alors \(\overline{a_{k-1}a_{k-2}\ldots a_0}\) est divisible par \(n\) si et seulement si \(\overline{a_{k-2}\ldots a_0a_{k-1}}\) l'est. Cela découle de ce que

\[10 \cdot \overline{a_{k-1}a_{k-2}\ldots a_0} - \overline{a_{k-2}\ldots a_0a_{k-1}} = (10^k - 1) \cdot a_{k-1}\]

est divisible par \(n\) (et \(n\) est premier avec \(10\)).

Cette observation montre que l'ensemble des multiples de \(n\) entre \(1\) et \(10^k - 1\) est invariant par permutation circulaire simultanée des chiffres (les nombres étant écrits avec \(k\) chiffres, zéros en tête compris).

Double comptage. Par conséquent, pour chaque \(i \in \{1, \ldots, 9\}\), le nombre d'apparitions du chiffre \(i\) en une position donnée parmi ces multiples est le même pour les \(k\) positions ; donc \(d_i(10^k - 1)\) vaut \(k\) fois le nombre de multiples de \(n\) à \(k\) chiffres qui commencent par le chiffre \(i\). Ces derniers sont les multiples de \(n\) de l'intervalle \([i \cdot 10^{k-1}, (i+1) \cdot 10^{k-1})\), de longueur \(10^{k-1}\) ; leur nombre vaut donc \(\lfloor 10^{k-1}/n \rfloor\) ou \(1 + \lfloor 10^{k-1}/n \rfloor\). On conclut que \(\#\{d_i(10^k - 1)\} \leq 2\). \(\blacksquare\)

Remarques

Remarque. Une analyse plus fine montre que \(\#\{d_i(10^k - 1) : 1 \leq i \leq 9\} = 1\) si et seulement si \(n \equiv 1 \pmod{10}\), ce qui n'est pas le cas pour \(n = 1829\).