Shortlist 2010, A7¶

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

Concepts : Suites et récurrences · Principe des tiroirs · Principe extrémal

Solution officielle : Shortlist officielle 2010 (avec solutions), p. 16 (page 17 du PDF)

Problème 6 de l'OIM 2010

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

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé¶

Let \(a_1, \ldots, a_r\) be positive real numbers. For \(n > r\), we inductively define

\[a_n = \max_{1 \leq k \leq n-1}(a_k + a_{n-k}). \tag{1}\]

Prove that there exist positive integers \(\ell \leq r\) and \(N\) such that \(a_n = a_{n-\ell} + a_\ell\) for all \(n \geq N\).

Indices : les idées clés

Décomposition : pour \(n > r\), \(a_n = \max\{a_{i_1} + \cdots + a_{i_k}\}\) sur les suites d'indices \(1 \leq i_j \leq r\) de somme \(n\) avec \(i_1 + i_2 > r\).
Meilleur rapport : on fixe \(\ell \leq r\) maximisant \(\frac{a_i}{i}\) ; par les tiroirs, un indice \(j\) apparaît au moins \(\ell\) fois et peut être remplacé par \(j\) copies de \(\ell\).
Solution 2 : \(b_n = a_n - sn\) vérifie la même récurrence, est négatif et ne prend qu'un nombre fini de valeurs, donc devient périodique de période \(\ell\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (deux solutions).

Solution 1¶

D'abord, d'après les conditions du problème, chaque \(a_n\) (\(n > r\)) peut s'écrire \(a_n = a_{j_1} + a_{j_2}\) avec \(j_1, j_2 < n\), \(j_1 + j_2 = n\). Si, par exemple, \(j_1 > r\), on peut procéder de même avec \(a_{j_1}\), et ainsi de suite. Finalement, on écrit \(a_n\) sous la forme

\[a_n = a_{i_1} + \cdots + a_{i_k}, \tag{2}\]

\[1 \leq i_j \leq r, \qquad i_1 + \cdots + i_k = n. \tag{3}\]

De plus, si \(a_{i_1}\) et \(a_{i_2}\) sont les nombres de (2) obtenus à la dernière étape, alors \(i_1 + i_2 > r\). On peut donc préciser (3) en

\[1 \leq i_j \leq r, \qquad i_1 + \cdots + i_k = n, \qquad i_1 + i_2 > r. \tag{4}\]

D'autre part, supposons que les indices \(i_1, \ldots, i_k\) vérifient les conditions (4). Alors, en notant \(s_j = i_1 + \cdots + i_j\), (1) donne

\[a_n = a_{s_k} \geq a_{s_{k-1}} + a_{i_k} \geq a_{s_{k-2}} + a_{i_{k-1}} + a_{i_k} \geq \cdots \geq a_{i_1} + \cdots + a_{i_k}.\]

En résumant ces observations, on obtient le résultat suivant.

Affirmation. Pour tout \(n > r\), on a

\[a_n = \max\{a_{i_1} + \cdots + a_{i_k} : \text{la suite } (i_1, \ldots, i_k) \text{ vérifie } (4)\}. \qquad \square\]

Posons maintenant

\[s = \max_{1 \leq i \leq r} \frac{a_i}{i},\]

et fixons un indice \(\ell \leq r\) tel que \(s = \frac{a_\ell}{\ell}\).

Considérons un \(n \geq r^2\ell + 2r\) et choisissons un développement de \(a_n\) de la forme (2), (4). On a alors \(n = i_1 + \cdots + i_k \leq rk\), donc \(k \geq n/r \geq r\ell + 2\). Supposons qu'aucun des nombres \(i_3, \ldots, i_k\) ne soit égal à \(\ell\). Par le principe des tiroirs, il existe un indice \(1 \leq j \leq r\) qui apparaît au moins \(\ell\) fois parmi \(i_3, \ldots, i_k\), et sûrement \(j \neq \ell\). Supprimons ces \(\ell\) occurrences de \(j\) de \((i_1, \ldots, i_k)\), et ajoutons à la place \(j\) occurrences de \(\ell\) ; on obtient une suite \((i_1, i_2, i'_3, \ldots, i'_{k'})\) qui vérifie aussi (4). D'après l'affirmation,

\[a_{i_1} + \cdots + a_{i_k} = a_n \geq a_{i_1} + a_{i_2} + a_{i'_3} + \cdots + a_{i'_{k'}},\]

ou, après suppression des termes communs, \(\ell a_j \geq j a_\ell\), donc \(\frac{a_\ell}{\ell} \leq \frac{a_j}{j}\). Par définition de \(\ell\), cela signifie que \(\ell a_j = j a_\ell\), donc

\[a_n = a_{i_1} + a_{i_2} + a_{i'_3} + \cdots + a_{i'_{k'}}.\]

Ainsi, pour tout \(n \geq r^2\ell + 2r\), on a trouvé une représentation de la forme (2), (4) avec \(i_j = \ell\) pour un certain \(j \geq 3\). Quitte à réordonner les indices, on peut supposer \(i_k = \ell\).

Enfin, remarquons que, dans cette représentation, les indices \((i_1, \ldots, i_{k-1})\) vérifient les conditions (4) avec \(n\) remplacé par \(n - \ell\). L'affirmation donne donc

\[a_{n-\ell} + a_\ell \geq (a_{i_1} + \cdots + a_{i_{k-1}}) + a_\ell = a_n,\]

ce qui, d'après (1), implique

\[a_n = a_{n-\ell} + a_\ell \qquad \text{pour tout } n \geq r^2\ell + 2r,\]

comme voulu. \(\blacksquare\)

Solution 2¶

Comme dans la solution précédente, on utilise le développement (2), (3), et l'on fixe un indice \(1 \leq \ell \leq r\) tel que

\[\frac{a_\ell}{\ell} = s = \max_{1 \leq i \leq r}\frac{a_i}{i}.\]

Introduisons la suite \((b_n)\) définie par \(b_n = a_n - sn\) ; alors \(b_\ell = 0\).

Montrons par récurrence sur \(n\) que \(b_n \leq 0\) et que \((b_n)\) vérifie la même relation de récurrence que \((a_n)\). Les cas de base \(n \leq r\) découlent de la définition de \(s\). Pour \(n > r\), l'hypothèse de récurrence donne

\[b_n = \max_{1 \leq k \leq n-1}(a_k + a_{n-k}) - ns = \max_{1 \leq k \leq n-1}(b_k + b_{n-k} + ns) - ns = \max_{1 \leq k \leq n-1}(b_k + b_{n-k}) \leq 0,\]

comme voulu.

Si \(b_k = 0\) pour tout \(1 \leq k \leq r\), alors \(b_n = 0\) pour tout \(n\), donc \(a_n = sn\), et l'énoncé est trivial. Sinon, posons

\[M = \max_{1 \leq i \leq r}\lvert b_i \rvert, \qquad \varepsilon = \min\{\lvert b_i \rvert : 1 \leq i \leq r, \ b_i < 0\}.\]

Pour \(n > r\), on obtient

\[b_n = \max_{1 \leq k \leq n-1}(b_k + b_{n-k}) \geq b_\ell + b_{n-\ell} = b_{n-\ell},\]

donc

\[0 \geq b_n \geq b_{n-\ell} \geq b_{n-2\ell} \geq \cdots \geq -M.\]

Ainsi, d'après le développement (2), (3) appliqué à la suite \((b_n)\), chaque \(b_n\) appartient à l'ensemble

\[T = \{b_{i_1} + b_{i_2} + \cdots + b_{i_k} : i_1, \ldots, i_k \leq r\} \cap [-M, 0].\]

Montrons que cet ensemble est fini. En effet, pour tout \(x \in T\), écrivons \(x = b_{i_1} + \cdots + b_{i_k}\) (\(i_1, \ldots, i_k \leq r\)). Parmi les \(b_{i_j}\), il y a au plus \(\frac{M}{\varepsilon}\) termes non nuls (sinon \(x < \frac{M}{\varepsilon} \cdot (-\varepsilon) < -M\)). Donc \(x\) peut s'écrire de la même façon avec \(k \leq \frac{M}{\varepsilon}\), et il n'y a qu'un nombre fini de telles sommes.

Enfin, pour tout \(t = 1, 2, \ldots, \ell\), la suite

\[b_{r+t}, \ b_{r+t+\ell}, \ b_{r+t+2\ell}, \ \ldots\]

est croissante (au sens large) et ne prend qu'un nombre fini de valeurs ; elle est donc constante à partir d'un certain rang. La suite \((b_n)\) est donc périodique de période \(\ell\) à partir d'un certain indice \(N\), ce qui signifie que

\[b_n = b_{n-\ell} = b_{n-\ell} + b_\ell \qquad \text{pour tout } n > N + \ell,\]

et donc

\[a_n = b_n + ns = \big(b_{n-\ell} + (n - \ell)s\big) + (b_\ell + \ell s) = a_{n-\ell} + a_\ell \qquad \text{pour tout } n > N + \ell,\]

comme voulu. \(\blacksquare\)