Aller au contenu

Shortlist 2024, N5

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

Concepts : Partie entière et majorations · Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2024 (avec solutions), section N5 (livret PDF)

Énoncé

Let \(S\) be a finite nonempty set of prime numbers. Let \(1 = b_1 < b_2 < \cdots\) be the sequence of all positive integers whose prime divisors all belong to \(S\). Prove that, for all but finitely many positive integers \(n\), there exist positive integers \(a_1, a_2, \ldots, a_n\) such that

\[\frac{a_1}{b_1} + \frac{a_2}{b_2} + \cdots + \frac{a_n}{b_n} = \left\lceil \frac{1}{b_1} + \frac{1}{b_2} + \cdots + \frac{1}{b_n} \right\rceil.\]
Indices : les idées clés
  • Produit eulérien : \(\sum_i \frac{1}{b_i} = \prod_{p \in S} \frac{p}{p-1}\) ; hors des cas \(|S| = 1\) et \(S = \{2, 3\}\), ce produit n'est pas entier, ce qui laisse une marge \(\alpha > 0\) sous la partie entière supérieure.
  • Partie entière et majorations : pour \(n\) grand, \(\left\lceil \sum_{j \leq n} \frac{1}{b_j} \right\rceil = \left\lceil \prod_{p \in S} \frac{p}{p-1} \right\rceil\), et il suffit de rendre les « excédents » plus petits que \(\alpha\).
  • Congruences, théorèmes de Fermat et d'Euler (solution 1) : chaque \(a_{i_p}\) est choisi grâce à un inverse modulo \(p^{e_p - c}\) pour éliminer les grandes puissances de \(p\) au dénominateur.
  • Valuations p-adiques et lemme LTE : regroupement selon \(\nu_3(b_i)\) pour \(S = \{2,3\}\), et élimination prime par prime des facteurs du dénominateur (solution 2).
  • Divisibilité, PGCD et algorithme d'Euclide (solution 3) : le choix \(a_i = b_i / \operatorname{pgcd}(b_i, b_j)\) rend toutes les fractions multiples de \(\frac{1}{b_j}\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (trois solutions).

Solution 1

Cas \(|S| = 1\). Si \(S = \{p\}\), alors \(b_i = p^{i-1}\) et, pour \(n \geq 2\), \(\left\lceil \sum_{i=0}^{n-1} \frac{1}{p^i} \right\rceil = 2\). On prend \(a_1 = \cdots = a_{n-1} = 1\) et \(a_n = p^{n-1} - (p + p^2 + \cdots + p^{n-2})\), ce qui donne \(\sum_{i=1}^n \frac{a_i}{p^{i-1}} = 2\).

Le produit eulérien. En général, la somme de tous les \(\frac{1}{b_i}\) vaut

\[\sum_i \frac{1}{b_i} = \prod_{p \in S}\left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots\right) = \prod_{p \in S} \frac{p}{p-1}.\]

En particulier, pour \(n\) assez grand,

\[\left\lceil \sum_{j=1}^n \frac{1}{b_j} \right\rceil = \left\lceil \prod_{p \in S} \frac{p}{p-1} \right\rceil.\]

Dans la suite, on ne considère que des \(n\) assez grands pour que cette égalité soit vraie.

Cas \(S = \{2, 3\}\). Le produit vaut \(3\). On pose

\[a_i = \begin{cases} 1 & \text{si } 2b_i \leq b_n, \\ 2 & \text{si } 2b_i > b_n. \end{cases}\]

Alors, pour chaque \(t \geq 0\) (les \(b_i\) de valuation \(\nu_3(b_i) = t\) sont les \(3^t 2^s \leq b_n\), et le dernier compte double),

\[\sum_{\substack{i \leq n \\ \nu_3(b_i) = t}} \frac{a_i}{b_i} = \begin{cases} \dfrac{2}{3^t} & \text{si } b_n \geq 3^t, \\ 0 & \text{sinon.} \end{cases}\]

Par suite

\[\sum_{i \leq n} \frac{a_i}{b_i} = \sum_{\substack{t \geq 0 \\ 3^t \leq b_n}} \frac{2}{3^t} = 3 - \frac{1}{3^T},\]

où \(T\) est le plus grand \(t \geq 0\) tel que \(3^t \leq b_n\). En augmentant de \(1\) le coefficient \(a_j\) tel que \(b_j = 3^T\), on obtient une somme égale à \(3\), qui convient.

Cas général. On suppose désormais \(|S| > 1\) et \(S \neq \{2, 3\}\) ; alors \(\prod_{p \in S} \frac{p}{p-1}\) n'est pas entier :

  • si \(|S| > 2\), le dénominateur contient au moins deux facteurs pairs, donc \(2\) divise le dénominateur de la fraction ;
  • si \(|S| = 2\) et \(2 \notin S\), alors \(2\) divise le dénominateur mais pas le numérateur ;
  • si \(S = \{2, p\}\), le produit vaut \(\frac{2p}{p-1}\), qui n'est pas entier pour \(p > 3\).

Il existe donc un réel fixé \(\alpha > 0\) tel que

\[\left\lceil \prod_{p \in S} \frac{p}{p-1} \right\rceil = \prod_{p \in S} \frac{p}{p-1} + \alpha, \quad \text{d'où} \quad \left\lceil \sum_{i=1}^n \frac{1}{b_i} \right\rceil - \sum_{i=1}^n \frac{1}{b_i} > \alpha.\]

Il suffit alors de prouver l'affirmation suivante.

Affirmation. Soit \(n\) assez grand, et soit \(e_p\) le plus grand entier \(\geq 0\) tel que \(p^{e_p} \leq b_n\) ; posons \(M = \prod_{p \in S} p^{e_p}\). Si \(u\) est un entier positif tel que \(\frac{u}{M} > \alpha\), il existe des entiers \(a_i \geq 0\) tels que \(\sum_i \frac{a_i}{b_i} = \frac{u}{M}\).

L'énoncé s'en déduit en appliquant l'affirmation à \(\frac{u}{M} = \left\lceil \sum \frac{1}{b_i} \right\rceil - \sum \frac{1}{b_i}\) (tous les \(b_i\), \(i \leq n\), divisent \(M\)), puis en remplaçant chaque \(a_i\) par \(a_i + 1\).

Preuve de l'affirmation. On choisit une constante \(c\) telle que \(\sum_{p \in S} p^{-c} < \alpha\), et on suppose \(n\) assez grand pour que \(p^c < b_n\) pour tout \(p \in S\) ; en particulier \(p^c \mid M\).

Pour chaque \(p \in S\), soit \(i_p\) l'indice tel que \(b_{i_p} = p^{e_p}\), et soit \(a_{i_p}\) le plus petit entier \(\geq 0\) tel que

\[p^{e_p - c} \;\Big|\; a_{i_p} \cdot \frac{M}{p^{e_p}} - u.\]

Un tel entier existe et est inférieur à \(p^{e_p - c}\) : comme \(\frac{M}{p^{e_p}}\) est un entier premier avec \(p\), on peut prendre pour \(a_{i_p}\) le produit de \(u\) par l'inverse de \(\frac{M}{p^{e_p}}\) modulo \(p^{e_p - c}\). La contribution totale de ces \(a_{i_p}\) à la somme est au plus

\[\sum_{p \in S} \frac{p^{e_p - c}}{p^{e_p}} = \sum_{p \in S} p^{-c} < \alpha.\]

On a donc

\[\frac{u}{M} = \sum_{p \in S} \frac{a_{i_p}}{p^{e_p}} + \frac{r}{\prod_{p \in S} p^c},\]

où \(r\) est un entier grâce au choix des \(a_{i_p}\) (le numérateur \(u - \sum_p a_{i_p} \frac{M}{p^{e_p}}\) est divisible par chaque \(p^{e_p - c}\)), et \(r \geq 0\) grâce à la majoration de \(u\). Il suffit de prendre \(a_i = r\) pour l'indice \(i\) tel que \(b_i = \prod_{p \in S} p^c\) (et \(a_i = 0\) pour les autres indices). \(\blacksquare\)

Solution 2

On se ramène à l'affirmation comme dans la solution 1, et on construit les \(a_i\) autrement.

Soit \(p_0\) le plus petit premier de \(S\) et \(p_1\) le plus grand. Posons \(z_0 = \frac{u}{M}\). On construit une suite \(z_0, z_1, z_2, \ldots\) et des valeurs de \(a_i\) par le procédé suivant ; pour obtenir \(z_{k+1}\) :

  • on prend le plus grand premier \(p \in S\) divisant le dénominateur de \(z_k\), et on note \(\mu\) la valuation \(p\)-adique de ce dénominateur ;
  • on prend le plus grand \(\nu\) tel que \(p_0^\nu p^\mu \leq b_n\), et l'indice \(i \leq n\) tel que \(b_i = p_0^\nu p^\mu\) ;
  • on choisit \(0 \leq a_i < p\) tel que le dénominateur de \(z_k - \frac{a_i}{b_i}\) contienne au plus \(\mu - 1\) facteurs \(p\), et on pose \(z_{k+1} = z_k - \frac{a_i}{b_i}\) ;
  • on s'arrête quand \(p_0\) est le seul premier divisant le dénominateur de \(z_k\).

Le choix de la troisième étape est toujours possible : par construction, \(z_k b_i\) n'a pas de facteur \(p\) au dénominateur, c'est donc un entier \(p\)-adique, et il suffit de prendre \(a_i \equiv z_k b_i \pmod p\).

À chaque étape, par maximalité de \(\nu\), on a \(b_i > \frac{b_n}{p_0}\), donc

\[\frac{a_i}{b_i} < \frac{p\,p_0}{b_n} \leq \frac{p_0 p_1}{b_n}.\]

Le livret écrit \(b_i > M/p_0\) et majore par \(\frac{p_0p_1}{M}\) ; ce qui est vrai est \(b_i > b_n/p_0\), et comme \(\log_2 M \leq |S| \log_2 b_n\), la conclusion reste valable en remplaçant \(\frac{\log_2 M}{M}\) par \(\frac{|S| \log_2 b_n}{b_n}\). Le nombre d'étapes est au plus

\[\sum_{\substack{p \in S \\ p > p_0}} e_p \leq |S| \log_2 M,\]

donc la somme des \(\frac{a_i}{b_i}\) ainsi choisis est au plus \(\frac{|S| p_0 p_1 \log_2 M}{b_n} \leq \frac{|S|^2 p_0 p_1 \log_2 b_n}{b_n}\). On choisit \(n\) assez grand pour que cette quantité soit inférieure à \(\alpha\). Après avoir retranché ces \(\frac{a_i}{b_i}\) de \(\frac{u}{M}\), il reste une quantité de la forme \(\frac{r}{p_0^{e_{p_0}}}\), où \(r\) est entier par construction et positif grâce aux majorations. On prend \(a_i = r\) pour l'indice \(i\) tel que \(b_i = p_0^{e_{p_0}}\). \(\blacksquare\)

Solution 3

Comme dans la solution 1, on traite à part les cas \(|S| = 1\) et \(S = \{2, 3\}\) ; dans les autres cas, on définit \(\alpha\) comme dans la solution 1, ainsi que \(e_p\) (le plus grand entier \(\geq 0\) tel que \(p^{e_p} \leq b_n\)).

On va montrer que, pour \(n\) assez grand, on peut choisir un indice \(j \leq n\) et des entiers positifs \(a_i\) (\(i \neq j\)) tels que

\[\sum_{i \neq j} \frac{a_i}{b_i} - \sum_{i \neq j} \frac{1}{b_i} < \alpha,\]

et que tous les \(\frac{a_i}{b_i}\) soient des multiples entiers de \(\frac{1}{b_j}\). On prend alors pour \(a_j\) le plus petit entier positif rendant la somme totale entière. Cette somme est alors au moins \(\sum_{i \leq n} \frac{1}{b_i}\) et strictement inférieure à \(\sum_{i \leq n} \frac{1}{b_i} + \alpha + 1 < \left\lceil \sum_{i \leq n} \frac{1}{b_i} \right\rceil + 1\) ; c'est donc exactement la partie entière supérieure voulue.

Concrètement, on choisit \(j\) tel que \(b_j = \prod_{p \in S} p^{\lfloor e_p / |S| \rfloor}\), qui est inférieur à \(b_n\) par construction. Pour \(i \neq j\), on pose \(a_i = \frac{b_i}{\operatorname{pgcd}(b_i, b_j)}\), de sorte que \(\frac{a_i}{b_i} = \frac{1}{\operatorname{pgcd}(b_i, b_j)}\) est un multiple de \(\frac{1}{b_j}\). On a

\[\sum_{i \neq j} \frac{a_i}{b_i} - \sum_{i \neq j} \frac{1}{b_i} < \sum_{\substack{i \neq j \\ a_i > 1}} \frac{a_i}{b_i}.\]

Si \(a_i > 1\), il existe \(p \in S\) tel que \(p^{\lfloor e_p/|S| \rfloor + 1} \mid b_i\), et alors

\[\frac{a_i}{b_i} = \frac{1}{\operatorname{pgcd}(b_i, b_j)} \leq \frac{1}{p^{\lfloor e_p/|S| \rfloor}} < \frac{p}{b_n^{1/|S|}},\]

la dernière inégalité venant de \(p^{e_p + 1} > b_n\). Par ailleurs, \(n \leq \prod_{p \in S}(\log_p(b_n) + 1) \leq (2 \log b_n)^{|S|}\), donc

\[\sum_{\substack{i \neq j \\ a_i > 1}} \frac{a_i}{b_i} \leq \frac{p_1 (2 \log b_n)^{|S|}}{b_n^{1/|S|}},\]

où \(p_1\) est le plus grand premier de \(S\). Le livret omet le facteur constant \(p_1\), sans conséquence. On peut donc choisir \(n\) assez grand pour que cette quantité soit inférieure à \(\alpha\), ce qui conclut. \(\blacksquare\)