Aller au contenu

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é

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

\[a_1 a_2 a_3 \cdots a_n,\quad b_1 a_2 a_3 \cdots a_n,\quad b_1 b_2 a_3 \cdots a_n,\quad \ldots,\quad b_1 b_2 b_3 \cdots b_n\]

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

\[D = (b_1 - a_1)a_2 a_3 \cdots a_n = b_1(b_2 - a_2)a_3 a_4 \cdots a_n = \cdots = b_1 b_2 \cdots b_{n-1}(b_n - a_n).\]

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

\[(b_i - a_i)a_{i+1} = b_i(b_{i+1} - a_{i+1}) \quad \text{pour tout } 1 \leq i \leq n - 1. \tag{1}\]

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

\[a_1,\quad b_1 = a_2,\quad b_2 = a_3,\quad \ldots,\quad b_{n-1} = a_n,\quad b_n\]

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

\[D = (b_1 - a_1)a_2 a_3 \cdots a_n \geq 1 \cdot 2 \cdot 3 \cdots n = n!.\]

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ù

\[2 - \frac{a_i}{b_i} = \frac{2b_i - a_i}{b_i} = \frac{2p_{i+1} - p_i}{p_{i+1}} = \frac{p_{i+2}}{p_{i+1}} = \frac{b_{i+1}}{a_{i+1}}.\]

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

\[\frac{a_{i+1}}{b_{i+1} - a_{i+1}} = \frac{b_i}{b_i - a_i} = 1 + \frac{a_i}{b_i - a_i}.\]

Par récurrence (télescopage), pour \(1 \leq i \leq n\),

\[\frac{a_i}{b_i - a_i} = \frac{a_1}{b_1 - a_1} + (i - 1).\]

Comme \(b_i - a_i \geq 1\) et \(\frac{a_1}{b_1 - a_1} > 0\),

\[a_i \geq \frac{a_i}{b_i - a_i} = \frac{a_1}{b_1 - a_1} + (i - 1) > i - 1.\]

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