Shortlist 2011, C2¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Principe extrémal · Invariants et monovariants
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 29 (page 30 du PDF)
Énoncé¶
Suppose that \(1000\) students are standing in a circle. Prove that there exists an integer \(k\) with \(100 \leq k \leq 300\) such that in this circle there exists a contiguous group of \(2k\) students, for which the first half contains the same number of girls as the second half.
Indices : les idées clés
- Reformuler : avec \(a_i = 1\) pour une fille, \(S_k(i) = a_i + \cdots + a_{i+k-1}\) ; il s'agit de trouver \(k\) et \(i\) avec \(S_k(i) = S_k(i + k)\).
- Principe extrémal : en un \(i\) où \(S_{100}(i)\) est maximal, la différence \(S_{100}(j) - S_{100}(j + 100)\) change de signe entre \(i - 100\) et \(i\) ; on obtient \(a_j = 0\), \(a_{j+100} = 1\), \(a_{j+200} = 0\) et \(S_{99}(j + 1) = S_{99}(j + 101)\).
- Prolonger : en allant jusqu'aux filles les plus proches de part et d'autre, on trouve deux blocs consécutifs de longueur \(100 + \ell \leq 299\) de même somme.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution et une remarque).
Solution¶
Numérotons les élèves de \(1\) à \(1000\). Posons \(a_i = 1\) si le \(i\)-ème élève est une fille, et \(a_i = 0\) sinon. On prolonge cette notation à tous les entiers \(i\) en posant \(a_{i+1000} = a_{i-1000} = a_i\). Posons ensuite
L'énoncé se reformule ainsi : il existe un entier \(k\) avec \(100 \leq k \leq 300\) et un indice \(i\) tels que \(S_k(i) = S_k(i + k)\).
Supposons que cet énoncé soit faux. Choisissons un indice \(i\) tel que \(S_{100}(i)\) atteigne sa valeur maximale. En particulier, \(S_{100}(i - 100) - S_{100}(i) < 0\) et \(S_{100}(i) - S_{100}(i + 100) > 0\) (une égalité rendrait l'énoncé vrai). La fonction \(S(j) - S(j + 100)\) change donc de signe sur le segment \([i - 100, i]\) : il existe un indice \(j \in [i - 100, i - 1]\) tel que
En soustrayant la première inégalité de la seconde, on obtient \(a_{j+100} - a_j \geq a_{j+200} - a_{j+100} + 2\), donc
En reportant dans (1), on obtient aussi \(S_{99}(j + 1) \leq S_{99}(j + 101) \leq S_{99}(j + 1)\), d'où
Soient maintenant \(k\) et \(\ell\) les plus petits entiers strictement positifs tels que \(a_{j-k} = 1\) et \(a_{j+200+\ell} = 1\). Par symétrie, on peut supposer \(k \geq \ell\). Si \(k \geq 200\), alors \(a_j = a_{j-1} = \cdots = a_{j-199} = 0\), donc \(S_{100}(j - 199) = S_{100}(j - 99) = 0\), ce qui contredit l'hypothèse. Donc \(\ell \leq k \leq 199\). Enfin,
Avec (2), on obtient \(S_{100+\ell}(j - \ell + 1) = S_{100+\ell}(j + 101)\) et \(100 + \ell \leq 299\), ce qui contredit à nouveau l'hypothèse. \(\blacksquare\)
Remarque¶
La solution montre qu'on peut remplacer le nombre \(300\) de l'énoncé par \(299\). Étudions des améliorations de ce résultat : par quel intervalle peut-on remplacer \([100, 300]\) en gardant l'énoncé vrai ?
D'abord, les deux exemples
montrent que l'intervalle ne peut être remplacé ni par \([84, 248]\), ni par \([126, 374]\).
En revanche, on affirme qu'il peut être remplacé par \([125, 250]\). Cet énoncé est invariant quand on échange les \(1\) et les \(0\). Supposons au contraire qu'il n'y ait aucun \(k\) admissible dans \([125, 250]\). Les arguments de la solution donnent facilement le lemme suivant.
Lemme. Sous cette hypothèse, supposons que pour des indices \(i < j\) on ait \(S_{125}(i) \leq S_{125}(i + 125)\) mais \(S_{125}(j) \geq S_{125}(j + 125)\). Alors il existe \(t \in [i, j - 1]\) tel que \(a_t = a_{t-1} = \cdots = a_{t-125} = 0\) et \(a_{t+250} = a_{t+251} = \cdots = a_{t+375} = 0\). \(\square\)
Appelons foule un segment \([i, j]\) d'indices tel que (a) \(a_i = a_{i+1} = \cdots = a_j\), mais \(a_{i-1} \neq a_i \neq a_{j+1}\), et (b) \(j - i \geq 125\). Avec le lemme, on montre comme dans la solution qu'il existe une foule. Prenons toutes les foules du cercle, et numérotons-les dans l'ordre cyclique \(A_1, \ldots, A_d\), avec la convention \(A_{s+d} = A_{s-d} = A_s\).
Considérons une foule, disons \(A_1\). On a \(A_1 = [i, i + t]\) avec \(125 \leq t \leq 248\) (si \(t \geq 249\), alors \(a_i = a_{i+1} = \cdots = a_{i+249}\) et donc \(S_{125}(i) = S_{125}(i + 125)\), ce qui contredit l'hypothèse). On peut supposer \(a_i = 1\). Alors \(S_{125}(i + t - 249) \leq 125 = S_{125}(i + t - 124)\) et \(S_{125}(i) = 125 \geq S_{125}(i + 125)\), donc par le lemme il existe un indice \(j \in [i + t - 249, i - 1]\) tel que les segments \([j - 125, j]\) et \([j + 250, j + 375]\) soient contenus dans des foules.
Fixons un tel \(j\) et notons \(B_1\) le segment \([j + 1, j + 249]\). Clairement, \(A_1 \subseteq B_1\). De plus, \(B_1\) ne peut contenir aucune autre foule que \(A_1\), puisque \(\lvert B_1 \rvert = 249 < 2 \cdot 126\). Il est donc clair que \(j \in A_d\) et \(j + 250 \in A_2\) ; en particulier, les « sexes » de \(A_d\) et \(A_2\) sont différents de celui de \(A_1\).
En faisant de même pour chaque foule \(A_s\), on trouve des segments \(B_s = [j_s + 1, j_s + 249]\) avec \(\lvert B_s \rvert = 249\), \(A_s \subseteq B_s\), \(j_s \in A_{s-1}\) et \(j_s + 250 \in A_{s+1}\). Ainsi \(B_s\) recouvre tout le segment entre \(A_{s-1}\) et \(A_{s+1}\), donc les ensembles \(B_1, \ldots, B_d\) recouvrent \(1000\) indices consécutifs. Cela implique \(249d \geq 1000\), donc \(d \geq 5\). De plus, le sexe des \(A_i\) alterne, donc \(d\) est pair ; par conséquent \(d \geq 6\).
Considérons maintenant les trois segments \(A_1 = [i_1, i'_1]\), \(B_2 = [j_2 + 1, j_2 + 249]\) et \(A_3 = [i_3, i'_3]\). Par construction, \([j_2 - 125, j_2] \subseteq A_1\) et \([j_2 + 250, j_2 + 375] \subseteq A_3\), d'où \(i_1 \leq j_2 - 125\) et \(i'_3 \geq j_2 + 375\). Donc \(i'_3 - i_1 \geq 500\). De même, si \(A_4 = [i_4, i'_4]\) et \(A_6 = [i_6, i'_6]\), alors \(i'_6 - i_4 \geq 500\). Mais \(d \geq 6\) donne \(i_1 < i'_3 < i_4 < i'_6 < i_1 + 1000\), donc \(1000 > (i'_3 - i_1) + (i'_6 - i_4) \geq 500 + 500\). Cette contradiction finale prouve l'affirmation.
On peut même montrer que l'intervalle de l'énoncé peut être remplacé par \([125, 249]\) (aucune de ces deux bornes ne peut être améliorée, d'après les exemples ci-dessus). Mais la preuve est un peu fastidieuse, et on ne la présente pas ici.