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é

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.