Shortlist 2020, N3¶

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

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

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 74 (page 76 du PDF)

Problème 5 de l'OIM 2020

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2020, où il était le problème 5 (jour 2).

Énoncé¶

Let \(n\) be an integer with \(n \geq 2\). Does there exist a sequence \((a_1, \ldots, a_n)\) of positive integers with not all terms being equal such that the arithmetic mean of every two terms is equal to the geometric mean of some (one or more) terms in this sequence?

Indices : les idées clés

Divisibilité, PGCD : on se ramène à \(\operatorname{pgcd}(a_1, \ldots, a_n) = 1\) en divisant tous les termes par leur PGCD.
Principe extrémal : on choisit le plus grand terme et le plus grand terme non divisible par un premier \(p\) (solution 1), ou une paire de PGCD minimal et de somme maximale (solution 2).
Valuations p-adiques (solution 2) : comparer les exposants de \(p\) pour montrer que \(D\) divise \(d^t\).
Une racine rationnelle d'un entier est entière : la moyenne arithmétique de deux termes, demi-entier, doit être entière si c'est une moyenne géométrique.

Solutions

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

Réponse. Une telle suite n'existe pas.

Solution 1¶

Supposons que \(a_1, \ldots, a_n\) vérifient les conditions. Soit \(d = \operatorname{pgcd}(a_1, \ldots, a_n)\). Si \(d > 1\), on remplace \(a_1, \ldots, a_n\) par \(\frac{a_1}{d}, \ldots, \frac{a_n}{d}\) : toutes les moyennes arithmétiques et géométriques sont divisées par \(d\), et la nouvelle suite vérifie encore la condition. On peut donc supposer (PGCD) que \(\operatorname{pgcd}(a_1, \ldots, a_n) = 1\).

Nous allons exhiber deux termes \(a_m\) et \(a_k\) dont la moyenne arithmétique \(\frac{a_m + a_k}{2}\) n'est la moyenne géométrique d'aucune sous-suite (non vide) de \(a_1, \ldots, a_n\), ce qui prouvera qu'une telle suite ne peut exister.

Choix des deux termes (principe extrémal). Choisissons \(m\) tel que \(a_m = \max(a_1, \ldots, a_n)\). On a \(a_m \geq 2\) car les termes ne sont pas tous égaux. Soit \(p\) un diviseur premier de \(a_m\). Soit ensuite \(k\) un indice tel que

\[a_k = \max\{a_i : p \nmid a_i\}.\]

Un tel \(k\) existe : comme le PGCD vaut \(1\), les \(a_i\) ne sont pas tous divisibles par \(p\). On a \(a_m > a_k\), car \(a_m \geq a_k\), \(p \mid a_m\) et \(p \nmid a_k\).

Posons \(b = \frac{a_m + a_k}{2}\) ; montrons que \(b\) n'est la moyenne géométrique d'aucune sous-suite. Soit \(g = \sqrt[t]{a_{i_1} \cdots a_{i_t}}\) la moyenne géométrique d'une sous-suite quelconque.

Si aucun des \(a_{i_1}, \ldots, a_{i_t}\) n'est divisible par \(p\), ils sont tous au plus égaux à \(a_k\), donc

\[g = \sqrt[t]{a_{i_1} \cdots a_{i_t}} \leq a_k < \frac{a_m + a_k}{2} = b,\]

et \(g \neq b\).
Sinon, l'un au moins des \(a_{i_j}\) est divisible par \(p\). Alors \(2g = 2\sqrt[t]{a_{i_1} \cdots a_{i_t}}\) ou bien n'est pas un entier, ou bien est un entier divisible par \(p\) (car \(p\) divise le produit, donc divise \((2g)^t = 2^t a_{i_1} \cdots a_{i_t}\), et \(p\) premier). Or \(2b = a_m + a_k\) est un entier non divisible par \(p\). Donc \(g \neq b\) encore.

Ainsi \(b\) n'est la moyenne géométrique d'aucune sous-suite : contradiction. \(\blacksquare\)

Solution 2¶

Comme dans la solution 1, on suppose que les \(a_i\) n'ont pas de diviseur commun supérieur à \(1\).

Tous les termes sont impairs. La moyenne arithmétique de deux termes est la moitié d'un entier ; d'autre part, c'est une racine (d'ordre entier) d'un entier. Une racine rationnelle d'un entier étant entière, la moyenne de chaque paire est un entier, donc tous les termes ont la même parité ; comme leur PGCD vaut \(1\), ils sont tous impairs.

Choix extrémal. Soit

\[d = \min\{\operatorname{pgcd}(a_i, a_j) : a_i \neq a_j\}.\]

Quitte à réordonner, on peut supposer que \(\operatorname{pgcd}(a_1, a_2) = d\), que la somme \(a_1 + a_2\) est maximale parmi les paires de PGCD égal à \(d\), et que \(a_1 > a_2\). Montrons que \(\frac{a_1 + a_2}{2}\) n'est la moyenne géométrique d'aucune sous-suite.

Écrivons \(a_1 = xd\) et \(a_2 = yd\) avec \(x, y\) premiers entre eux, et supposons qu'il existe \(b_1, \ldots, b_t \in \{a_1, \ldots, a_n\}\) de moyenne géométrique \(\frac{a_1 + a_2}{2}\). Posons \(d_i = \operatorname{pgcd}(a_1, b_i)\) pour \(i = 1, \ldots, t\) et \(D = d_1 d_2 \cdots d_t\). Alors

\[D = d_1 d_2 \cdots d_t \;\Big|\; b_1 b_2 \cdots b_t = \left(\frac{a_1 + a_2}{2}\right)^t = \left(\frac{x + y}{2}\right)^t d^t.\]

Affirmation : \(D \mid d^t\). Soit \(p\) un diviseur premier de \(D\), et notons \(\nu_p\) l'exposant de \(p\) (valuation p-adique).

Si \(p \mid \frac{x + y}{2}\), alors \(p \nmid x\) et \(p \nmid y\) (car \(x\) et \(y\) sont premiers entre eux), donc \(p\) est premier avec \(x\). Ainsi \(\nu_p(d_i) \leq \nu_p(a_1) = \nu_p(xd) = \nu_p(d)\) pour tout \(i\), d'où \(\nu_p(D) = \sum_i \nu_p(d_i) \leq t\,\nu_p(d) = \nu_p(d^t)\).
Sinon, \(p\) est premier avec \(\frac{x + y}{2}\), et la divisibilité ci-dessus donne directement \(\nu_p(D) \leq \nu_p(d^t)\).

L'affirmation est démontrée.

Conclusion. On a \(d_i = \operatorname{pgcd}(b_i, a_1) \geq d\) pour tout \(i\) : si \(b_i \neq a_1\), cela découle de la définition de \(d\) ; sinon \(b_i = a_1\) et \(d_i = a_1 \geq d\). Donc \(D = d_1 \cdots d_t \geq d^t\), et l'affirmation impose \(d_1 = \cdots = d_t = d\).

Enfin, comme \(\frac{a_1 + a_2}{2} > a_2\), l'un des \(b_k\) est strictement supérieur à \(a_2\) (sinon leur moyenne géométrique serait au plus \(a_2\)). Comme \(a_1 > a_2 \geq d = \operatorname{pgcd}(a_1, b_k)\), on a \(b_k \neq a_1\). On obtient ainsi une paire \(a_1, b_k\) avec \(\operatorname{pgcd}(a_1, b_k) = d\) mais \(a_1 + b_k > a_1 + a_2\), ce qui contredit le choix de \(a_1\) et \(a_2\). \(\blacksquare\)

Remarques¶

Remarque 1 (la question « inverse »). La proposition originale posait aussi la question : existe-t-il une suite non constante d'entiers strictement positifs telle que la moyenne géométrique de deux termes quelconques soit égale à la moyenne arithmétique de certains termes ? Pour \(n \geq 3\), la suite \((4, 1, 1, \ldots, 1)\) convient. Le cas \(n = 2\) se règle par les encadrements triviaux

\[\min(a_1, a_2) < \sqrt{a_1 a_2} < \frac{a_1 + a_2}{2} < \max(a_1, a_2).\]

Le comité de sélection a jugé cette variante moins intéressante et n'a retenu que la première question.