Shortlist 2007, A1

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

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

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 7 (page 8 du PDF)

Problème 1 de l'OIM 2007

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

Figures reprises du livret officiel de la Shortlist.

Énoncé

Given a sequence \(a_1, a_2, \ldots, a_n\) of real numbers. For each \(i\) (\(1 \leq i \leq n\)) define

\[d_i = \max\{a_j : 1 \leq j \leq i\} - \min\{a_j : i \leq j \leq n\}\]

and let

\[d = \max\{d_i : 1 \leq i \leq n\}.\]

(a) Prove that for arbitrary real numbers \(x_1 \leq x_2 \leq \ldots \leq x_n\),

\[\max\{\lvert x_i - a_i \rvert : 1 \leq i \leq n\} \geq \frac{d}{2}. \tag{1}\]

(b) Show that there exists a sequence \(x_1 \leq x_2 \leq \ldots \leq x_n\) of real numbers such that we have equality in (1).

Indices : les idées clés

• Indices extrémaux : on choisit \(p \leq q \leq r\) avec \(d = d_q = a_p - a_r\) ; comme \(x_p \leq x_r\), on a \((a_p - x_p) + (x_r - a_r) \geq d\), donc l'un des deux écarts vaut au moins \(\frac{d}{2}\).
• Construction gloutonne : \(x_1 = a_1 - \frac{d}{2}\), \(x_k = \max\{x_{k-1}, a_k - \frac{d}{2}\}\) donne une suite croissante avec \(\lvert x_k - a_k \rvert \leq \frac{d}{2}\).
• Construction symétrique (solution 2) : \(x_i = \frac{M_i + m_i}{2}\), avec \(M_i\) et \(m_i\) les maximum et minimum de la définition de \(d_i\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2007 (deux solutions). C'est le problème 1 de l'OIM 2007.

Solution 1

(a) Soient \(1 \leq p \leq q \leq r \leq n\) des indices tels que

\[d = d_q, \qquad a_p = \max\{a_j : 1 \leq j \leq q\}, \qquad a_r = \min\{a_j : q \leq j \leq n\},\]

et donc \(d = a_p - a_r\). (Ces indices ne sont pas forcément uniques.)

Pour des réels quelconques \(x_1 \leq x_2 \leq \ldots \leq x_n\), considérons seulement les deux quantités \(\lvert x_p - a_p \rvert\) et \(\lvert x_r - a_r \rvert\). Comme

\[(a_p - x_p) + (x_r - a_r) = (a_p - a_r) + (x_r - x_p) \geq a_p - a_r = d,\]

on a \(a_p - x_p \geq \frac{d}{2}\) ou \(x_r - a_r \geq \frac{d}{2}\). Donc

\[\max\{\lvert x_i - a_i \rvert : 1 \leq i \leq n\} \geq \max\{\lvert x_p - a_p \rvert, \lvert x_r - a_r \rvert\} \geq \max\{a_p - x_p, x_r - a_r\} \geq \frac{d}{2}.\]

(b) Définissons la suite \((x_k)\) par

\[x_1 = a_1 - \frac{d}{2}, \qquad x_k = \max\left\{x_{k-1}, a_k - \frac{d}{2}\right\} \quad \text{pour } 2 \leq k \leq n.\]

Montrons qu'on a l'égalité dans (1) pour cette suite.

Par définition, la suite \((x_k)\) est croissante et \(x_k - a_k \geq -\frac{d}{2}\) pour tout \(1 \leq k \leq n\). Montrons ensuite que

\[x_k - a_k \leq \frac{d}{2} \qquad \text{pour tout } 1 \leq k \leq n. \tag{2}\]

Considérons un indice \(1 \leq k \leq n\) quelconque. Soit \(\ell \leq k\) le plus petit indice tel que \(x_k = x_\ell\). On a ou bien \(\ell = 1\), ou bien \(\ell \geq 2\) et \(x_\ell > x_{\ell-1}\). Dans les deux cas,

\[x_k = x_\ell = a_\ell - \frac{d}{2}. \tag{3}\]

Comme

\[a_\ell - a_k \leq \max\{a_j : 1 \leq j \leq k\} - \min\{a_j : k \leq j \leq n\} = d_k \leq d,\]

l'égalité (3) implique

\[x_k - a_k = a_\ell - a_k - \frac{d}{2} \leq d - \frac{d}{2} = \frac{d}{2}.\]

On a obtenu \(-\frac{d}{2} \leq x_k - a_k \leq \frac{d}{2}\) pour tout \(1 \leq k \leq n\), donc

\[\max\{\lvert x_i - a_i \rvert : 1 \leq i \leq n\} \leq \frac{d}{2}.\]

On a l'égalité, puisque \(\lvert x_1 - a_1 \rvert = \frac{d}{2}\). \(\blacksquare\)

Solution 2

Voici une autre construction d'une suite \((x_i)\) pour la partie (b). Pour tout \(1 \leq i \leq n\), posons

\[M_i = \max\{a_j : 1 \leq j \leq i\} \qquad \text{et} \qquad m_i = \min\{a_j : i \leq j \leq n\}.\]

Pour tout \(1 \leq i < n\), on a

\[M_i = \max\{a_1, \ldots, a_i\} \leq \max\{a_1, \ldots, a_i, a_{i+1}\} = M_{i+1}\]

et

\[m_i = \min\{a_i, a_{i+1}, \ldots, a_n\} \leq \min\{a_{i+1}, \ldots, a_n\} = m_{i+1}.\]

Les suites \((M_i)\) et \((m_i)\) sont donc croissantes. De plus, comme \(a_i\) figure dans les deux définitions,

\[m_i \leq a_i \leq M_i.\]

Pour obtenir l'égalité dans (1), posons

\[x_i = \frac{M_i + m_i}{2}.\]

Comme les suites \((M_i)\) et \((m_i)\) sont croissantes, cette suite l'est aussi. De \(d_i = M_i - m_i\), on tire

\[-\frac{d_i}{2} = \frac{m_i - M_i}{2} = x_i - M_i \leq x_i - a_i \leq x_i - m_i = \frac{M_i - m_i}{2} = \frac{d_i}{2}.\]

Donc

\[\max\{\lvert x_i - a_i \rvert : 1 \leq i \leq n\} \leq \max\left\{\frac{d_i}{2} : 1 \leq i \leq n\right\} = \frac{d}{2}.\]

Comme l'inégalité inverse a été prouvée dans la partie (a), on a l'égalité. \(\blacksquare\)