Aller au contenu

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é

On suppose que \(1000\) élèves sont disposés en cercle. Montrer qu'il existe un entier \(k\) avec \(100 \leq k \leq 300\) tel que, dans ce cercle, il existe un groupe de \(2k\) élèves consécutifs dont la première moitié contient autant de filles que la seconde.

Énoncé original (anglais)

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

\[S_k(i) = a_i + a_{i+1} + \cdots + a_{i+k-1}.\]

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

\[S_{100}(j) \leq S_{100}(j + 100) - 1, \quad \text{mais} \quad S_{100}(j + 1) \geq S_{100}(j + 101) + 1. \tag{1}\]

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

\[a_j = 0, \qquad a_{j+100} = 1, \qquad a_{j+200} = 0.\]

En reportant dans (1), on obtient aussi \(S_{99}(j + 1) \leq S_{99}(j + 101) \leq S_{99}(j + 1)\), d'où

\[S_{99}(j + 1) = S_{99}(j + 101). \tag{2}\]

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,

\[S_{100+\ell}(j - \ell + 1) = (a_{j-\ell+1} + \cdots + a_j) + S_{99}(j + 1) + a_{j+100} = S_{99}(j + 1) + 1,\]
\[S_{100+\ell}(j + 101) = S_{99}(j + 101) + (a_{j+200} + \cdots + a_{j+200+\ell-1}) + a_{j+200+\ell} = S_{99}(j + 101) + 1.\]

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

\[\underbrace{1, \ldots, 1}_{167}, \underbrace{0, \ldots, 0}_{167}, \underbrace{1, \ldots, 1}_{167}, \underbrace{0, \ldots, 0}_{167}, \underbrace{1, \ldots, 1}_{167}, \underbrace{0, \ldots, 0}_{165} \qquad \text{et} \qquad \underbrace{1, \ldots, 1}_{249}, \underbrace{0, \ldots, 0}_{251}, \underbrace{1, \ldots, 1}_{249}, \underbrace{0, \ldots, 0}_{251}\]

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.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2024 C3 ★★☆☆☆ : Des chevaliers en cercle échangent leurs places pour serrer la main de leur partenaire : combien d'échanges ?
  • 2022 A4 ★★☆☆☆ : Des réels de \([0, 1]\) de somme \(s \geq 3\) : deux d'entre eux vérifient \(2^{j-i} x_i x_j > 2^{s-3}\).
  • 2019 A3 ★★☆☆☆ : La partie qui approche le mieux \(1\) pour une suite croissante de somme \(2\) l'atteint exactement pour une autre suite.
  • 2007 A1 ★★☆☆☆ · OIM P1 : Approcher une suite quelconque par une suite croissante : l'écart minimal vaut exactement \(d/2\).