Shortlist 2018, A4¶

Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : Belgium

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 14 (page 16 du PDF)

Énoncé¶

Let \(a_0, a_1, a_2, \ldots\) be a sequence of real numbers such that \(a_0 = 0\), \(a_1 = 1\), and for every \(n \geq 2\) there exists \(1 \leq k \leq n\) satisfying

\[a_n = \frac{a_{n-1} + \cdots + a_{n-k}}{k}.\]

Find the maximal possible value of \(a_{2018} - a_{2017}\).

Indices : les idées clés

Réponse : la valeur maximale est \(\dfrac{2016}{2017^2}\).
Encadrer par les moyennes extrêmes : avec \(S(n, k) = a_{n-1} + \cdots + a_{n-k}\), \(m_n = \min_k S(n,k)/k\) et \(M_n = \max_k S(n,k)/k\), les termes \(a_{n-1}\) et \(a_n\) sont tous deux dans \([m_n, M_n]\).
Suites et récurrences : on établit par récurrence une inégalité sur l'écart \(\Delta_n = M_n - m_n\) (solution 1) ou des formules exactes pour \(M_n\) et \(m_n\) (solution 2).
Produit télescopique (solution 1) : \(\Delta_n \leq \frac{n-1}{n}\Delta_{n-1}\) donne, en partant du premier indice \(q\) où \(a_q < 1\), la borne \(\frac{1}{N+1}\left(1 - \frac{1}{q^2}\right)\).
Intervalles emboîtés (solution 2) : \([m_{n+1}, M_{n+1}] \subseteq [m_n, M_n]\), donc tous les termes ultérieurs restent dans \([m_n, M_n]\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions et quatre remarques).

Réponse : la valeur maximale de \(a_{2018} - a_{2017}\) est \(\dfrac{2016}{2017^2}\).

Solution 1¶

La valeur est atteinte pour

\[a_1 = a_2 = \cdots = a_{2016} = 1, \qquad a_{2017} = \frac{a_{2016} + \cdots + a_0}{2017} = 1 - \frac{1}{2017}, \qquad a_{2018} = \frac{a_{2017} + \cdots + a_1}{2017} = 1 - \frac{1}{2017^2}.\]

Optimalité. Notons, pour des entiers \(0 \leq k \leq n\),

\[S(n, k) = a_{n-1} + a_{n-2} + \cdots + a_{n-k}.\]

En particulier \(S(n, 0) = 0\) et \(S(n, 1) = a_{n-1}\). Avec ces notations, pour tout \(n \geq 2\), il existe un entier \(1 \leq k \leq n\) tel que \(a_n = S(n, k)/k\). Pour tout \(n \geq 1\), posons

\[M_n = \max_{1 \leq k \leq n} \frac{S(n, k)}{k}, \qquad m_n = \min_{1 \leq k \leq n} \frac{S(n, k)}{k}, \qquad \Delta_n = M_n - m_n \geq 0.\]

Par définition, \(a_n \in [m_n, M_n]\) pour tout \(n \geq 2\) ; d'autre part \(a_{n-1} = S(n, 1)/1 \in [m_n, M_n]\). Donc

\[a_{2018} - a_{2017} \leq M_{2018} - m_{2018} = \Delta_{2018},\]

et il s'agit de majorer \(\Delta_{2018}\). Par définition aussi, pour \(0 < k \leq n\), \(k m_n \leq S(n, k) \leq k M_n\) ; ces inégalités restent vraies pour \(k = 0\).

Affirmation 1. Pour tout \(n > 2\), \(\Delta_n \leq \dfrac{n-1}{n} \Delta_{n-1}\).

Preuve. Choisissons des entiers \(1 \leq k, \ell \leq n\) tels que \(M_n = S(n, k)/k\) et \(m_n = S(n, \ell)/\ell\). On a \(S(n, k) = a_{n-1} + S(n-1, k-1)\), donc

\[k(M_n - a_{n-1}) = S(n, k) - k a_{n-1} = S(n-1, k-1) - (k-1)a_{n-1} \leq (k-1)(M_{n-1} - a_{n-1}),\]

puisque \(S(n-1, k-1) \leq (k-1) M_{n-1}\). De même,

\[\ell(a_{n-1} - m_n) = (\ell - 1)a_{n-1} - S(n-1, \ell-1) \leq (\ell - 1)(a_{n-1} - m_{n-1}).\]

Comme \(m_{n-1} \leq a_{n-1} \leq M_{n-1}\) et \(k, \ell \leq n\), on en déduit

\[M_n - a_{n-1} \leq \frac{k-1}{k}(M_{n-1} - a_{n-1}) \leq \frac{n-1}{n}(M_{n-1} - a_{n-1}),\]

\[a_{n-1} - m_n \leq \frac{\ell - 1}{\ell}(a_{n-1} - m_{n-1}) \leq \frac{n-1}{n}(a_{n-1} - m_{n-1}).\]

Donc

\[\Delta_n = (M_n - a_{n-1}) + (a_{n-1} - m_n) \leq \frac{n-1}{n}\Big((M_{n-1} - a_{n-1}) + (a_{n-1} - m_{n-1})\Big) = \frac{n-1}{n}\Delta_{n-1}. \qquad \square\]

Retour au problème. Si \(a_n = 1\) pour tout \(n \leq 2017\), alors \(a_{2018} \leq 1\), donc \(a_{2018} - a_{2017} \leq 0\). Sinon, soit \(2 \leq q \leq 2017\) le plus petit indice tel que \(a_q < 1\). On a \(S(q, i) = i\) pour \(i = 1, 2, \ldots, q-1\), et \(S(q, q) = q - 1\). Donc \(a_q < 1\) impose \(a_q = S(q, q)/q = 1 - \frac{1}{q}\).

On a alors \(S(q+1, i) = i - \frac{1}{q}\) pour \(i = 1, 2, \ldots, q\), et \(S(q+1, q+1) = q - \frac{1}{q}\). Cela donne

\[m_{q+1} = \frac{S(q+1, 1)}{1} = \frac{S(q+1, q+1)}{q+1} = \frac{q-1}{q} \qquad \text{et} \qquad M_{q+1} = \frac{S(q+1, q)}{q} = \frac{q^2 - 1}{q^2},\]

donc \(\Delta_{q+1} = M_{q+1} - m_{q+1} = (q-1)/q^2\). En notant \(N = 2017 \geq q\) et en appliquant l'affirmation 1 pour \(n = q+2, q+3, \ldots, N+1\) (récurrence), on obtient finalement

\[\Delta_{N+1} \leq \frac{q-1}{q^2} \cdot \frac{q+1}{q+2} \cdot \frac{q+2}{q+3} \cdots \frac{N}{N+1} = \frac{1}{N+1}\left(1 - \frac{1}{q^2}\right) \leq \frac{1}{N+1}\left(1 - \frac{1}{N^2}\right) = \frac{N-1}{N^2},\]

ce qui est la borne voulue. \(\blacksquare\)

Solution 2¶

On donne une autre preuve de la majoration \(a_{2018} - a_{2017} \leq \frac{2016}{2017^2}\), avec les notations \(S(n, k)\), \(m_n\), \(M_n\) de la solution 1.

Remarquons que \(S(n, n) = S(n, n-1)\), car \(a_0 = 0\), et que pour \(0 \leq k \leq \ell \leq n\), \(S(n, \ell) = S(n, k) + S(n-k, \ell-k)\).

Affirmation 2. Pour tout entier \(n \geq 1\), \(m_n \leq m_{n+1}\) et \(M_{n+1} \leq M_n\) ; autrement dit, \([m_{n+1}, M_{n+1}] \subseteq [m_n, M_n]\).

Preuve. Choisissons un entier \(1 \leq k \leq n+1\) tel que \(m_{n+1} = S(n+1, k)/k\). Alors

\[k\, m_{n+1} = S(n+1, k) = a_n + S(n, k-1) \geq m_n + (k-1)m_n = k\, m_n,\]

ce qui donne la première inégalité. La seconde se prouve de même. \(\square\)

Affirmation 3. Pour tous entiers \(k \geq n\), \(m_n \leq a_k \leq M_n\).

Preuve. D'après l'affirmation 2, \([m_k, M_k] \subseteq [m_{k-1}, M_{k-1}] \subseteq \cdots \subseteq [m_n, M_n]\). Comme \(a_k \in [m_k, M_k]\), le résultat suit. \(\square\)

Affirmation 4. Pour tout entier \(n \geq 2\), \(M_n = \dfrac{S(n, n-1)}{n-1}\) et \(m_n = \dfrac{S(n, n)}{n}\).

Preuve. Par récurrence sur \(n\). Le cas \(n = 2\) est immédiat. Pour l'hérédité, il faut prouver

\[\frac{S(n, n)}{n} \leq \frac{S(n, k)}{k} \qquad \text{et} \qquad \frac{S(n, k)}{k} \leq \frac{S(n, n-1)}{n-1} \tag{1}\]

pour tout entier \(1 \leq k \leq n\). Ces inégalités sont claires pour \(k = n\) et \(k = n-1\), car \(S(n, n) = S(n, n-1) > 0\). Supposons désormais \(k < n - 1\).

La première inégalité de (1) s'écrit \(n S(n, k) \geq k S(n, n) = k\big(S(n, k) + S(n-k, n-k)\big)\), c'est-à-dire, après simplification,

\[(n-k) S(n, k) \geq k S(n-k, n-k) \iff S(n, k) \geq k \cdot \frac{S(n-k, n-k)}{n-k}.\]

Par hypothèse de récurrence, \(S(n-k, n-k)/(n-k) = m_{n-k}\). Par l'affirmation 3, \(a_{n-i} \geq m_{n-k}\) pour tout \(i = 1, 2, \ldots, k\). En sommant ces \(k\) inégalités,

\[S(n, k) \geq k\, m_{n-k} = k \cdot \frac{S(n-k, n-k)}{n-k},\]

comme voulu.

La seconde inégalité de (1) se prouve de même. Elle équivaut à

\[(n-1) S(n, k) \leq k S(n, n-1) \iff (n-k-1) S(n, k) \leq k S(n-k, n-k-1) \iff S(n, k) \leq k \cdot \frac{S(n-k, n-k-1)}{n-k-1} = k M_{n-k},\]

et la dernière inégalité découle encore de l'affirmation 3, puisque chaque terme de \(S(n, k)\) est au plus \(M_{n-k}\). \(\square\)

Conclusion. Posons \(N = 2017\). Par l'affirmation 4,

\[a_{N+1} - a_N \leq M_{N+1} - a_N = \frac{S(N+1, N)}{N} - a_N = \frac{a_N + S(N, N-1)}{N} - a_N = \frac{S(N, N-1)}{N} - \frac{N-1}{N} \cdot a_N.\]

D'autre part, la même affirmation donne

\[a_N \geq m_N = \frac{S(N, N)}{N} = \frac{S(N, N-1)}{N}.\]

Comme chaque terme de \(S(N, N-1)\) est au plus \(1\), on a \(S(N, N-1) \leq N - 1\), et finalement

\[a_{N+1} - a_N \leq \frac{S(N, N-1)}{N} - \frac{N-1}{N} \cdot \frac{S(N, N-1)}{N} = \frac{S(N, N-1)}{N^2} \leq \frac{N-1}{N^2}. \qquad \blacksquare\]

Précision ajoutée : chaque \(a_i\) est au plus \(1\), car \(a_0 = 0\), \(a_1 = 1\) et, pour \(i \geq 2\), \(a_i \leq M_2 = 1\) par l'affirmation 3.

Remarques¶

Remarque 1 (solution 1 : unicité). On peut vérifier que la valeur maximale de \(a_{2018} - a_{2017}\) n'est atteinte que pour la suite donnée au début de la solution 1.

Remarque 2 (solution 1 : une version plus facile). Une question plus facile serait de déterminer la valeur maximale de \(|a_{2018} - a_{2017}|\). La réponse \(\frac{1}{2018}\) est atteinte pour

\[a_1 = a_2 = \cdots = a_{2017} = 1, \qquad a_{2018} = \frac{a_{2017} + \cdots + a_0}{2018} = 1 - \frac{1}{2018}.\]

Pour l'optimalité, il suffit de remarquer que \(\Delta_2 = \frac12\) et d'appliquer l'affirmation 1 :

\[|a_{2018} - a_{2017}| \leq \Delta_{2018} \leq \frac{1}{2} \cdot \frac{2}{3} \cdots \frac{2017}{2018} = \frac{1}{2018}.\]

Remarque 3 (solution 2 : retrouver l'affirmation 1). L'affirmation 1 se déduit des affirmations 2 et 4. Par l'affirmation 4, \(M_n = \frac{S(n, n-1)}{n-1}\) et \(m_n = \frac{S(n, n)}{n} = \frac{S(n, n-1)}{n}\), donc \(\Delta_n = \frac{S(n, n-1)}{(n-1)n}\), puis \(M_n = n\Delta_n\) et \(m_n = (n-1)\Delta_n\). De même \(M_{n-1} = (n-1)\Delta_{n-1}\) et \(m_{n-1} = (n-2)\Delta_{n-1}\). Les inégalités \(m_{n-1} \leq m_n\) et \(M_n \leq M_{n-1}\) de l'affirmation 2 s'écrivent alors \((n-2)\Delta_{n-1} \leq (n-1)\Delta_n\) et \(n\Delta_n \leq (n-1)\Delta_{n-1}\), d'où

\[\frac{n-2}{n-1}\Delta_{n-1} \leq \Delta_n \leq \frac{n-1}{n}\Delta_{n-1}.\]

Remarque 4 (solution 2 : se restreindre à une suite optimale). Les deux solutions étudient une suite quelconque vérifiant les conditions. On peut se contenter d'étudier une suite optimale, qui maximise \(a_{2018} - a_{2017}\) ; cela simplifie par exemple les preuves de l'affirmation 1 et de l'affirmation 4. La suite \((a_n)\) est entièrement déterminée par le choix, pour chaque \(n \geq 2\), d'un entier \(1 \leq k(n) \leq n\) tel que \(a_n = S(n, k(n))/k(n)\). Fixons \(2 \leq n_0 \leq 2018\) et tous les \(k(n)\) pour \(n \neq n_0\). Alors chaque \(a_n\) est une fonction affine de \(a_{n_0}\) (dont les valeurs possibles forment une partie discrète de \([m_{n_0}, M_{n_0}]\) contenant les deux extrémités). Donc \(a_{2018} - a_{2017}\) est aussi une fonction affine de \(a_{n_0}\), et atteint son maximum en une extrémité de \([m_{n_0}, M_{n_0}]\). Pour une suite optimale, on peut donc supposer \(a_n \in \{m_n, M_n\}\) pour tout \(2 \leq n \leq 2018\). On voit alors facilement que, si \(a_n = m_n\), alors \(m_{n+1} = m_n\) et \(M_{n+1} \leq \frac{m_n + nM_n}{n+1}\) ; on a des estimations analogues si \(a_n = M_n\). Cela établit déjà l'affirmation 1 et simplifie la preuve par récurrence de l'affirmation 4, pour une suite optimale.