Shortlist 2021, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Principe des tiroirs · Double comptage
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 32 (page 32 du PDF)
Énoncé¶
Let \(n\) and \(k\) be two integers with \(n > k \geq 1\). There are \(2n + 1\) students standing in a circle. Each student \(S\) has \(2k\) neighbours, namely the \(k\) students closest to \(S\) on the right, and the \(k\) students closest to \(S\) on the left.
Suppose that \(n + 1\) of the students are girls, and the other \(n\) are boys. Prove that there is a girl with at least \(k\) girls among her neighbours.
Indices : les idées clés
- Codage par une suite périodique : filles \(= 1\), garçons \(= 0\), et \(b_i = a_i + a_{i-k-1} - 1 \in \{-1, 0, 1\}\), dont la somme sur toute période vaut \(1\).
- Réduction : il suffit de trouver \(i\) avec \(b_i = 1\) et \(b_{i+1} + \cdots + b_{i+k} \geq 0\).
- Principe des tiroirs : dans une suite d'indices construite gloutonnement, deux indices sont congrus modulo \(2n+1\).
- Double comptage : on calcule la même somme des \(b_i\) par blocs (somme \(\leq 0\)) et par périodes (somme \(> 0\)).
- Lemme de Raney / problème des stations-service (remarques) : le même fait sous une forme classique.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2021 (une solution et quatre remarques).
Solution¶
Remplaçons les filles par des \(1\) et les garçons par des \(0\) : on obtient des nombres \(a_1, a_2, \ldots, a_{2n+1}\) disposés en cercle. Prolongeons-les en une suite périodique en posant \(a_{j + 2n+1} = a_j\) pour tout \(j \in \mathbb{Z}\) :
Posons, pour tout \(i \in \mathbb{Z}\),
Comme chaque période contient \(n+1\) uns, on a, pour tout \(m \in \mathbb{Z}\),
En particulier, il existe un indice \(i_0\) tel que \(b_{i_0} = 1\).
Réduction. Nous voulons trouver un indice \(i\) tel que
En effet, \(b_i = 1\) impose \(a_i = 1\) (l'élève \(i\) est une fille), et la seconde condition s'écrit \(\sum_{j=i+1}^{i+k} (a_j + a_{j-k-1}) \geq k\), c'est-à-dire
cette fille a au moins \(k\) filles parmi ses voisins.
Preuve par l'absurde. Supposons que, pour tout indice \(i\) avec \(b_i = 1\), la somme \(b_{i+1} + \cdots + b_{i+k}\) soit négative. Partant d'un indice \(i_0\) avec \(b_{i_0} = 1\), construisons une suite \(i_0, i_1, i_2, \ldots\) où, pour \(j > 0\), \(i_j\) est le plus petit indice tel que \(i_j > i_{j-1} + k\) et \(b_{i_j} = 1\). Par le principe des tiroirs, deux des \(2n+2\) nombres \(i_0, i_1, \ldots, i_{2n+1}\) sont congrus modulo \(2n+1\) ; quitte à recommencer la construction à partir du premier des deux, on peut supposer que ce sont \(i_0\) et \(i_T\).
Calculons de deux façons la somme \(\sum_{i = i_0}^{i_T - 1} b_i\) (double comptage).
Par blocs. Pour \(0 \leq j \leq T-1\), posons \(S_j = b_{i_j} + b_{i_j + 1} + \cdots + b_{i_{j+1} - 1}\). Par minimalité de \(i_{j+1}\), les termes \(b_{i_j + k + 1}, \ldots, b_{i_{j+1} - 1}\) sont tous \(\leq 0\), donc
Par périodes. Comme \(2n+1\) divise \(i_T - i_0\), la relation (1) donne
Ces deux résultats se contredisent, ce qui achève la preuve. \(\blacksquare\)
Remarques¶
Remarque 1 (Raney, stations-service). Une fois le problème ramené à trouver un indice vérifiant (2), on peut conclure avec la partie « existence » de l'énoncé suivant.
Lemme de Raney. Si \(\langle x_1, x_2, \ldots, x_m \rangle\) est une suite d'entiers de somme \(+1\), alors exactement une de ses permutations circulaires \(\langle x_1, \ldots, x_m \rangle\), \(\langle x_2, \ldots, x_m, x_1 \rangle\), ..., \(\langle x_m, x_1, \ldots, x_{m-1} \rangle\) a toutes ses sommes partielles strictement positives.
Une version peut-être plus connue, qui permet aussi de résoudre le problème, est le problème des stations-service : si plusieurs stations sur un circuit circulaire contiennent au total exactement assez d'essence pour faire un tour, alors on peut faire le tour complet en partant, réservoir vide, de la bonne station. Ces deux résultats ont de nombreuses preuves, dont les idées peuvent se cacher dans des solutions directes (c'est en fait le cas ci-dessus) qui évitent parfois l'introduction des \(b_i\) (remarque 2).
Remarque 2 (variante sans les \(b_i\)). Supposons le contraire et gardons les \(a_i\). À partir d'un indice \(s_0\) avec \(a_{s_0} = 1\), on définit \(s_i\) comme le plus petit indice supérieur à \(s_{i-1} + k\) tel que \(a_{s_i} = 1\). Deux des indices sont congrus modulo \(2n+1\) ; on suppose que ce sont \(s_0\) et \(s_T\), avec \(s_T - s_0 = t(2n+1)\), et alors \(s_{T+1} - s_T = s_1 - s_0\). On pose \(L_i = s_{i+1} - s_i\) et \(S_i = a_{s_i} + a_{s_i + 1} + \cdots + a_{s_{i+1} - 1}\). Par hypothèse, pour \(i = 1, \ldots, T\),
et \(a_j = 0\) pour \(s_i + k < j < s_{i+1}\). D'où
En sommant pour \(i = 1, \ldots, T\) :
ce qui est absurde.
Remarque 3 (autre preuve du lemme de Raney). Traçons les sommes partielles \(s_n = x_1 + \cdots + x_n\) en fonction de \(n\) (en prolongeant la suite périodiquement). Comme \(s_{m+n} = s_n + 1\), la pente moyenne est \(1/m\). Tout le graphe tient entre deux droites de pente \(1/m\), et ces droites touchent le graphe une seule fois par période de \(m\) points, car une droite de pente \(1/m\) ne passe par des points à coordonnées entières qu'une fois toutes les \(m\) unités. Le point de contact inférieur (unique dans une période) est le seul point de départ à partir duquel toutes les sommes partielles sont positives.
Remarque 4. L'exemple \(0110\,0110\,1\) montre que, selon la valeur de \(k\), la fille cherchée peut se trouver à des places différentes.