Shortlist 2008, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Double comptage · Principe extrémal
Solution officielle : Shortlist officielle 2008 (avec solutions), p. 26 (page 27 du PDF)
Énoncé¶
Let \(S = \{x_1, x_2, \ldots, x_{k+\ell}\}\) be a \((k + \ell)\)-element set of real numbers contained in the interval \([0, 1]\); \(k\) and \(\ell\) are positive integers. A \(k\)-element subset \(A \subset S\) is called nice if
Prove that the number of nice subsets is at least \(\dfrac{2}{k + \ell}\dbinom{k + \ell}{k}\).
Indices : les idées clés
- Disposition circulaire : à chaque permutation de \(S\), on associe les \(k + \ell\) blocs \(A_i\) de \(k\) éléments consécutifs ; deux blocs voisins vérifient \(\lvert f(A_{i+1}) - f(A_i) \rvert \leq 2d\).
- Somme nulle : \(\sum_i f(A_i) = 0\) ; en partant du minimum et du maximum, on trouve au moins deux blocs dans \([-d, d]\) (valeurs intermédiaires discrètes).
- Double comptage : au moins \(2(k + \ell)!\) paires (permutation, bloc agréable), et chaque partie est associée à exactement \((k + \ell)\,k!\,\ell!\) permutations.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).
Solution¶
Pour une partie \(A \subset S\) à \(k\) éléments, posons \(f(A) = \frac{1}{k}\sum_{x_i \in A} x_i - \frac{1}{\ell}\sum_{x_j \in S \setminus A} x_j\), et notons \(d = \frac{k + \ell}{2k\ell}\). Par définition, une partie \(A\) est agréable si \(\lvert f(A) \rvert \leq d\).
À chaque permutation \((y_1, y_2, \ldots, y_{k+\ell})\) de l'ensemble \(S = \{x_1, x_2, \ldots, x_{k+\ell}\}\), on associe \(k + \ell\) parties de \(S\) à \(k\) éléments, à savoir \(A_i = \{y_i, y_{i+1}, \ldots, y_{i+k-1}\}\), \(i = 1, 2, \ldots, k + \ell\). Les indices sont pris modulo \(k + \ell\) ici et dans la suite. Autrement dit, si \(y_1, y_2, \ldots, y_{k+\ell}\) sont disposés sur un cercle dans cet ordre, les parties en question sont tous les blocs possibles de \(k\) éléments consécutifs.
Affirmation. Au moins deux parties agréables sont associées à chaque permutation de \(S\).
Preuve. Les parties voisines \(A_i\) et \(A_{i+1}\) ne diffèrent que par les éléments \(y_i\) et \(y_{i+k}\), \(i = 1, \ldots, k + \ell\). Par définition de \(f\), et comme \(y_i, y_{i+k} \in [0, 1]\),
Chaque élément \(y_i \in S\) appartient à exactement \(k\) des parties \(A_1, \ldots, A_{k+\ell}\). Donc, dans \(k\) des expressions \(f(A_1), \ldots, f(A_{k+\ell})\), le coefficient de \(y_i\) vaut \(1/k\) ; dans les \(\ell\) autres, il vaut \(-1/\ell\). La contribution de \(y_i\) à la somme des \(f(A_i)\) vaut donc \(k \cdot 1/k - \ell \cdot 1/\ell = 0\). Comme c'est vrai pour tout \(i\), il s'ensuit que \(f(A_1) + \cdots + f(A_{k+\ell}) = 0\).
Si \(f(A_p) = \min f(A_i)\) et \(f(A_q) = \max f(A_i)\), on obtient en particulier \(f(A_p) \leq 0\), \(f(A_q) \geq 0\). Supposons \(p < q\) (le cas \(p > q\) est analogue ; et l'affirmation est vraie pour \(p = q\), puisqu'alors \(f(A_i) = 0\) pour tout \(i\)).
Montrons qu'au moins deux des parties \(A_1, \ldots, A_{k+\ell}\) sont agréables. L'intervalle \([-d, d]\) est de longueur \(2d\), et l'on a vu que des termes voisins de la disposition circulaire \(f(A_1), \ldots, f(A_{k+\ell})\) diffèrent d'au plus \(2d\). Supposons que \(f(A_p) < -d\) et \(f(A_q) > d\). Alors l'un des nombres \(f(A_{p+1}), \ldots, f(A_{q-1})\) est dans \([-d, d]\), ainsi que l'un des nombres \(f(A_{q+1}), \ldots, f(A_{p-1})\). Par conséquent, l'une des parties \(A_{p+1}, \ldots, A_{q-1}\) est agréable, de même que l'une des parties \(A_{q+1}, \ldots, A_{p-1}\). Si \(-d \leq f(A_p)\) et \(f(A_q) \leq d\), alors \(A_p\) et \(A_q\) sont agréables.
Soit maintenant \(f(A_p) < -d\) et \(f(A_q) \leq d\). Alors \(f(A_p) + f(A_q) < 0\), et comme \(\sum f(A_i) = 0\), il existe un \(r \neq q\) tel que \(f(A_r) > 0\). On a \(0 < f(A_r) \leq f(A_q) \leq d\), donc les parties \(A_r\) et \(A_q\) sont agréables. Le seul cas restant, \(-d \leq f(A_p)\) et \(d < f(A_q)\), est analogue. \(\square\)
Appliquons l'affirmation à chacune des \((k + \ell)!\) permutations de \(S = \{x_1, x_2, \ldots, x_{k+\ell}\}\). On obtient au moins \(2(k + \ell)!\) parties agréables, comptées avec répétitions : chaque partie agréable est comptée autant de fois qu'il y a de permutations auxquelles elle est associée.
D'autre part, chaque partie \(A \subset S\) à \(k\) éléments est associée à exactement \((k + \ell)\,k!\,\ell!\) permutations. En effet, une telle permutation \((y_1, y_2, \ldots, y_{k+\ell})\) est déterminée par trois choix indépendants : un indice \(i \in \{1, 2, \ldots, k + \ell\}\) tel que \(A = \{y_i, y_{i+1}, \ldots, y_{i+k-1}\}\), une permutation \((y_i, y_{i+1}, \ldots, y_{i+k-1})\) de l'ensemble \(A\), et une permutation \((y_{i+k}, y_{i+k+1}, \ldots, y_{i-1})\) de l'ensemble \(S \setminus A\).
En résumé, il y a au moins
parties agréables. \(\blacksquare\)