Shortlist 2017, A4¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Russia
Concepts : Suites et récurrences · Principe extrémal
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 17 (page 19 du PDF)
Énoncé¶
A sequence of real numbers \(a_1, a_2, \ldots\) satisfies the relation
Prove that this sequence is bounded, i.e., there is a constant \(M\) such that \(|a_n| \leq M\) for all positive integers \(n\).
Indices : les idées clés
- Suivre le maximum et le minimum courants (solution 1) : avec \(M_n = \max_{k<n} a_k\) et \(m_n = -\min_{k<n} a_k\), on encadre \(-2M_n \leq a_n \leq m_n - M_n\), puis on étudie ces deux suites croissantes.
- Disjonction de cas « indice chanceux » (solution 1) : dès que \(m_n \leq 2M_n\), la suite \((M_n)\) se fige ; sinon c'est \((m_n)\) qui se fige.
- Raisonnement par l'absurde avec un indice record (solution 2) : si la suite n'est pas majorée, on prend un indice \(n\) où \(a_n\) bat tous les termes précédents.
- Principe extrémal (solution 2) : on choisit \(u < n\) qui maximise \(a_u\), puis on « déplie » \(a_v\) avec la relation de récurrence pour contredire ce maximum.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions et deux remarques).
Solution 1¶
Posons \(D = 2017\) et
Les suites \((m_n)\) et \((M_n)\) sont clairement croissantes (au sens large). Il faut montrer qu'elles sont bornées.
Soit \(n > D\) quelconque. Commençons par encadrer \(a_n\) à l'aide de \(m_n\) et \(M_n\).
(i) Il existe des indices \(p, q\) avec \(p + q = n\) et \(a_n = -(a_p + a_q)\). Comme \(a_p, a_q \leq M_n\), on a \(a_n \geq -2M_n\).
(ii) Choisissons un indice \(k < n\) tel que \(a_k = M_n\). Alors
En résumé, \(-2M_n \leq a_n \leq m_n - M_n\), d'où
Disons qu'un indice \(n > D\) est chanceux si \(m_n \leq 2M_n\). Deux cas sont possibles.
Cas 1 : il existe un indice chanceux \(n\). Alors (1) donne \(m_{n+1} \leq 2M_n\) et \(M_n \leq M_{n+1} \leq M_n\) (car \(m_n - M_n \leq M_n\)). Donc \(M_{n+1} = M_n\) et \(m_{n+1} \leq 2M_n = 2M_{n+1}\) : l'indice \(n + 1\) est aussi chanceux, et \(M_{n+1} = M_n\). En répétant l'argument, tous les indices \(k > n\) sont chanceux (\(m_k \leq 2M_k\)) et \(M_k = M_n\). Ainsi tous les \(m_k\) et \(M_k\) sont majorés par \(2M_n\) (et, comme \(-m_k \leq M_k\), minorés aussi).
Cas 2 : aucun indice n'est chanceux, c'est-à-dire \(2M_n < m_n\) pour tout \(n > D\). Alors (1) donne \(m_n \leq m_{n+1} \leq m_n\) pour tout \(n > D\), donc \(m_n = m_{D+1}\) pour tout \(n > D\). Comme \(M_n < m_n / 2\) pour ces indices, tous les \(m_n\) et \(M_n\) sont bornés par \(m_{D+1}\).
Dans les deux cas, \((m_n)\) et \((M_n)\) sont bornées, donc \((a_n)\) aussi. \(\blacksquare\)
Solution 2¶
Posons encore \(D = 2017\). Si la suite est majorée, disons par \(Q\), alors \(a_n \geq \min\{a_1, \ldots, a_D, -2Q\}\) pour tout \(n\) (car pour \(n > D\), \(a_n = -(a_p + a_q) \geq -2Q\)), donc elle est bornée. Supposons par l'absurde que la suite n'est pas majorée. Soient \(\ell = \min\{a_1, \ldots, a_D\}\) et \(L = \max\{a_1, \ldots, a_D\}\). Disons qu'un indice \(n\) est bon s'il vérifie
Il existe un bon indice. Par hypothèse, il existe \(N\) tel que \(a_N > \max\{L, -2\ell\}\). Choisissons \(n\) minimal tel que \(a_n = \max\{a_1, a_2, \ldots, a_N\}\). La première condition de (2) vient de la minimalité de \(n\) ; la deuxième et la troisième viennent de \(a_n \geq a_N > L, -2\ell\) et de \(L \geq a_i\) pour \(1 \leq i \leq D\).
Contradiction. Soit \(n\) un bon indice. Par définition de \(a_n\),
Par principe extrémal, choisissons \(u\) qui maximise \(a_u\) parmi \(1 \leq u \leq n - 1\), et posons \(v = n - u\). Alors \(a_u \geq a_v\) par maximalité.
Si \(v \leq D\), alors \(a_u \geq a_v \geq \ell\), et (3) donne \(a_n + 2\ell \leq 0\), ce qui contredit la deuxième condition de (2).
Si \(v > D\), il existe des indices \(w_1, w_2\) de somme \(v\) tels que \(a_v + a_{w_1} + a_{w_2} = 0\). Avec (3), on obtient
Comme \(a_n > a_u\) (première condition de (2)), on a \(\max\{a_{w_1}, a_{w_2}\} > a_u\). Mais chaque \(w_i\) est inférieur à \(v \leq n - 1\), ce qui contredit la maximalité de \(a_u\). \(\blacksquare\)
Remarques¶
Remarque 1 (deux versions plus difficiles).
Version 1. Si une suite vérifie \(a_n = -\max_{i+j+k=n}(a_i + a_j + a_k)\) pour tout \(n > 2017\), elle est bornée.
Preuve (dans l'esprit de la solution 1). Avec \(D\), \(M_n\), \(m_n\) comme dans la solution 1, soit \(n > 2D\) et \(k = \lfloor n/2 \rfloor\).
(i) Soient \(p \geq q \geq r\) avec \(p + q + r = n\) et \(a_n = -(a_p + a_q + a_r)\). Si \(p \geq k + 1\) (\(> D\)), alors \(p > q + r\), donc \(-a_p = \max_{i_1+i_2+i_3=p}(a_{i_1} + a_{i_2} + a_{i_3}) \geq a_q + a_r + a_{p-q-r}\), et \(a_n \geq a_{p-q-r} \geq -m_n\). Sinon \(k \geq p \geq q \geq r\), et comme \(n < 3k\), \(r < k\) ; alors \(a_p, a_q \leq M_{k+1}\) et \(a_r \leq M_k\), d'où \(a_n \geq -2M_{k+1} - M_k\). Dans tous les cas, \(a_n \geq -\max\{m_n, 2M_{k+1} + M_k\}\).
(ii) Choisissons \(p \leq k\) et \(q \leq k - 1\) avec \(a_p = M_{k+1}\) et \(a_q = M_k\). Comme \(p + q < n\), \(a_n \leq -(a_p + a_q + a_{n-p-q}) \leq m_n - M_{k+1} - M_k\).
Donc
Disons que \(n > 2D\) est chanceux si \(m_n \leq 2M_{\lfloor n/2 \rfloor + 1} + M_{\lfloor n/2 \rfloor}\). S'il existe un indice chanceux \(n\), (4) donne \(m_{n+1} \leq 2M_{k+1} + M_k\) et \(M_{n+1} = M_n\) (car \(m_n - M_{k+1} - M_k \leq M_{k+1} \leq M_n\)) ; donc \(n + 1\) est chanceux, puis tous les \(N > n\) le sont, avec \(M_N = M_n \geq m_N / 3\) : tout est borné par \(3M_n\). Sinon, (4) donne \(m_N = m_{2D+1}\) pour tout \(N > 2D\), et \(M_N < m_{2N+1}/3\) : tout est borné par \(m_{2D+1}\).
Version 2. Si une suite vérifie \(a_n = -\max_{i_1+\cdots+i_k=n}(a_{i_1} + \cdots + a_{i_k})\) pour tout \(n > 2017\) (\(k \geq 2\) fixé), elle est bornée.
Preuve (dans l'esprit de la solution 2). Si la suite est majorée par \(Q\), alors \(a_n \geq \min\{a_1, \ldots, a_D, -kQ\}\). Sinon, avec \(\ell\), \(L\) comme ci-dessus, un indice \(n\) est bon si \(a_n > a_i\) pour tout \(i < n\), \(a_n > -k\ell\) et \(n > D\) ; il en existe un comme dans la solution 2, et alors \(a_n + a_{v_1} + \cdots + a_{v_k} \leq 0\) dès que \(v_1 + \cdots + v_k = n\). On choisit \(v_1, \ldots, v_{k-1}\) de façon gloutonne : \(v_i\) maximise \(a_{v_i}\) parmi \(1 \leq v_i \leq n - (k - i) - (v_1 + \cdots + v_{i-1})\) (ce choix est toujours possible), puis \(v_k = n - (v_1 + \cdots + v_{k-1}) \geq 1\). On a \(a_{v_i} \geq a_{v_j}\) pour \(i < j\). Si \(v_k \leq D\), on obtient \(a_n + k\ell \leq 0\), contradiction. Si \(v_k > D\), il existe \(w_1 + \cdots + w_k = v_k\) avec \(a_{v_k} + a_{w_1} + \cdots + a_{w_k} = 0\), d'où \(a_n + a_{v_1} + \cdots + a_{v_{k-1}} \leq a_{w_1} + \cdots + a_{w_k}\) ; comme \(a_n > a_{v_1} \geq \cdots \geq a_{v_{k-1}}\), l'un des \(a_{w_i}\) dépasse \(a_{v_{k-1}}\), alors que \(w_i < v_k\) était un choix autorisé pour \(v_{k-1}\) : contradiction.
Remarque 2. Il semble que toute suite vérifiant la condition de la version 2 soit périodique à partir d'un certain rang, au moins lorsque ses termes sont entiers. Le comité de sélection ne connaît cependant pas de preuve de ce fait (même pour \(k = 2\)).