Aller au contenu

Shortlist 2018, N7

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

Concepts : Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 68 (page 70 du PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(n \geq 2018\) be an integer, and let \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\) be pairwise distinct positive integers not exceeding \(5n\). Suppose that the sequence

\[\frac{a_1}{b_1},\ \frac{a_2}{b_2},\ \ldots,\ \frac{a_n}{b_n}\]

forms an arithmetic progression. Prove that the terms of the sequence are equal.

Indices : les idées clés
  • Écrire la raison sous forme irréductible \(\Delta = \frac{c}{d}\) et montrer que beaucoup trop de dénominateurs \(b_i\) devraient être divisibles par \(d\).
  • Valuations \(p\)-adiques : un indice \(i\) est « \(p\)-mauvais » si \(v_p(b_i) < v_p(d)\) ; les indices \(p\)-mauvais sont tous congrus modulo \(p\).
  • Fractions irréductibles et divisibilité : la différence de deux termes, \(\frac{(i-j)c}{d}\), a un dénominateur divisible par \(p^{\alpha}\) dès que \(p \nmid i - j\).
  • Comptage par blocs de 30 : \(d\) n'a que \(2, 3, 5\) comme facteurs premiers, donc dans tout bloc de \(30\) indices consécutifs, au moins \((2-1)(3-1)(5-1) = 8\) dénominateurs sont multiples de \(d\).
  • Majorer la raison : la plupart des termes sont dans \((0, 10]\), donc \(|\Delta|\) est petit et \(d\) est grand ; d'où des dénominateurs trop grands.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2018 (une solution et deux remarques).

Solution

Supposons que (1), la suite \(\frac{a_1}{b_1}, \ldots, \frac{a_n}{b_n}\), soit une progression arithmétique de raison non nulle. Écrivons la raison \(\Delta = \frac{c}{d}\), avec \(d > 0\) et \(c, d\) premiers entre eux.

On va montrer que trop de dénominateurs \(b_i\) devraient être divisibles par \(d\). Pour cela, pour tout \(1 \leq i \leq n\) et tout diviseur premier \(p\) de \(d\), on dit que l'indice \(i\) est \(p\)-mauvais si \(v_p(b_i) < v_p(d)\), où \(v_p(x)\) est l'exposant de \(p\) dans la décomposition de \(x\) (valuation \(p\)-adique).

Affirmation 1. Pour tout premier \(p\), les indices \(p\)-mauvais sont tous congrus entre eux modulo \(p\). Autrement dit, ils sont contenus dans une progression arithmétique de raison \(p\).

Preuve. Soit \(\alpha = v_p(d)\). Par l'absurde, supposons que \(i\) et \(j\) soient \(p\)-mauvais (aucun des deux \(b_i\), \(b_j\) n'est divisible par \(p^{\alpha}\)) avec \(i \not\equiv j \pmod p\). Alors le plus petit dénominateur commun de \(\frac{a_i}{b_i}\) et \(\frac{a_j}{b_j}\) n'est pas divisible par \(p^{\alpha}\). C'est impossible, car dans leur différence \((i - j)\Delta = \frac{(i - j)c}{d}\), le numérateur est premier avec \(p\) alors que \(p^{\alpha}\) divise le dénominateur \(d\). \(\square\)

Affirmation 2. \(d\) n'a aucun diviseur premier supérieur à \(5\).

Preuve. Supposons que \(p \geq 7\) soit un diviseur premier de \(d\). Parmi les indices \(1, 2, \ldots, n\), au plus \(\left\lceil \frac{n}{p} \right\rceil < \frac{n}{p} + 1\) sont \(p\)-mauvais, donc \(p\) divise au moins \(\frac{p-1}{p}n - 1\) des nombres \(b_1, \ldots, b_n\). Comme ces dénominateurs sont distincts,

\[5n \geq \max\{b_i : p \mid b_i\} \geq \left(\frac{p-1}{p}n - 1\right)p = (p - 1)(n - 1) - 1 \geq 6(n - 1) - 1 > 5n,\]

contradiction. \(\square\)

Affirmation 3. Pour tout \(0 \leq k \leq n - 30\), parmi les dénominateurs \(b_{k+1}, b_{k+2}, \ldots, b_{k+30}\), au moins \(\varphi(30) = 8\) sont divisibles par \(d\).

Preuve. D'après l'affirmation 1, les indices \(2\)-mauvais, \(3\)-mauvais et \(5\)-mauvais sont couverts par trois progressions arithmétiques de raisons \(2\), \(3\) et \(5\). Par un simple argument d'inclusion-exclusion, \((2 - 1)(3 - 1)(5 - 1) = 8\) indices du bloc ne sont pas couverts ; d'après l'affirmation 2, \(d \mid b_i\) pour chaque indice \(i\) non couvert. \(\square\)

Affirmation 4. \(|\Delta| < \frac{20}{n-2}\) et \(d > \frac{n-2}{20}\).

Preuve. Retirons de la suite (1) toutes les fractions avec \(b_i < \frac{n}{2}\). Il en reste au moins \(\frac{n}{2}\) (les \(b_i\) sont distincts), et elles ne dépassent pas \(\frac{5n}{n/2} = 10\). On a donc au moins \(\frac{n}{2}\) termes de la progression arithmétique (1) dans l'intervalle \((0, 10]\), d'où \(|\Delta| < \frac{10}{n/2 - 1} = \frac{20}{n - 2}\). La seconde inégalité découle de \(\frac{1}{d} \leq \frac{|c|}{d} = |\Delta|\). \(\square\)

Conclusion. D'après l'affirmation 3 (appliquée à \(\left\lfloor \frac{n}{30} \right\rfloor\) blocs disjoints), \(d \mid b_i\) pour au moins \(8\left\lfloor \frac{n}{30} \right\rfloor\) indices \(i\). D'après l'affirmation 4, \(d > \frac{n-2}{20}\). Comme ces \(b_i\) sont des multiples distincts de \(d\),

\[5n \geq \max\{b_i : d \mid b_i\} \geq \left(\left\lfloor \frac{n}{30} \right\rfloor \cdot 8\right) \cdot d > \left(\frac{n}{30} - 1\right) \cdot 8 \cdot \frac{n - 2}{20} > 5n,\]

la dernière inégalité étant vraie pour \(n \geq 2018\). C'est une contradiction : la raison est nulle et tous les termes sont égaux. \(\blacksquare\)

Remarques

Remarque 1. Il est possible que tous les termes de (1) soient égaux : par exemple, avec \(a_i = 2i - 1\) et \(b_i = 4i - 2\), on a \(\frac{a_i}{b_i} = \frac{1}{2}\).

Remarque 2. La borne \(5n\) de l'énoncé est loin d'être optimale : la solution ci-dessus peut être adaptée pour \(9n\), et pour \(n\) grand, la borne \(5n\) peut être remplacée par \(n^{3/2 - \varepsilon}\).