Shortlist 2019, C6

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : USA

Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Invariants et monovariants · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2019 (avec solutions), section C6 (livret PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(n > 1\) be an integer. Suppose we are given \(2n\) points in a plane such that no three of them are collinear. The points are to be labelled \(A_1, A_2, \ldots, A_{2n}\) in some order. We then consider the \(2n\) angles \(\angle A_1A_2A_3, \angle A_2A_3A_4, \ldots, \angle A_{2n-2}A_{2n-1}A_{2n}, \angle A_{2n-1}A_{2n}A_1, \angle A_{2n}A_1A_2\). We measure each angle in the way that gives the smallest positive value (i.e. between \(0^\circ\) and \(180^\circ\)). Prove that there exists an ordering of the given points such that the resulting \(2n\) angles can be separated into two groups with the sum of one group of angles equal to the sum of the other group.

Indices : les idées clés

• Géométrie combinatoire (solutions 1 à 3) : une droite \(\ell\) sépare les points en deux groupes de \(n\) ; on numérote en alternant les deux côtés.
• Angles orientés et tours à gauche / à droite : en comptant \(+\) les angles où le chemin tourne à gauche et \(-\) ceux où il tourne à droite, la somme est un multiple de \(360^\circ\).
• Invariant par déformation (solution 2) : cette somme ne peut changer que si un angle passe par \(180^\circ\), ce que la droite \(\ell\) interdit.
• Récurrence (solution 3) : avec des angles signés additifs, on passe de \(n = k\) à \(n = k+1\) grâce au cas \(n = 2\).
• Argument de continuité discrète (solution 4) : une transposition change la somme de \(0\) ou \(\pm 360^\circ\), et renverser l'ordre change \(360k^\circ\) en \(-360k^\circ\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (quatre solutions et deux remarques).

Solution 1

Soit \(\ell\) une droite séparant les points en deux groupes \(L\) et \(R\) de \(n\) points chacun. Numérotons les points \(A_1, A_2, \ldots, A_{2n}\) de sorte que \(L = \{A_1, A_3, \ldots, A_{2n-1}\}\). Montrons que cette numérotation convient.

Prenons la droite \(s = A_{2n}A_1\).

(a) Faisons tourner \(s\) autour de \(A_1\) jusqu'à ce qu'elle passe par \(A_2\), dans le sens tel que \(s\) ne soit jamais parallèle à \(\ell\).

(b) Faisons ensuite tourner la nouvelle droite \(s\) autour de \(A_2\) jusqu'à ce qu'elle passe par \(A_3\), de la même manière.

(c) Effectuons \(2n - 2\) étapes de plus ; \(s\) revient alors à sa position initiale.

L'angle total (orienté) \(\Theta\) dont \(s\) a tourné est clairement un multiple de \(180^\circ\). D'autre part, \(s\) n'a jamais été parallèle à \(\ell\), ce qui n'est possible que si \(\Theta = 0\). Précision ajoutée : comme \(A_{i-1}\) et \(A_{i+1}\) sont du côté de \(\ell\) opposé à \(A_i\), la rotation autour de \(A_i\) balaie les demi-droites issues de \(A_i\) qui pointent vers ce côté, et elle est donc exactement d'angle \(\angle A_{i-1}A_iA_{i+1}\), dans un sens ou dans l'autre. Il reste à répartir les \(2n\) angles en ceux où \(s\) tourne dans le sens direct et les autres : les deux groupes ont la même somme. \(\blacksquare\)

Solution 2

Parcourons le chemin fermé passant par les \(A_i\) dans l'ordre, en ligne droite entre deux points consécutifs, et soit \(\theta_i\) l'angle extérieur en \(A_i\), compté positivement si le chemin tourne à gauche et négativement s'il tourne à droite. Alors \(\sum_{i=1}^{2n} \theta_i = 360k^\circ\) pour un entier \(k\). Soit \(\varphi_i = \angle A_{i-1}A_iA_{i+1}\) (indices modulo \(2n\)) comme dans l'énoncé ; ainsi \(\varphi_i = 180^\circ - |\theta_i|\).

Soit \(L\) l'ensemble des \(i\) où le chemin tourne à gauche et \(R\) l'ensemble de ceux où il tourne à droite. Alors

\[S = \sum_{i \in L} \varphi_i - \sum_{i \in R} \varphi_i = \big(180(|L| - |R|) - 360k\big)^\circ,\]

qui est un multiple de \(360^\circ\) car le nombre de points est pair. Nous allons montrer qu'on peut numéroter les points de sorte que \(S = 0\) ; alors \(L\) et \(R\) répondent à la question.

La valeur de \(S\) est définie pour une classe un peu plus large de configurations : deux points peuvent coïncider s'ils ne sont pas consécutifs, et trois points peuvent être alignés tant que \(A_i\), \(A_{i+1}\), \(A_{i+2}\) ne sont pas alignés dans cet ordre. Il sera commode (sans être indispensable) de considérer de telles configurations.

Regardons comment \(S\) varie quand on déplace un seul des \(A_i\) le long d'un chemin rectiligne (ne passant par aucun \(A_j\) et ne restant sur aucune droite \(A_jA_k\), mais pouvant traverser de telles droites). Comme \(S\) est un multiple de \(360^\circ\) et que les angles varient continûment, \(S\) ne peut changer que lorsqu'un point passe de \(R\) à \(L\) ou inversement. De plus, si \(\varphi_j = 0\) au moment où \(A_j\) change d'ensemble, \(S\) ne change pas ; \(S\) ne change que si \(\varphi_j = 180^\circ\) à ce moment.

Pour une configuration de départ quelconque, construisons une nouvelle configuration, numérotée de sorte que \(S = 0\), que l'on peut déformer en la configuration d'origine sans qu'aucun \(\varphi_i\) ne passe par \(180^\circ\) ; on aura alors aussi \(S = 0\) pour la configuration d'origine avec ces numéros.

Prenons une droite ayant \(n\) points de chaque côté. La nouvelle configuration est formée de \(n\) copies d'un même point de chaque côté de la droite, avec un chemin qui alterne entre les deux côtés ; tous les angles sont nuls, donc \(S = 0\). En déplaçant les points jusqu'à leurs positions d'origine, chacun restant de son côté de la droite, aucun angle \(\varphi_i\) ne peut passer par \(180^\circ\), car un segment ne peut pas aller d'un côté de la droite à l'autre puis revenir (les voisins de \(A_i\) sont de l'autre côté). La déformation laisse donc \(S = 0\) (invariant). \(\blacksquare\)

Solution 3

Soit \(\ell\) une droite ayant \(n\) points d'un côté et \(n\) de l'autre ; on la suppose horizontale (quitte à faire tourner le plan), ce qui permet de parler de « dessus », « dessous », « gauche », « droite ». On note \(P_1, \ldots, P_n\) les points au-dessus de \(\ell\) (dans un ordre quelconque) et \(Q_1, \ldots, Q_n\) ceux en dessous.

Le segment \(P_iQ_j\) coupe \(\ell\) en un point noté \(I_{ij}\). Si \(P_i\) est relié à \(Q_j\) et \(Q_k\) avec \(j < k\), alors \(I_{ij} \neq I_{ik}\), car \(P_i\), \(Q_j\), \(Q_k\) ne sont pas alignés.

On définit un signe pour chaque angle \(\angle Q_jP_iQ_k\). Supposons \(j < k\). Le signe est positif dans les deux cas suivants :

• \(i\) est impair et \(I_{ij}\) est à gauche de \(I_{ik}\) ;
• \(i\) est pair et \(I_{ij}\) est à droite de \(I_{ik}\).

Sinon, il est négatif. Si \(j > k\), le signe de \(\angle Q_jP_iQ_k\) est celui de \(\angle Q_kP_iQ_j\). On définit de même le signe de \(\angle P_jQ_iP_k\) pour \(j < k\) ; par exemple, il est positif si \(i\) est impair et \(I_{ji}\) est à gauche de \(I_{ki}\). Désormais, \(\angle Q_jP_iQ_k\) ou \(\angle P_jQ_iP_k\) désigne la mesure de l'angle affectée de ce signe.

On a alors le fait important suivant pour les mesures signées :

\[\angle Q_{i_1}P_kQ_{i_3} = \angle Q_{i_1}P_kQ_{i_2} + \angle Q_{i_2}P_kQ_{i_3} \tag{1}\]

pour tous points \(P_k\), \(Q_{i_1}\), \(Q_{i_2}\), \(Q_{i_3}\) avec \(i_1 < i_2 < i_3\). (Le livret le montre sur une disposition « naturelle » des points, représentée ci-dessous, et indique qu'on le vérifie facilement pour toute autre disposition.) De même,

\[\angle P_{i_1}Q_kP_{i_3} = \angle P_{i_1}Q_kP_{i_2} + \angle P_{i_2}Q_kP_{i_3} \tag{2}\]

pour tous \(Q_k\), \(P_{i_1}\), \(P_{i_2}\), \(P_{i_3}\) avec \(i_1 < i_2 < i_3\).

On définit maintenant l'ordre \(A_1, \ldots, A_{2n}\) :

• si \(i \leq n\) est impair, \(A_i = P_i\) et \(A_{2n+1-i} = Q_i\) ;
• si \(i \leq n\) est pair, \(A_i = Q_i\) et \(A_{2n+1-i} = P_i\).

Par exemple, pour \(n = 3\), l'ordre est \(P_1, Q_2, P_3, Q_3, P_2, Q_1\). Cette suite alterne entre \(P\) et \(Q\), donc les conventions ci-dessus donnent un signe à chaque angle \(\angle A_{i-1}A_iA_{i+1}\). Affirmation : la somme de ces \(2n\) angles signés est nulle, ce qui conclut. On note \(\angle P_i\) l'angle de sommet \(P_i\) parmi les \(2n\) angles, et de même \(\angle Q_i\).

Cas \(n = 2\). L'ordre est \(P_1, Q_2, P_2, Q_1\). Si les quatre points forment un quadrilatère convexe, les quatre segments \(P_1Q_1\), \(P_1Q_2\), \(P_2Q_1\), \(P_2Q_2\) forment un quadrilatère croisé. Dans la disposition de la première figure ci-dessous, \(\angle P_1\) et \(\angle Q_1\) sont positifs, \(\angle P_2\) et \(\angle Q_2\) négatifs, et \(|\angle P_1| + |\angle Q_1| = |\angle P_2| + |\angle Q_2|\) ; en mesures signées,

\[\angle P_1 + \angle Q_1 + \angle P_2 + \angle Q_2 = 0. \tag{3}\]

Échanger les noms de \(P_1\) et \(P_2\) change le signe des quatre angles (en échangeant les mesures des points renommés) : les nouvelles valeurs de \((\angle P_1, \angle P_2, \angle Q_1, \angle Q_2)\) sont les anciennes valeurs de \((-\angle P_2, -\angle P_1, -\angle Q_1, -\angle Q_2)\), donc \((3)\) reste vraie. De même en échangeant \(Q_1\) et \(Q_2\), ou les deux paires.

Le dernier sous-cas est celui où un point est à l'intérieur du triangle formé par les trois autres. Dans la disposition de la figure ci-dessous, \(|\angle P_1| + |\angle Q_1| + |\angle Q_2| = |\angle P_2|\) et \((3)\) est vraie. À nouveau, échanger les noms des \(P\) ou des \(Q\) ne change pas la validité de \((3)\). Si le point intérieur est un \(Q\) plutôt qu'un \(P\), le résultat tient encore, car la convention de signe est préservée en échangeant les rôles des \(P\) et des \(Q\) et en faisant une symétrie par rapport à \(\ell\). Le cas \(n = 2\) est démontré.

Hérédité. Supposons l'affirmation vraie pour \(n = k\) et prenons \(2(k+1)\) points. Oublions d'abord \(P_{k+1}\) et \(Q_{k+1}\) et formons les \(2k\) angles à partir de \(P_1, \ldots, P_k, Q_1, \ldots, Q_k\) comme pour \(n = k\). Par hypothèse de récurrence,

\[\sum_{i=1}^k (\angle P_i + \angle Q_i) = 0.\]

L'ajout de \(P_{k+1}\) et \(Q_{k+1}\) modifie les angles ainsi (dans l'ordre, \(P_{k+1}\) et \(Q_{k+1}\) viennent s'insérer entre \(P_k\) et \(Q_k\), qui étaient consécutifs) :

• l'angle en \(P_k\) passe de \(\angle Q_{k-1}P_kQ_k\) à \(\angle Q_{k-1}P_kQ_{k+1}\) ;
• l'angle en \(Q_k\) passe de \(\angle P_{k-1}Q_kP_k\) à \(\angle P_{k-1}Q_kP_{k+1}\) ;
• deux nouveaux angles \(\angle Q_kP_{k+1}Q_{k+1}\) et \(\angle P_kQ_{k+1}P_{k+1}\) apparaissent.

Il faut montrer que ces changements ne modifient pas la somme, c'est-à-dire

\[\big(\angle Q_{k-1}P_kQ_{k+1} - \angle Q_{k-1}P_kQ_k\big) + \big(\angle P_{k-1}Q_kP_{k+1} - \angle P_{k-1}Q_kP_k\big) + \big(\angle P_{k+1} + \angle Q_{k+1}\big) = 0. \tag{4}\]

D'après \((1)\) et \((2)\),

\[\angle Q_{k-1}P_kQ_{k+1} - \angle Q_{k-1}P_kQ_k = \angle Q_kP_kQ_{k+1}, \qquad \angle P_{k-1}Q_kP_{k+1} - \angle P_{k-1}Q_kP_k = \angle P_kQ_kP_{k+1}.\]

Le membre de gauche de \((4)\) devient donc

\[\angle Q_kP_kQ_{k+1} + \angle P_kQ_kP_{k+1} + \angle Q_kP_{k+1}Q_{k+1} + \angle P_kQ_{k+1}P_{k+1},\]

qui est nul d'après le cas \(n = 2\) appliqué aux quatre points \(P_k, P_{k+1}, Q_k, Q_{k+1}\). Ceci achève la récurrence. \(\blacksquare\)

Solution 4

On voit le problème comme l'attribution d'un poids \(\pm 1\) à chaque angle, de sorte que la somme pondérée des angles soit nulle.

Pour un ordre \(A_1, \ldots, A_{2n}\) des points, on attribue les poids ainsi : on parcourt les points dans l'ordre, et on donne le poids \(+1\) aux virages à gauche et \(-1\) aux virages à droite. Comme dans la solution 2, la somme pondérée est un multiple de \(360^\circ\). (Le livret renvoie ici à la solution 3 ; c'est la pondération et le calcul de la solution 2.)

Lemme. Transposer deux points consécutifs dans l'ordre change la somme pondérée de \(\pm 360^\circ\) ou de \(0\).

Conclusion à partir du lemme : si l'ordre \(A_1, \ldots, A_{2n}\) a une somme pondérée \(360k^\circ\), alors l'ordre \(A_{2n}, \ldots, A_1\) a une somme pondérée \(-360k^\circ\) (les angles sont les mêmes, mais virages à gauche et à droite sont échangés). On peut renverser l'ordre par une suite de transpositions de points consécutifs ; comme la somme ne varie que par pas de \(0\) ou \(\pm 360^\circ\) et passe de \(360k^\circ\) à \(-360k^\circ\), elle s'annule à un moment.

Preuve du lemme. Transposer deux points revient à prendre une portion \(A_kA_{k+1}A_{k+2}A_{k+3}\), à renverser le segment central \(A_{k+1}A_{k+2}\) et à remplacer ses deux voisins par les segments \(A_kA_{k+2}\) et \(A_{k+1}A_{k+3}\). Pour chacun des deux triangles \(A_kA_{k+1}A_{k+2}\) et \(A_{k+1}A_{k+2}A_{k+3}\), la somme change de \(\pm 180^\circ\) : en utilisant des angles orientés (sens direct) modulo \(360^\circ\), on ajoute ou on retranche les trois angles du triangle. Les deux triangles ensemble changent donc la somme de \(\pm 180^\circ \pm 180^\circ\), soit \(\pm 360^\circ\) ou \(0\). \(\square\) \(\blacksquare\)

Remarques

Remarque 1. Les trois premières solutions utilisent la même construction (une droite séparant les points en deux groupes de \(n\)) mais prouvent différemment qu'elle convient. Bien que la solution 1 soit très courte, le comité de sélection estime qu'aucune des solutions n'est facile à trouver, et classe ce problème comme de difficulté moyenne.

Remarque 2 (sur la solution 2). Des variantes plus compliquées de cette solution sont possibles, par exemple avec un chemin défini à l'aide de quatre quadrants du plan au lieu de deux demi-plans.