Shortlist 2022, A5¶
Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : Czech Republic
Concepts : Polynômes : racines, relations de Viète, factorisation · Principe extrémal
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 16 (page 18 du PDF)
Énoncé¶
Find all positive integers \(n \geq 2\) for which there exist \(n\) real numbers \(a_1 < \cdots < a_n\) and a real number \(r > 0\) such that the \(\frac{1}{2} n(n-1)\) differences \(a_j - a_i\) for \(1 \leq i < j \leq n\) are equal, in some order, to the numbers \(r^1, r^2, \ldots, r^{\frac{1}{2} n(n-1)}\).
Indices : les idées clés
- Constructions explicites pour \(n = 3\) et \(n = 4\) à l'aide des racines de \(x^2 - x - 1\) (nombre d'or) et de \(x^3 - x - 1\).
- Principe extrémal : la plus grande différence \(a_n - a_1 = r^b\) se décompose de \(n - 2\) façons en somme de deux différences, et le plus grand terme de chaque décomposition doit être parmi les \(n-2\) plus grandes puissances restantes.
- Convexité de \(t \mapsto r^t\) : elle force les petits exposants à augmenter avec des écarts strictement décroissants, et un comptage montre que tout est imposé.
- Comparer deux égalités \(r^{n-1} = r + 1\) et \(r^{n+1} = r^4 + 1\) pour conclure \(n = 4\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution).
Réponse : \(n \in \{2, 3, 4\}\).
Solution 1¶
Constructions pour \(n \in \{2, 3, 4\}\).
- Pour \(n = 2\) : par exemple \((a_1, a_2) = (1, 3)\) et \(r = 2\).
-
Pour \(n = 3\) : soit \(r > 1\) la racine de \(x^2 - x - 1 = 0\) (le nombre d'or), et \((a_1, a_2, a_3) = (0, r, r + r^2)\). Alors
\[(a_2 - a_1,\ a_3 - a_2,\ a_3 - a_1) = (r,\ r^2,\ r + r^2 = r^3).\] -
Pour \(n = 4\) : soit \(r \in (1, 2)\) une racine de \(x^3 - x - 1 = 0\) (elle existe car \(1^3 - 1 - 1 < 0\) et \(2^3 - 2 - 1 > 0\)), et \((a_1, a_2, a_3, a_4) = (0, r, r + r^2, r + r^2 + r^3)\). Alors
\[(a_2 - a_1,\ a_3 - a_2,\ a_4 - a_3,\ a_3 - a_1,\ a_4 - a_2,\ a_4 - a_1) = (r,\ r^2,\ r^3,\ r^4,\ r^5,\ r^6),\]car \(r^3 = r + 1\) donne \(a_3 - a_1 = r + r^2 = r(1 + r) = r^4\), \(a_4 - a_2 = r^2 + r^3 = r^5\) et \(a_4 - a_1 = r^4 + r^3 = r^3(r + 1) = r^6\).
Impossibilité pour \(n \geq 5\). On raisonne par l'absurde : supposons qu'il existe \(a_1 < \cdots < a_n\) et \(r > 1\) vérifiant les conditions. (On peut supposer \(r > 1\) : \(r = 1\) est impossible car les différences seraient toutes égales, et si \(r < 1\), on multiplie tous les \(a_i\) par \(r^{-(b+1)}\), où \(b = \frac{1}{2}n(n-1)\), ce qui remplace les différences par \((1/r)^1, \ldots, (1/r)^b\).)
Lemme. On a \(r^{n-1} > 2\).
Preuve. Il n'y a que \(n - 1\) différences \(a_j - a_i\) avec \(j = i + 1\) ; parmi les \(n\) valeurs \(r^1, \ldots, r^n\), il existe donc un exposant \(e \leq n\) et une différence \(a_j - a_i\) avec \(j \geq i + 2\) tels que \(a_j - a_i = r^e\). Alors
donc \(r^{n-1} > 2\). \(\square\)
Idée dans le cas \(n = 5\). Ici \(a_5 - a_1 = r^{10}\), et il y a trois façons d'écrire \(a_5 - a_1\) comme somme de deux différences :
À l'aide du lemme et de la convexité de \(t \mapsto r^t\), on montre que ces trois écritures sont forcément \(r^{10} = r^9 + r^1 = r^8 + r^4 = r^7 + r^6\) : les « grands » exposants diminuent de \(1\) à chaque fois, tandis que les « petits » augmentent de \(n - 2, n - 3, \ldots, 2\). En comparant deux telles égalités, on obtient une contradiction sauf si \(n \leq 4\).
Preuve générale pour \(n \geq 5\). Notons \(b = \frac{1}{2}n(n-1)\). La plus grande différence est \(a_n - a_1 = r^b\). Considérons les \(n - 2\) égalités
Dans chacune, l'un des deux termes du membre de droite vaut au moins \(\frac{1}{2}(a_n - a_1)\). Or, d'après le lemme, \(r^{b - (n-1)} = r^b / r^{n-1} < \frac{1}{2}(a_n - a_1)\). Il y a donc au plus \(n - 2\) éléments assez grands dans \(\{r^k \mid 1 \leq k < b\}\), à savoir \(r^{b-1}, \ldots, r^{b-(n-2)}\) (rappelons que \(r^b\) est déjà utilisé par \(a_n - a_1\)). Ces \(n-2\) « grands » termes (un par égalité, et tous distincts car les différences sont deux à deux distinctes) sont donc, dans un certain ordre, exactement les éléments de
Montrons ensuite que les « petits » termes des \(n - 2\) égalités sont exactement les éléments de
appariés dans l'ordre (le plus grand « grand » terme avec le plus petit « petit » terme, etc.). En effet, écrivons
avec \(1 \leq \alpha_1 < \cdots < \alpha_{n-2} \leq b - (n-1)\). Comme \(r > 1\) et que \(t \mapsto r^t\) est convexe,
ce qui implique (en soustrayant deux égalités consécutives)
La convexité de \(t \mapsto r^t\) implique encore
(si l'on avait \(\alpha_{k+1} - \alpha_k \leq \alpha_{k+2} - \alpha_{k+1}\), la croissance des accroissements de \(r^t\) donnerait \(r^{\alpha_{k+1}} - r^{\alpha_k} < r^{\alpha_{k+2}} - r^{\alpha_{k+1}}\), puisque \(\alpha_k < \alpha_{k+1}\)).
De plus \(\alpha_{n-2} - \alpha_{n-3} \geq 2\). Sinon on aurait \(\alpha_{n-2} - \alpha_{n-3} = 1\), et donc
d'où \(\alpha_{n-3} = b - (n-2)\), ce qui contredit \(\alpha_{n-3} < \alpha_{n-2} \leq b - (n-1)\). Par conséquent,
D'autre part, \(\alpha_{n-2} \leq b - (n-1)\) et \(\alpha_1 \geq 1\) donnent
Toutes les inégalités sont donc des égalités : \(\alpha_{n-2} = b - (n-1)\), \(\alpha_{n-3} = b - (n-1) - 2\), etc., ce qui prouve l'affirmation sur les petits termes.
Conclusion. Comme \(n - 2 \geq 2\), on dispose des deux égalités distinctes (pour \(i = n-2\) et \(i = n-3\))
qui se réécrivent (en divisant respectivement par \(r^{b-n+1}\) et par \(r^{b-n-1}\))
Un calcul simple donne alors
Comme \(r \neq 1\), on a \(r^3 = r + 1 = r^{n-1}\) d'après (1), donc \(n = 4\), ce qui contredit \(n \geq 5\). \(\blacksquare\)