Shortlist 2016, C7¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 40 (page 43 du PDF)
Problème 6 de l'OIM 2016
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2016, où il était le problème 6 (jour 2).
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Soit \(n \geq 2\) un entier. Dans le plan, on a \(n\) segments tels que deux segments quelconques aient un point d'intersection intérieur, et que trois segments ne se coupent jamais en un même point. Jeff place un escargot à l'une des extrémités de chaque segment, puis frappe \(n - 1\) fois dans ses mains. À chaque fois qu'il frappe dans ses mains, tous les escargots avancent le long de leur segment jusqu'au point d'intersection suivant, où ils restent jusqu'au clap suivant. Comme chaque segment porte \(n - 1\) points d'intersection, après \(n - 1\) claps, chaque escargot atteint le point d'intersection le plus éloigné de son point de départ.
(a) Montrer que si \(n\) est impair, Jeff peut toujours placer les escargots de sorte que deux d'entre eux n'occupent jamais le même point d'intersection.
(b) Montrer que si \(n\) est pair, il y a forcément un moment où deux escargots occupent le même point d'intersection, quelle que soit la façon dont Jeff place les escargots.
Énoncé original (anglais)
Let \(n \geq 2\) be an integer. In the plane, there are \(n\) segments given in such a way that any two segments have an intersection point in the interior, and no three segments intersect at a single point. Jeff places a snail at one of the endpoints of each of the segments and claps his hands \(n - 1\) times. Each time when he claps his hands, all the snails move along their own segments and stay at the next intersection points until the next clap. Since there are \(n - 1\) intersection points on each segment, all snails will reach the furthest intersection points from their starting points after \(n - 1\) claps.
(a) Prove that if \(n\) is odd then Jeff can always place the snails so that no two of them ever occupy the same intersection point.
(b) Prove that if \(n\) is even then there must be a moment when some two snails occupy the same intersection point no matter how Jeff places the snails.
Indices : les idées clés
- Géométrie combinatoire : on prolonge les segments en droites coupant un grand disque, et tout se lit sur l'ordre des \(2n\) extrémités le long du cercle.
- Marquage alterné « entrée / sortie » : sur le cercle, on marque alternativement les extrémités ; pour \(n\) impair, chaque droite a exactement une extrémité « entrée ».
- Argument de parité : deux escargots ne se rencontrent en \(P\) que si les segments \(A_iP\) et \(A_jP\) portent le même nombre de points d'intersection, ce qui impose une somme paire.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2016 (une solution et une remarque).
Solution¶
On considère un grand disque contenant tous les segments. On prolonge chaque segment en une droite \(l_i\), qui coupe le bord du disque en deux points distincts \(A_i\) et \(B_i\). Comme deux droites quelconques se coupent à l'intérieur du disque, il y a exactement \(n - 1\) points (parmi les \(2n\) extrémités) sur chacun des deux arcs délimités par \(A_i\) et \(B_i\) : en effet, chacune des \(n-1\) autres droites coupe \(l_i\), donc a une extrémité de chaque côté de \(l_i\).
(a) \(n\) impair. On parcourt le cercle et on marque les \(2n\) points \(A_i, B_i\) alternativement « entrée » et « sortie ». Il y a exactement \(n - 1\) points entre \(A_i\) et \(B_i\) ; comme \(n\) est impair, \(n-1\) est pair, donc l'un des deux points \(A_i\), \(B_i\) est marqué « entrée » et l'autre « sortie ». Jeff place alors chaque escargot à l'extrémité de son segment située du côté « entrée » de la droite correspondante. Montrons que les escargots de \(l_i\) et \(l_j\) ne se rencontrent jamais.
Quitte à renommer, les escargots partent du côté de \(A_i\) et de \(A_j\) ; soit \(P\) le point d'intersection de \(l_i\) et \(l_j\). Comme \(A_i\) et \(A_j\) sont tous deux marqués « entrée », il y a un nombre impair de points sur l'arc \(A_iA_j\) (celui qui ne contient ni \(B_i\) ni \(B_j\), c'est-à-dire l'arc qui borde la région délimitée par \(A_iP\) et \(PA_j\)). Chacun de ces points appartient à une droite \(l_k\), et une telle droite \(l_k\) coupe exactement un des deux segments \(A_iP\) et \(A_jP\). Les autres droites coupent soit les deux segments \(A_iP\) et \(A_jP\), soit aucun. Ainsi, le nombre total de points d'intersection situés sur \(A_iP\) et sur \(A_jP\) (sans compter \(P\)) est impair.

Or, si les deux escargots arrivaient en \(P\) au même moment, ils auraient franchi le même nombre de points d'intersection, donc \(A_iP\) et \(A_jP\) porteraient le même nombre de points d'intersection, et le total serait pair. C'est une contradiction : les escargots ne se rencontrent jamais.
(b) \(n\) pair. Jeff place les escargots d'une manière quelconque ; on marque chaque point \(A_i\) ou \(B_i\) « entrée » ou « sortie » selon le sens de déplacement de l'escargot sur \(l_i\). Il existe alors deux points voisins sur le cercle, disons \(A_i\) et \(A_j\), tous deux marqués « entrée ».
Précision ajoutée : sinon, les \(n\) points « entrée » et les \(n\) points « sortie » alterneraient exactement le long du cercle ; comme \(A_i\) et \(B_i\) sont séparés par \(n - 1\) points, nombre impair, ils auraient la même marque, alors qu'une droite a exactement une extrémité « entrée ».
Soit \(P\) le point d'intersection des segments \(A_iB_i\) et \(A_jB_j\). Comme aucun point n'est situé entre \(A_i\) et \(A_j\) sur le cercle, toute autre droite qui coupe l'un des segments \(A_iP\), \(A_jP\) coupe aussi l'autre. Ces deux segments portent donc le même nombre de points d'intersection, et les escargots partis de \(A_i\) et de \(A_j\) arrivent en \(P\) au même moment. \(\blacksquare\)
Remarques¶
Remarque. Les conclusions sont fausses pour des pseudo-segments (des courbes qui se coupent deux à deux exactement une fois) : en voici deux contre-exemples.

Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2019 C6 ★★★☆☆ : Ordonner \(2n\) points pour que les angles du polygone obtenu se répartissent en deux groupes de même somme.
- 2009 G5 ★★★★☆ : Tout polygone convexe à centre de symétrie tient dans un parallélogramme d'aire au plus \(\sqrt{2}\) fois la sienne.
- 2007 G6 ★★★★☆ : Un quadrilatère inscrit dans un autre : comparer son aire aux deux plus petits triangles des coins.
- 2022 C9 ★★★★★ : Une bijection de \(\mathbb{N}^2\) compatible avec les translations : combien de valeurs impaires sur le carré \(100 \times 100\) ?