Aller au contenu

Shortlist 2016, A3

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

Concepts : Récurrence et constructions récursives · Principe des tiroirs

Solution officielle : Shortlist officielle 2016 (avec solutions), p. 14 (page 17 du PDF)

Énoncé

Find all integers \(n \geq 3\) with the following property: for all real numbers \(a_1, a_2, \ldots, a_n\) and \(b_1, b_2, \ldots, b_n\) satisfying \(|a_k| + |b_k| = 1\) for \(1 \leq k \leq n\), there exist \(x_1, x_2, \ldots, x_n\), each of which is either \(-1\) or \(1\), such that

\[\left| \sum_{k=1}^{n} x_k a_k \right| + \left| \sum_{k=1}^{n} x_k b_k \right| \leq 1.\]
Indices : les idées clés
  • Contre-exemple par parité pour \(n\) pair : avec des \(a_k, b_k \in \{0, 1\}\) bien choisis, les deux sommes sont des entiers impairs, donc chacune vaut au moins \(1\) en valeur absolue.
  • Signes alternés après tri (solution 1) : on trie les \(a_k\) et on prend \(x_k = (-1)^{k+1}\) ; les sommes alternées d'une suite monotone sont encadrées.
  • Récurrence et constructions récursives (solution 2) : récurrence de \(n-2\) à \(n\) sur les entiers impairs, en choisissant \(x_1, x_2\) en dernier.
  • Principe des tiroirs (solution 2) : trois indices de même type, puis deux \(a_k\) distants d'au plus \(\frac{1}{2}\).
Solutions

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

Réponse. Les entiers cherchés sont exactement les entiers impairs \(n \geq 3\).

Solution 1

On note (1) l'inégalité \(\left| \sum x_k a_k \right| + \left| \sum x_k b_k \right| \leq 1\) à obtenir.

Cas \(n\) pair (\(n \geq 4\)) : la propriété est fausse. Prenons

\[a_1 = a_2 = \cdots = a_{n-1} = b_n = 0 \quad \text{et} \quad b_1 = b_2 = \cdots = b_{n-1} = a_n = 1.\]

On a bien \(|a_k| + |b_k| = 1\) pour tout \(k\). Quel que soit le choix des \(x_k \in \{-1, 1\}\), la somme \(\sum_{k=1}^n x_k a_k = x_n\) est un entier impair, et \(\sum_{k=1}^n x_k b_k = x_1 + \cdots + x_{n-1}\) est une somme d'un nombre impair de termes \(\pm 1\), donc aussi un entier impair. Ainsi les deux valeurs absolues valent au moins \(1\), et (1) ne peut pas être vérifiée.

Cas \(n\) impair (\(n \geq 3\)) : la propriété est vraie. Quitte à remplacer le couple \((a_k, b_k)\) par \((-a_k, -b_k)\) et \(x_k\) par \(-x_k\), on peut supposer \(b_k \geq 0\) pour tout \(k\). Quitte à renuméroter, on peut aussi supposer

\[a_1 \geq a_2 \geq \cdots \geq a_m \geq 0 > a_{m+1} \geq \cdots \geq a_n.\]

Montrons que le choix \(x_k = (-1)^{k+1}\) pour \(1 \leq k \leq n\) convient. Posons

\[s = \sum_{k=1}^{m} x_k a_k \quad \text{et} \quad t = -\sum_{k=m+1}^{n} x_k a_k.\]

On a

\[s = (a_1 - a_2) + (a_3 - a_4) + \cdots \geq 0\]

puisque \(a_1 \geq a_2 \geq \cdots \geq a_m\) (si \(m\) est impair, il reste un terme isolé \(a_m\) à la fin, lui aussi positif). D'autre part,

\[s = a_1 - (a_2 - a_3) - (a_4 - a_5) - \cdots \leq a_1 \leq 1.\]

De même (comme \(n\) est impair, \(x_n = 1\), et les signes alternent en remontant à partir de \(a_n\)),

\[t = (-a_n + a_{n-1}) + (-a_{n-2} + a_{n-3}) + \cdots \geq 0\]

et

\[t = -a_n + (a_{n-1} - a_{n-2}) + (a_{n-3} - a_{n-4}) + \cdots \leq -a_n \leq 1.\]

Par hypothèse, \(a_k + b_k = 1\) pour \(1 \leq k \leq m\) et \(-a_k + b_k = 1\) pour \(m+1 \leq k \leq n\). On en déduit

\[\sum_{k=1}^n x_k a_k = s - t \quad \text{et} \quad \sum_{k=1}^n x_k b_k = \sum_{k=1}^m x_k (1 - a_k) + \sum_{k=m+1}^n x_k (1 + a_k) = 1 - s - t,\]

car \(\sum_{k=1}^n x_k = 1\) (\(n\) impair). Il reste donc à prouver

\[|s - t| + |1 - s - t| \leq 1 \quad \text{pour } 0 \leq s, t \leq 1.\]

Par symétrie, on peut supposer \(s \geq t\). Si \(1 - s - t \geq 0\), alors

\[|s - t| + |1 - s - t| = s - t + 1 - s - t = 1 - 2t \leq 1.\]

Si \(1 - s - t \leq 0\), alors

\[|s - t| + |1 - s - t| = s - t - 1 + s + t = 2s - 1 \leq 1.\]

L'inégalité est vraie dans les deux cas.

Les entiers cherchés sont donc exactement les entiers impairs \(n \geq 3\). \(\blacksquare\)

Solution 2

Le cas pair se traite comme dans la solution 1. Pour le cas impair, on raisonne par récurrence sur \(n\) (de \(n - 2\) à \(n\)).

Initialisation : \(n = 3\). Quitte à changer \((a_k, b_k)\) en \((-a_k, -b_k)\) et à renuméroter, on peut supposer \(a_1 \geq a_2 \geq a_3 \geq 0\) ; chaque \(b_k\) vaut alors \(a_k - 1\) ou \(1 - a_k\). Quitte à remplacer tous les \(b_k\) par \(-b_k\), on peut supposer \(b_1 = a_1 - 1\).

  • Cas 1 : \(b_2 = a_2 - 1\) et \(b_3 = a_3 - 1\). On prend \((x_1, x_2, x_3) = (1, -1, 1)\). Soit \(c = a_1 - a_2 + a_3\), de sorte que \(0 \leq c \leq 1\). Alors \(|b_1 - b_2 + b_3| = |a_1 - a_2 + a_3 - 1| = 1 - c\), donc \(|c| + |b_1 - b_2 + b_3| = 1\).

  • Cas 2 : \(b_2 = 1 - a_2\) et \(b_3 = 1 - a_3\). On prend \((x_1, x_2, x_3) = (1, -1, 1)\) et \(c = a_1 - a_2 + a_3 \in [0, 1]\). Comme \(a_3 \leq a_2\) et \(a_1 \leq 1\),

    \[c - 1 \leq b_1 - b_2 + b_3 = a_1 + a_2 - a_3 - 1 \leq 1 - c.\]

    Donc \(|b_1 - b_2 + b_3| \leq 1 - c\) et \(|c| + |b_1 - b_2 + b_3| \leq 1\).

  • Cas 3 : \(b_2 = a_2 - 1\) et \(b_3 = 1 - a_3\). On prend \((x_1, x_2, x_3) = (-1, 1, 1)\) et \(c = -a_1 + a_2 + a_3\). Si \(c \geq 0\), alors \(a_3 \leq 1\) et \(a_2 \leq a_1\) donnent

    \[c - 1 \leq -b_1 + b_2 + b_3 = -a_1 + a_2 - a_3 + 1 \leq 1 - c.\]

    Si \(c < 0\), alors \(a_1 \leq a_2 + 1\) et \(a_3 \geq 0\) donnent

    \[-c - 1 \leq -b_1 + b_2 + b_3 = -a_1 + a_2 - a_3 + 1 \leq 1 + c.\]

    Dans les deux cas \(|-b_1 + b_2 + b_3| \leq 1 - |c|\), d'où \(|c| + |-b_1 + b_2 + b_3| \leq 1\).

  • Cas 4 : \(b_2 = 1 - a_2\) et \(b_3 = a_3 - 1\). On prend \((x_1, x_2, x_3) = (-1, 1, 1)\) et \(c = -a_1 + a_2 + a_3\). Si \(c \geq 0\), alors \(a_2 \leq 1\) et \(a_3 \leq a_1\) donnent

    \[c - 1 \leq -b_1 + b_2 + b_3 = -a_1 - a_2 + a_3 + 1 \leq 1 - c.\]

    Si \(c < 0\), alors \(a_1 \leq a_3 + 1\) et \(a_2 \geq 0\) donnent

    \[-c - 1 \leq -b_1 + b_2 + b_3 = -a_1 - a_2 + a_3 + 1 \leq 1 + c.\]

    Dans les deux cas \(|-b_1 + b_2 + b_3| \leq 1 - |c|\), d'où \(|c| + |-b_1 + b_2 + b_3| \leq 1\).

On a trouvé \(x_1, x_2, x_3\) convenables dans chaque cas.

Hérédité. Soit \(n \geq 5\) impair, et supposons le résultat vrai pour les entiers impairs plus petits. On peut encore supposer \(a_k \geq 0\) pour tout \(k\), et chaque \(b_k\) vaut \(a_k - 1\) ou \(1 - a_k\). Par le principe des tiroirs, il y a au moins trois indices \(k\) de même type ; quitte à changer tous les \(b_k\) en \(-b_k\) et à renuméroter, \(b_k = a_k - 1\) pour \(k = 1, 2, 3\). Encore par le principe des tiroirs, comme \(a_1, a_2, a_3\) sont dans \([0, 1]\), deux d'entre eux diffèrent d'au plus \(\frac{1}{2}\) ; quitte à renuméroter, on peut supposer

\[0 \leq d = a_1 - a_2 \leq \tfrac{1}{2}.\]

Par hypothèse de récurrence (appliquée aux \(n - 2\) couples d'indices \(3, \ldots, n\)), on peut choisir \(x_3, \ldots, x_n\) tels que \(a' = \sum_{k=3}^n x_k a_k\) et \(b' = \sum_{k=3}^n x_k b_k\) vérifient \(|a'| + |b'| \leq 1\). Quitte à changer tous ces \(x_k\) de signe, on peut supposer \(a' \geq 0\).

  • Cas 1 : \(b' \geq 0\). On prend \((x_1, x_2) = (-1, 1)\). Alors

    \[|-a_1 + a_2 + a'| + |-(a_1 - 1) + (a_2 - 1) + b'| = |a' - d| + |b' - d| \leq \max\{a' + b' - 2d,\ a' - b',\ b' - a',\ 2d - a' - b'\} \leq 1,\]

    car \(0 \leq a', b'\), \(a' + b' \leq 1\) et \(0 \leq d \leq \frac{1}{2}\).

  • Cas 2 : \(0 > b' \geq -a'\). On prend \((x_1, x_2) = (-1, 1)\) ; la quantité vaut encore \(|a' - d| + |b' - d|\). Si \(a' - d \geq 0\), elle vaut \(a' - b' = |a'| + |b'| \leq 1\). Si \(a' - d < 0\), elle vaut \(2d - a' - b' \leq 2d \leq 1\) (car \(a' + b' \geq 0\)).

  • Cas 3 : \(b' < -a'\). On prend \((x_1, x_2) = (1, -1)\). Alors

    \[|a_1 - a_2 + a'| + |(a_1 - 1) - (a_2 - 1) + b'| = |d + a'| + |d + b'|.\]

    Si \(d + b' \geq 0\), cela vaut \(2d + a' + b' < 2d \leq 1\). Si \(d + b' < 0\), cela vaut \(a' - b' = |a'| + |b'| \leq 1\).

On a donc trouvé \(x_1, \ldots, x_n\) vérifiant (1) dans tous les cas, et par récurrence la propriété est vraie pour tout entier impair \(n \geq 3\). \(\blacksquare\)