Shortlist 2017, G8¶
Domaine : Géométrie · Difficulté : ★★★★★ · Proposé par : Australia
Concepts : Invariants et monovariants · Graphes : degrés, chemins, arbres · Double comptage
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 70 (page 72 du PDF)
Figures reprises du livret officiel de la Shortlist.
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
There are \(2017\) mutually external circles drawn on a blackboard, such that no two are tangent and no three share a common tangent. A tangent segment is a line segment that is a common tangent to two circles, starting at one tangent point and ending at the other one. Luciano is drawing tangent segments on the blackboard, one at a time, so that no tangent segment intersects any other circles or previously drawn tangent segments. Luciano keeps drawing tangent segments until no more can be drawn. Find all possible numbers of tangent segments when he stops drawing.
Indices : les idées clés
- Réponse : avec \(n\) cercles, Luciano trace toujours exactement \(3(n-1)\) segments, soit \(3 \cdot 2017 - 3 = 6048\).
- Invariants et monovariants (solution 1) : on déforme continûment la configuration ; le nombre de segments d'une configuration maximale ne change pas lors des « transitions », ce qui ramène au cas de cercles alignés.
- Graphes : degrés, chemins, arbres (solution 2) : cercles = sommets, segments = arêtes d'un graphe planaire ; la formule d'Euler conclut.
- Double comptage (solution 2) : on compte les « coins pointus » par segment (2 chacun) et par région (3 chacune), d'où \(2s = 3r\).
- Suivre la rotation le long d'un bord (solution 2) : en parcourant le bord d'une région, on tourne de \(2\pi\) au total, ce qui force au moins 3 coins pointus.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions).
Réponse : \(6048\) (avec \(n\) cercles, toujours exactement \(3(n-1)\) segments).
Solution 1¶
Un cas particulier. Considérons des cercles \(C_1, C_2, \ldots, C_n\) dont les centres sont alignés et où chaque \(C_i\) est masqué des autres cercles par ses voisins : par exemple, \(C_i\) de centre \((i^2, 0)\) et de rayon \(i/2\). Les seuls segments tangents qu'on peut tracer relient alors deux cercles voisins \(C_i\) et \(C_{i+1}\), et on peut en tracer exactement trois pour chaque paire (voir la figure). Luciano trace donc exactement \(3(n-1)\) segments dans ce cas.
Idée générale. Partons d'une configuration finale quelconque (cercles et segments, sans segment supplémentaire possible). On va déplacer et redimensionner continûment les cercles, un par un (en veillant à ne jamais avoir 4 cercles avec une tangente commune), et montrer que le nombre de segments d'une configuration maximale reste invariant au cours de la déformation. On peut ainsi ramener toute configuration au cas particulier ci-dessus, et le nombre final de segments vaut toujours \(3n - 3\).
Préliminaires. Un segment tangent à un cercle \(A\) peut l'être dans deux orientations : il « sort » de \(A\) dans le sens horaire ou dans le sens trigonométrique. Deux segments touchant le même cercle avec la même orientation ne se coupent jamais. Chaque paire \((A, B)\) de cercles a 4 segments tangents possibles, que l'on identifie par leurs orientations ; par exemple \((A^+, B^-)\) sort de \(A\) dans le sens horaire et de \(B\) dans le sens trigonométrique. Au total, il y a \(2n(n-1)\) segments possibles, sans tenir compte des intersections.
Choisissons un cercle \(C\) et déplaçons-le et redimensionnons-le continûment, en conservant tous les segments existants selon leurs identifications (y compris ceux qui touchent \(C\)). On peut garder ce choix de segments jusqu'à ce que la configuration atteigne une transition. On peut supposer sans perte de généralité que \(C\) reste à distance au moins \(\varepsilon\) des autres cercles, pour un \(\varepsilon > 0\) fixé. À une transition, soit (1) un segment tracé \(t\) devient soudain obstrué, soit (2) un segment absent \(t\) devient soudain dégagé et disponible.
Affirmation. Une transition ne peut se produire que lorsque trois cercles \(C_1, C_2, C_3\) sont tangents à une même droite \(\ell\) contenant \(t\), de sorte que les trois segments tangents portés par \(\ell\) (reliant deux à deux les trois cercles) ne sont obstrués par aucun autre cercle ni segment (autre que \(C_1, C_2, C_3\)).
Preuve. Comme (2) est l'inverse de (1), il suffit de traiter (1). Supposons que \(t\) devienne soudain obstrué.
Cas 1 : \(t\) est obstrué par un cercle. Ce nouveau cercle devient le troisième cercle tangent à \(\ell\), et aucun autre cercle ni segment n'obstrue \(t\) (voir la figure).
Cas 2 : \(t\) est obstrué par un autre segment \(t'\). Quand deux segments \(t\) et \(t'\) se coupent pour la première fois, c'est forcément en une extrémité de l'un d'eux. Mais si une extrémité de \(t'\) traversait d'abord un point intérieur de \(t\), le cercle associé à cette extrémité bloquait déjà \(t\) (absurde), ou est sur le point de le faire (c'est le cas 1). Il reste donc la possibilité que \(t\) et \(t'\) acquièrent soudain une extrémité commune. Cette extrémité appartient alors à un seul cercle (les cercles restent à distance au moins \(\varepsilon\) les uns des autres), donc \(t\) et \(t'\) ont des orientations différentes par rapport à ce cercle. Ainsi, au moment de la transition, \(t\) et \(t'\) sont tangents au même cercle au même point : ils sont sur une même droite \(\ell\), et on a de nouveau trois cercles tangents simultanément à \(\ell\). De plus, aucun autre cercle ou segment n'obstrue \(t\) ou \(t'\) (sinon ils auraient disparu avant cette transition). \(\square\)
Maximalité avant et après une transition. Soient \(C_1, C_2, C_3\) les trois cercles tangents à \(\ell\), rangés dans l'ordre de leurs points de contact. Les seuls segments éventuellement affectés sont ceux portés par \(\ell\) : \(t_{12}\), \(t_{23}\) et \(t_{13}\). Comme \(C_2\) est au milieu, \(t_{12}\) et \(t_{23}\) ont des orientations différentes par rapport à \(C_2\). Pour \(C_1\), \(t_{12}\) et \(t_{13}\) ont la même orientation ; pour \(C_3\), \(t_{13}\) et \(t_{23}\) ont la même orientation (voir la figure, qui montre les positions possibles \(C_1, C_1'\) et \(C_3, C_3'\)).
Perturbons légèrement la figure pour que les trois cercles n'aient plus de tangente commune, en gardant les identifications de \(t_{12}\), \(t_{23}\), \(t_{13}\). Aucun autre cercle ni segment ne peut obstruer ces segments, et deux segments touchant le même cercle avec la même orientation ne s'obstruent jamais. On vérifie alors sur des figures simples :
- Cas 1 : \(t_{13}\) traverse \(C_2\). Alors \(t_{13}\) n'est pas disponible, mais \(t_{12}\) et \(t_{23}\) le sont tous les deux.
- Cas 2 : \(t_{13}\) ne traverse pas \(C_2\). Alors \(t_{13}\) est disponible, mais \(t_{12}\) et \(t_{23}\) se coupent, donc un seul des deux peut être tracé.
Dans tous les cas, exactement 2 de ces 3 segments peuvent être tracés. Le nombre de segments d'une configuration maximale reste donc constant quand on déplace ou redimensionne les cercles, ce qui conclut. \(\blacksquare\)
Solution 2¶
Remarquons d'abord que tous les segments tangents situés sur le bord de l'enveloppe convexe des cercles sont toujours tracés, car ils ne coupent rien d'autre. Dans la figure finale, en dehors des \(n\) cercles, le tableau est découpé en régions. On voit la figure comme un graphe planaire (éventuellement avec arêtes multiples) \(G\) : les cercles sont les sommets, les segments tangents les arêtes. L'idée est de relier le nombre d'arêtes au nombre de régions, puis, \(G\) étant connexe, d'utiliser la formule d'Euler.
Le bord de chaque région est formé (pour l'instant) d'une ou plusieurs courbes fermées simples, faites d'arcs de cercle et de segments tangents. Un segment et un arc peuvent se raccorder de façon lisse, ou non : on appelle coins pointus ces derniers points. En marchant le long du bord, on fait brusquement demi-tour (angle \(\pi\)) en un coin pointu (voir la figure).
Affirmation 1. Le bord extérieur \(B_1\) de toute région intérieure a au moins 3 coins pointus.
Preuve. Une personne fait un tour de \(B_1\) dans le sens trigonométrique. Le long des arcs de cercle, elle tourne dans le sens horaire ; le long des segments, elle ne tourne pas. Pourtant, sa rotation totale après un tour vaut \(2\pi\) dans le sens trigonométrique. Elle ne peut tourner dans le sens trigonométrique qu'aux coins pointus, et seulement d'un angle \(\pi\) à chaque fois. Deux coins pointus ne suffisent pas, puisqu'il y a au moins un arc : il y a donc au moins 3 coins pointus. \(\square\)
Affirmation 2. Chaque région intérieure est simplement connexe, c'est-à-dire n'a qu'une seule courbe de bord.
Preuve. Par l'absurde, supposons qu'une région ait un bord extérieur \(B_1\) et des bords intérieurs \(B_2, \ldots, B_m\) (\(m \geq 2\)). Soit \(P_1\) un coin pointu de \(B_1\).
Considérons une voiture partant de \(P_1\) et parcourant \(B_1\) dans le sens trigonométrique. Elle part en marche arrière, c'est-à-dire face au coin \(P_1\). Grâce aux conditions de tangence, la voiture peut rouler de sorte que son orientation ne change que lorsqu'elle parcourt un arc ; en particulier, elle roulera parfois en marche avant (par exemple, arrivant en marche arrière à un coin pointu, elle repart en marche avant au lieu de faire demi-tour). Ainsi, l'orientation de la voiture ne tourne que dans le sens horaire, puisque la voiture tourne dans le sens horaire autour de chaque arc.
Fixons un pointeur laser à l'avant de la voiture, pointant droit devant. Au départ, le point visé est \(P_1\) ; dès que la voiture aborde un arc, le point visé se déplace dans le sens horaire le long de \(B_1\). En fait, ce point se déplace continûment le long de \(B_1\) : s'il sautait (le long de \(B_1\), ou de \(B_1\) vers un bord intérieur), alors au moment du saut le rayon laser interrompu serait un segment tangent traçable que Luciano aurait oublié (voir la figure).
Soient \(P_2\) et \(P_3\) les deux coins pointus suivants rencontrés par la voiture après \(P_1\) (ils existent par l'affirmation 1). En \(P_2\) la voiture passe en marche avant, et en \(P_3\) elle repasse en marche arrière ; en \(P_3\), le point visé est donc \(P_3\) lui-même. Pendant que la voiture va de \(P_1\) à \(P_3\) dans le sens trigonométrique, le point visé va de \(P_1\) à \(P_3\) dans le sens horaire. Le rayon laser a donc balayé toute la région intérieure à \(B_1\), et il aurait dû croiser un des bords intérieurs : contradiction. \(\square\)
Affirmation 3. Chaque région a exactement 3 coins pointus.
Preuve. Reprenons la voiture et son laser, passant par les coins pointus consécutifs \(P_1, P_2, P_3\). Quand la voiture va de \(P_1\) à \(P_3\) dans le sens trigonométrique, le point visé va de \(P_1\) à \(P_3\) dans le sens horaire, de sorte qu'à eux deux ils couvrent tout le bord. S'il y avait un quatrième coin pointu \(P_4\), le point visé passerait par \(P_4\) à un certain moment. Comme \(P_4\) est un coin pointu, la voiture serait alors sur le prolongement d'un segment tangent passant par \(P_4\) ; comme elle n'est pas sur ce segment lui-même (elle ne passe jamais par \(P_4\)), on aurait 3 cercles ayant une tangente commune, ce qui est exclu. \(\square\)
Conclusion. Soient \(r\) le nombre de régions intérieures et \(s\) le nombre de segments tangents. Par double comptage des coins pointus : chaque segment fournit exactement 2 coins pointus et chaque région en a exactement 3, donc \(2s = 3r\). Le graphe associé à la figure étant connexe, la formule d'Euler donne \(n - s + r = 1\), d'où
Pour \(n = 2017\), on obtient \(s = 6048\). \(\blacksquare\)