Shortlist 2023, N4¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Canada
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences
Solution officielle : Shortlist officielle 2023 (avec solutions), p. 86 (page 88 du PDF)
Énoncé¶
Soient \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\) des entiers strictement positifs (\(2n\) nombres en tout) tels que les \(n + 1\) produits
forment, dans cet ordre, une progression arithmétique strictement croissante. Déterminer le plus petit entier strictement positif qui puisse être la raison d'une telle progression arithmétique.
Énoncé original (anglais)
Let \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\) be \(2n\) positive integers such that the \(n + 1\) products
form a strictly increasing arithmetic progression in that order. Determine the smallest positive integer that could be the common difference of such an arithmetic progression.
Indices : les idées clés
- Écrire les différences successives : \(D = (b_1 - a_1)a_2 \cdots a_n = b_1(b_2 - a_2)a_3 \cdots a_n = \cdots\), d'où \((b_i - a_i)a_{i+1} = b_i(b_{i+1} - a_{i+1})\).
- PGCD (solutions 1 et 2) : on peut supposer \(\operatorname{pgcd}(a_i, b_i) = 1\), et des fractions irréductibles égales ont même numérateur et même dénominateur.
- Suites arithmétiques : on obtient que \(a_1, a_2, \ldots, a_n, b_n\) est arithmétique, donc \(a_i \geq i\).
- Une relation télescopique (solution 3) : \(\frac{a_i}{b_i - a_i}\) augmente exactement de \(1\) à chaque rang, sans aucun argument de PGCD.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (trois solutions).
Réponse : la plus petite raison possible est \(n!\).
Solution 1¶
Mise en équations. Soit \(D\) la raison de la progression. La condition s'écrit
Comme la progression est strictement croissante, \(D > 0\), donc \(b_i > a_i\) pour tout \(1 \leq i \leq n\). En comparant deux expressions consécutives et en simplifiant, on obtient
Réduction au cas premier entre eux. Si \(g_i = \operatorname{pgcd}(a_i, b_i) > 1\) pour un certain \(i\), on peut remplacer \(a_i\) par \(a_i / g_i\) et \(b_i\) par \(b_i / g_i\) : tous les produits sont divisés par \(g_i\), ils restent en progression arithmétique strictement croissante et la raison devient plus petite. Pour chercher la raison minimale, on peut donc supposer \(\operatorname{pgcd}(a_i, b_i) = 1\) pour tout \(i\).
Structure arithmétique. Alors \(\operatorname{pgcd}(b_i - a_i, b_i) = \operatorname{pgcd}(a_i, b_i) = 1\) et \(\operatorname{pgcd}(a_{i+1}, b_{i+1} - a_{i+1}) = \operatorname{pgcd}(a_{i+1}, b_{i+1}) = 1\). Dans (1), \(b_i\) divise \((b_i - a_i)a_{i+1}\) et est premier avec \(b_i - a_i\), donc \(b_i \mid a_{i+1}\) ; de même \(a_{i+1}\) divise \(b_i(b_{i+1} - a_{i+1})\) et est premier avec \(b_{i+1} - a_{i+1}\), donc \(a_{i+1} \mid b_i\). Par ce raisonnement de divisibilité, \(a_{i+1} = b_i\), puis (1) donne \(b_i - a_i = b_{i+1} - a_{i+1}\). Ainsi
est une progression arithmétique de raison strictement positive (entière). Comme \(a_1 \geq 1\), on a \(a_i \geq i\) pour tout \(1 \leq i \leq n\), donc
Construction. L'égalité est atteinte pour \(b_i - a_i = 1\) et \(a_1 = 1\), c'est-à-dire \(a_i = i\) et \(b_i = i + 1\) pour tout \(i\). Le \(k\)-ième produit vaut alors \((2 \cdot 3 \cdots k) \cdot (k \cdot (k+1) \cdots n) = k \cdot n!\) pour \(k = 1, 2, \ldots, n + 1\) : ces produits forment une progression arithmétique de raison \(n!\). \(\blacksquare\)
Solution 2¶
(Variante de la solution 1.) Comme dans la solution 1, on peut supposer \(\operatorname{pgcd}(a_i, b_i) = 1\) pour tout \(i\).
Notons \(p_1, p_2, \ldots, p_{n+1}\) les produits de l'énoncé. Alors \(\frac{p_{i+1}}{p_i} = \frac{b_i}{a_i} > 1\), donc \(b_i > a_i\). Comme \((p_i)\) est une progression arithmétique, \(p_{i+2} = 2p_{i+1} - p_i\), d'où
Les fractions \(\frac{2b_i - a_i}{b_i}\) et \(\frac{b_{i+1}}{a_{i+1}}\) sont toutes deux irréductibles (car \(\operatorname{pgcd}(2b_i - a_i, b_i) = \operatorname{pgcd}(a_i, b_i) = 1\)) : par unicité de l'écriture irréductible (PGCD), on obtient \(b_i = a_{i+1}\). Alors \(2 - \frac{a_i}{a_{i+1}} = \frac{a_{i+2}}{a_{i+1}}\), c'est-à-dire \(a_i + a_{i+2} = 2a_{i+1}\) : la suite \(a_1, a_2, \ldots, a_n\) est arithmétique de raison strictement positive. On conclut comme dans la solution 1. \(\blacksquare\)
Solution 3¶
(Solution purement algébrique, sans considération de PGCD.) On repart de (1). On peut l'écrire
Par récurrence (télescopage), pour \(1 \leq i \leq n\),
Comme \(b_i - a_i \geq 1\) et \(\frac{a_1}{b_1 - a_1} > 0\),
Comme \(a_i\) est entier, \(a_i \geq i\). On conclut comme dans la solution 1 : \(D = (b_1 - a_1)a_2 \cdots a_n \geq n!\), avec égalité pour \(a_i = i\), \(b_i = i + 1\). \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2021 N3 ★★☆☆☆ : Pour quels \(n\) peut-on ordonner les diviseurs de façon que toutes les sommes partielles soient des carrés ?
- 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 ?
- 2016 N3 ★★☆☆☆ · OIM P4 : Des valeurs consécutives de \(n^2 + n + 1\) dont aucune n'est première avec le produit des autres : combien en faut-il au minimum ?
- 2021 N7 ★★★★☆ : Si \(a_{n+2m}\) divise \(a_n + a_{n+m}\), la suite finit par être périodique.