Aller au contenu

Shortlist 2007, C4

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Iran

Concepts : Invariants et monovariants · Principe des tiroirs

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 31 (page 32 du PDF)

Énoncé

Let \(A_0 = (a_1, \ldots, a_n)\) be a finite sequence of real numbers. For each \(k \geq 0\), from the sequence \(A_k = (x_1, \ldots, x_n)\) we construct a new sequence \(A_{k+1}\) in the following way.

  1. We choose a partition \(\{1, \ldots, n\} = I \cup J\), where \(I\) and \(J\) are two disjoint sets, such that the expression

    \[\left\lvert \sum_{i \in I} x_i - \sum_{j \in J} x_j \right\rvert\]

    attains the smallest possible value. (We allow the sets \(I\) or \(J\) to be empty; in this case the corresponding sum is \(0\).) If there are several such partitions, one is chosen arbitrarily.

  2. We set \(A_{k+1} = (y_1, \ldots, y_n)\), where \(y_i = x_i + 1\) if \(i \in I\), and \(y_i = x_i - 1\) if \(i \in J\).

Prove that for some \(k\), the sequence \(A_k\) contains an element \(x\) such that \(\lvert x \rvert \geq n/2\).

Indices : les idées clés
  • Lemme : si tous les termes vérifient \(\lvert x_i \rvert < a\), il existe une partition avec \(\left\lvert \sum_I x_i - \sum_J x_j \right\rvert < a\) (récurrence en plaçant chaque nouveau terme du bon côté).
  • Finitude : si tous les termes restent dans \((-n/2, n/2)\), chaque \(b_i - a_i\) est entier, donc il n'y a qu'un nombre fini de suites possibles et deux suites \(A_p = A_q\) coïncident (tiroirs).
  • Monovariant : la somme des carrés \(S_k\) augmente strictement, car \(S_{k+1} - S_k = n + 2\left(\sum_I x_i - \sum_J x_j\right) > n - 2 \cdot \frac{n}{2} = 0\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution).

Solution

Lemme. Supposons que tous les termes de la suite \((x_1, \ldots, x_n)\) vérifient \(\lvert x_i \rvert < a\). Il existe alors une partition \(\{1, 2, \ldots, n\} = I \cup J\) en deux ensembles disjoints telle que

\[\left\lvert \sum_{i \in I} x_i - \sum_{j \in J} x_j \right\rvert < a. \tag{1}\]

Preuve. Récurrence sur \(n\). Le cas de base \(n = 1\) est trivial. Pour l'hérédité, considérons une suite \((x_1, \ldots, x_n)\) (\(n > 1\)). D'après l'hypothèse de récurrence, il existe une partition \(\{1, \ldots, n - 1\} = I' \cup J'\) telle que

\[\left\lvert \sum_{i \in I'} x_i - \sum_{j \in J'} x_j \right\rvert < a.\]

Par commodité, supposons que \(\sum_{i \in I'} x_i \geq \sum_{j \in J'} x_j\). Si \(x_n \geq 0\), on choisit \(I = I'\), \(J = J' \cup \{n\}\) ; sinon, on choisit \(I = I' \cup \{n\}\), \(J = J'\). Dans les deux cas, on a \(\sum_{i \in I'} x_i - \sum_{j \in J'} x_j \in [0, a)\) et \(\lvert x_n \rvert \in [0, a)\) ; donc

\[\sum_{i \in I} x_i - \sum_{j \in J} x_j = \sum_{i \in I'} x_i - \sum_{j \in J'} x_j - \lvert x_n \rvert \in (-a, a),\]

comme voulu. \(\square\)

Revenons au problème. Supposons au contraire que, pour tout \(k\), tous les nombres de \(A_k\) soient dans l'intervalle \((-n/2, n/2)\). Considérons une suite quelconque \(A_k = (b_1, \ldots, b_n)\). Pour obtenir le terme \(b_i\), on a augmenté et diminué le nombre \(a_i\) de \(1\) plusieurs fois. Donc \(b_i - a_i\) est toujours un entier, et il y a au plus \(n\) valeurs possibles pour \(b_i\). Il y a donc au plus \(n^n\) suites \(A_k\) distinctes possibles, et deux des suites \(A_1, A_2, \ldots, A_{n^n+1}\) doivent être identiques, disons \(A_p = A_q\) pour un certain \(p < q\).

Pour tout entier \(k > 0\), soit \(S_k\) la somme des carrés des éléments de \(A_k\). Considérons deux suites consécutives \(A_k = (x_1, \ldots, x_n)\) et \(A_{k+1} = (y_1, \ldots, y_n)\). Soit \(\{1, 2, \ldots, n\} = I \cup J\) la partition utilisée à cette étape, c'est-à-dire \(y_i = x_i + 1\) pour tout \(i \in I\) et \(y_j = x_j - 1\) pour tout \(j \in J\). Comme la valeur de \(\left\lvert \sum_{i \in I} x_i - \sum_{j \in J} x_j \right\rvert\) est la plus petite possible, le lemme implique qu'elle est inférieure à \(n/2\). On a alors

\[S_{k+1} - S_k = \sum_{i \in I}\big((x_i + 1)^2 - x_i^2\big) + \sum_{j \in J}\big((x_j - 1)^2 - x_j^2\big) = n + 2\left(\sum_{i \in I} x_i - \sum_{j \in J} x_j\right) > n - 2 \cdot \frac{n}{2} = 0.\]

On obtient ainsi \(S_q > S_{q-1} > \cdots > S_p\). C'est impossible, puisque \(A_p = A_q\) et donc \(S_p = S_q\). \(\blacksquare\)