Shortlist 2023, A5¶
Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : Australia
Concepts : Double comptage
Solution officielle : Shortlist officielle 2023 (avec solutions), p. 21 (page 23 du PDF)
Énoncé¶
Let \(a_1, a_2, \ldots, a_{2023}\) be positive integers such that
- \(a_1, a_2, \ldots, a_{2023}\) is a permutation of \(1, 2, \ldots, 2023\), and
- \(|a_1 - a_2|, |a_2 - a_3|, \ldots, |a_{2022} - a_{2023}|\) is a permutation of \(1, 2, \ldots, 2022\).
Prove that \(\max(a_1, a_{2023}) \geq 507\).
Indices : les idées clés
- Généraliser : on démontre, pour une permutation \(a_1, \ldots, a_{2N-1}\) de \(1, \ldots, 2N-1\) dont les écarts consécutifs forment une permutation de \(1, \ldots, 2N-2\), que \(a_1 + a_{2N-1} \geq N + 1\) (le problème est le cas \(N = 1012\)).
- Le « score » \(s(a) = |a - N|\) : par l'inégalité triangulaire, \(|a - b| \leq s(a) + s(b)\).
- Sommer toutes les inégalités : la somme des écarts est connue, \((N-1)(2N-1)\), et la somme des scores aussi ; seules les extrémités ne sont comptées qu'une fois.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (une solution et deux remarques).
Solution¶
Généralisation. Soit \(N\) un entier strictement positif et \(a_1, a_2, \ldots, a_{2N-1}\) des entiers strictement positifs tels que
- \(a_1, a_2, \ldots, a_{2N-1}\) est une permutation de \(1, 2, \ldots, 2N-1\), et
- \(|a_1 - a_2|, |a_2 - a_3|, \ldots, |a_{2N-2} - a_{2N-1}|\) est une permutation de \(1, 2, \ldots, 2N-2\).
Alors \(a_1 + a_{2N-1} \geq N + 1\), et par conséquent \(\max(a_1, a_{2N-1}) \geq \left\lceil \frac{N+1}{2} \right\rceil\). Le problème est le cas \(N = 1012\) : on obtient \(\max(a_1, a_{2023}) \geq \left\lceil \frac{1013}{2} \right\rceil = 507\).
Le score. Pour \(a \in \{1, 2, \ldots, 2N-1\}\), on appelle score de \(a\) le nombre
Par l'inégalité triangulaire,
Sommation. Les écarts \(|a_i - a_{i+1}|\) sont exactement \(1, 2, \ldots, 2N-2\), de somme \(\frac{(2N-2)(2N-1)}{2} = (N-1)(2N-1)\). En appliquant l'inégalité précédente à chaque écart, chaque \(a_i\) intérieur (\(2 \leq i \leq 2N-2\)) apparaît deux fois et les extrémités \(a_1\), \(a_{2N-1}\) une seule fois :
Pour la dernière égalité, on a utilisé que les nombres \(s(a_1), s(a_2), \ldots, s(a_{2N-1})\) forment une permutation de \(0, 1, 1, 2, 2, \ldots, N-1, N-1\), dont la somme vaut \(2 \cdot \frac{(N-1)N}{2} = N(N-1)\).
Conclusion. On en déduit \(s(a_1) + s(a_{2N-1}) \leq 2N(N-1) - (N-1)(2N-1) = N - 1\). Ainsi
ce qui donne \(a_1 + a_{2N-1} \geq N + 1\). \(\blacksquare\)
Remarques¶
Remarque 1 (optimalité). Pour \(N = 1012\), il existe bien une suite avec \(\max(a_1, a_{2023}) = 507\) :
Pour \(N\) pair quelconque, on construit de même une suite avec \(\max(a_1, a_{2N-1}) = \left\lceil \frac{N+1}{2} \right\rceil\). Si \(N \geq 3\) est impair, l'inégalité n'est pas optimale : \(\max(a_1, a_{2N-1}) = \frac{N+1}{2}\) et \(a_1 + a_{2N-1} \geq N + 1\) imposeraient \(a_1 = a_{2N-1} = \frac{N+1}{2}\), ce qui est absurde.
Remarque 2 (formulation de l'auteur). La proposition originale était : soit \(a_1, a_2, a_3, \ldots\) une suite d'entiers strictement positifs telle que, pour tous entiers \(m, n \geq 1\), on ait \(a_{n+2023} = a_n + 2023\) ; si \(|a_{n+1} - a_n| = |a_{m+1} - a_m|\), alors \(2023 \mid (n - m)\) ; et la suite contient tous les entiers strictement positifs. Montrer que \(a_1 \geq 507\).
Les deux formulations sont équivalentes à des arguments simples près. Si \((a_n)\) vérifie la version de l'auteur, la première et la troisième condition montrent que \(a_1, \ldots, a_{2023}\) est une permutation de \(1, \ldots, 2023\) ; les écarts \(|a_i - a_{i+1}|\) (\(1 \leq i \leq 2022\)) sont des entiers \(\leq 2022\), deux à deux distincts par la deuxième condition, donc forment une permutation de \(1, \ldots, 2022\). De plus \(a_1 > a_{2023}\) : sinon \(|a_{2024} - a_{2023}| = |2023 + a_1 - a_{2023}| \leq 2022\) serait égal à un \(|a_i - a_{i+1}|\) avec \(1 \leq i \leq 2022\), contrairement à la deuxième condition. On se ramène ainsi à l'énoncé de la Shortlist. Réciproquement, une suite vérifiant l'énoncé de la Shortlist, renversée si besoin pour avoir \(a_1 > a_{2023}\), se prolonge en une suite infinie vérifiant la version de l'auteur.