Shortlist 2014, C9

Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : India

Concepts : Invariants et monovariants · Graphes : degrés, chemins, arbres · Double comptage

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 44 (page 45 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 \(n\) circles drawn on a piece of paper in such a way that any two circles intersect in two points, and no three circles pass through the same point. Turbo the snail slides along the circles in the following fashion. Initially he moves on one of the circles in clockwise direction. Turbo always keeps sliding along the current circle until he reaches an intersection with another circle. Then he continues his journey on this new circle and also changes the direction of moving, i.e. from clockwise to anticlockwise or vice versa.

Suppose that Turbo's path entirely covers all circles. Prove that \(n\) must be odd.

Indices : les idées clés

• Orbites : à chaque croisement, on remplace la croix par deux petits arcs ; les trajets possibles de l'escargot forment des courbes fermées simples disjointes. On montre plus généralement que le nombre d'orbites a la parité de \(n\).
• Invariant de parité : « retourner » un croisement change le nombre d'orbites de \(\pm 1\) ; le nombre de croisements est pair, puis la courbure totale, comptée de deux façons (double comptage), donne \(P - N = n\) (solution 1).
• Graphes (solution 3) : avec la formule d'Euler, \(\lvert R_{\text{impair}} \rvert - \lvert P_{\text{impair}} \rvert \equiv n \pmod 2\) ; s'il n'y a qu'une orbite, les régions impaires et les points impairs forment un arbre, d'où une différence égale à \(1\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2014 (trois solutions et une remarque).

Solution 1

Remplaçons chaque croisement (intersection de deux cercles) par deux petits arcs qui indiquent dans quelle direction l'escargot quitte le croisement (voir la figure 1.1). Le placement de ces petits arcs ne dépend pas du sens de parcours : quel que soit le sens dans lequel l'escargot se déplace, il suit les mêmes courbes (figure 1.2). On obtient ainsi un ensemble de courbes, qui sont les trajets possibles de l'escargot ; on les appelle orbites. Chaque orbite est une courbe fermée simple qui ne rencontre aucune autre orbite.

On prouve l'énoncé plus général suivant.

\((\ast)\) Dans toute configuration de \(n\) cercles dont deux ne sont jamais tangents, le nombre d'orbites a la même parité que \(n\). (On ne suppose pas que deux cercles quelconques se coupent.)

Cela résout immédiatement le problème.

Introduisons l'opération suivante, appelée retourner un croisement : en un croisement, on retire les deux petits arcs et on les remplace par les deux autres. Quand l'escargot arrive à un croisement retourné, il continue sur l'autre cercle comme avant, mais il conserve le sens dans lequel il parcourt les arcs (figure 2).

Voyons ce que devient le nombre d'orbites quand on retourne un croisement. Notons \(a\), \(b\), \(c\), \(d\) les quatre arcs qui se rencontrent au croisement, \(a\) et \(b\) étant sur le même cercle. Avant le retournement, \(a\) et \(b\) étaient reliés respectivement à \(c\) et \(d\) ; après, ils sont reliés respectivement à \(d\) et \(c\).

Les orbites qui passent par le croisement sont des courbes fermées, donc chacun des arcs \(a\), \(b\), \(c\), \(d\) est relié à un autre par les orbites en dehors du croisement. On distingue trois cas.

Cas 1 : à l'extérieur du croisement, \(a\) est relié à \(b\) et \(c\) à \(d\) (figure 3.1). Ce cas est impossible. Retirons les deux petits arcs du croisement, et relions \(a\) à \(b\) et \(c\) à \(d\) au croisement. Soit \(\gamma\) la nouvelle courbe fermée qui contient \(a\) et \(b\), et \(\delta\) celle qui relie \(c\) et \(d\). Ces deux courbes se croisent au croisement, donc l'un des arcs \(c\), \(d\) est à l'intérieur de \(\gamma\) et l'autre à l'extérieur. Les deux courbes fermées doivent alors se rencontrer au moins une autre fois, ce qui est absurde puisqu'aucune orbite ne se recoupe.

Cas 2 : \(a\) est relié à \(c\) et \(b\) à \(d\) (figure 3.2). Avant le retournement, \(a\) et \(c\) sont sur une orbite, \(b\) et \(d\) sur une autre. Le retournement fusionne ces deux orbites : leur nombre diminue de \(1\).

Cas 3 : \(a\) est relié à \(d\) et \(b\) à \(c\) (figure 3.3). Avant le retournement, \(a\), \(b\), \(c\), \(d\) sont sur une même orbite. Le retournement la coupe en deux : le nombre d'orbites augmente de \(1\).

Ainsi, chaque retournement change le nombre d'orbites de \(\pm 1\), donc change sa parité.

Retournons maintenant tous les croisements, un par un. Deux cercles ont \(0\) ou \(2\) points d'intersection, donc le nombre de croisements est pair. Quand tous les croisements ont été retournés, la parité de départ du nombre d'orbites est donc rétablie. Il suffit de prouver \((\ast)\) pour la nouvelle configuration, où tous les croisements sont retournés. Dans cette nouvelle configuration aussi, les orbites (modifiées) sont des courbes fermées simples qui ne se rencontrent pas.

Orientons les orbites de sorte que l'escargot parcoure toujours les arcs de cercle dans le sens inverse des aiguilles d'une montre. La figure 4 montre les cercles de la figure 1 après retournement de tous les croisements et orientation. (Cette orientation peut différer de l'orientation de l'orbite en tant que courbe plane : une orbite peut être orientée positivement ou négativement, comme l'orbite du milieu de la figure 4.) Quand l'escargot fait le tour d'une orbite, la variation totale de sa direction, la courbure totale, vaut \(+2\pi\) ou \(-2\pi\) selon l'orientation de l'orbite. Soient \(P\) et \(N\) les nombres d'orbites orientées positivement et négativement. La courbure totale de toutes les orbites vaut alors \((P - N) \cdot 2\pi\).

Comptons cette courbure totale d'une autre façon. Le long de chaque cercle, la courbure totale vaut \(2\pi\). En chaque croisement, les deux virages font deux changements de direction d'angles de même valeur absolue et de signes opposés (figure 5) ; ils se compensent. La courbure totale vaut donc \(n \cdot 2\pi\).

On a donc \((P - N) \cdot 2\pi = n \cdot 2\pi\), soit \(P - N = n\). Le nombre d'orbites (modifiées) est \(P + N\), qui a la même parité que \(P - N = n\). \(\blacksquare\)

Solution 2

On donne une autre preuve de \((\ast)\).

On effectue une suite de petites modifications de la configuration des cercles, de sorte qu'à la fin ils ne se coupent plus du tout (figure 6.1). On utilise deux types de changements locaux de la structure des orbites (figure 6.2) :

• étape de type 1 : un arc d'un cercle passe par-dessus un arc d'un autre cercle ; une telle étape crée ou supprime deux points d'intersection ;
• étape de type 2 : un arc d'un cercle passe par le point d'intersection de deux autres cercles.

On suppose qu'à chaque étape un seul cercle bouge, et qu'il passe par-dessus au plus un arc ou un point d'intersection des autres cercles.

On va montrer que la parité du nombre d'orbites ne change à aucune étape. Comme à la fin chaque cercle est une orbite à lui seul, cela prouve \((\ast)\).

Considérons une étape de type 1. Les deux points d'intersection sont créés ou supprimés dans un petit voisinage. Notons \(a\), \(b\), \(c\), \(d\), dans cet ordre autour du voisinage, des points des deux cercles où ils entrent dans ce voisinage ou en sortent ; \(a\) et \(b\) sont sur un cercle, \(c\) et \(d\) sur l'autre. Les deux arcs peuvent avoir la même orientation ou des orientations opposées. De plus, les quatre extrémités des deux arcs sont reliées par le reste des orbites, et cela ne peut se faire sans croisement que de deux façons : soit \(a\) est relié à \(d\) et \(b\) à \(c\), soit \(a\) est relié à \(b\) et \(c\) à \(d\). Il y a donc quatre cas, représentés sur la figure 7.

Le nombre d'orbites change de \(-2\) ou \(+2\) dans le cas de gauche, où les arcs ont la même orientation, \(a\) est relié à \(d\) et \(b\) à \(c\). Dans les trois autres cas, le nombre d'orbites ne change pas. Les étapes de type 1 ne changent donc pas la parité du nombre d'orbites.

Considérons maintenant une étape de type 2. Les trois cercles délimitent une petite région triangulaire ; l'étape la remplace par un autre triangle. Là encore, les orbites ne sont modifiées que dans un petit voisinage. Chaque côté de la région triangulaire peut être convexe ou concave ; le nombre de côtés concaves vaut \(0\), \(1\), \(2\) ou \(3\), d'où quatre dispositions possibles des orbites dans le voisinage (figure 8).

Notons \(a\), \(b\), \(c\), \(d\), \(e\), \(f\), dans cet ordre autour du voisinage, les points où les trois cercles entrent dans le voisinage ou en sortent. Comme on le voit sur la figure 8, il n'y a que deux cas essentiellement différents : soit \(a\), \(c\), \(e\) sont reliés respectivement à \(b\), \(d\), \(f\), soit \(a\), \(c\), \(e\) sont reliés respectivement à \(f\), \(b\), \(d\). L'étape conserve l'ensemble des liaisons ou passe à l'autre disposition. Dans le premier cas, le nombre d'orbites ne change évidemment pas ; il ne reste à considérer que le second.

Les points \(a\), \(b\), \(c\), \(d\), \(e\), \(f\) sont reliés par les orbites à l'extérieur, sans croisement. Si \(a\) était relié à \(c\), par exemple, cette orbite isolerait \(b\), ce qui est impossible. Chacun des points est donc relié soit à l'un de ses voisins, soit au point opposé. Si par exemple \(a\) est relié à \(d\), cette orbite sépare \(b\) et \(c\) de \(e\) et \(f\), donc \(b\) est relié à \(c\) et \(e\) à \(f\). Au total, il n'y a que deux cas (et leurs symétriques) : soit chaque point est relié à l'un de ses voisins, soit deux points opposés sont reliés et les autres paires de voisins sont reliées entre elles (figure 9).

Si seuls des points voisins sont reliés, le nombre d'orbites change de \(+2\) ou \(-2\). Si deux points opposés sont reliés (\(a\) et \(d\) sur la figure), les orbites sont réarrangées mais leur nombre ne change pas. Les étapes de type 2 conservent donc aussi la parité. Cela achève la preuve de \((\ast)\). \(\blacksquare\)

Solution 3

Comme dans les solutions précédentes, on n'a pas besoin que deux cercles quelconques se coupent, mais on suppose que la réunion des cercles est connexe. Notons \(\mathcal{C}\) l'ensemble des cercles et \(\mathcal{P}\) celui de leurs points d'intersection.

Les cercles découpent le plan en plusieurs régions bornées simplement connexes et une région non bornée ; notons \(\mathcal{R}\) l'ensemble de ces régions. Un point d'intersection ou une région est dit impair ou pair s'il est contenu à l'intérieur d'un nombre impair ou pair de cercles. Soient \(\mathcal{P}_{\text{imp}}\) et \(\mathcal{R}_{\text{imp}}\) les ensembles des points d'intersection impairs et des régions impaires.

Affirmation.

\[\lvert \mathcal{R}_{\text{imp}} \rvert - \lvert \mathcal{P}_{\text{imp}} \rvert \equiv n \pmod 2. \tag{1}\]

Preuve. Pour chaque cercle \(c \in \mathcal{C}\), notons \(R_c\), \(P_c\) et \(X_c\) respectivement le nombre de régions à l'intérieur de \(c\), le nombre de points d'intersection à l'intérieur de \(c\), et le nombre de cercles qui coupent \(c\). Les cercles se découpent mutuellement en arcs ; notons \(A_c\) le nombre de ces arcs situés à l'intérieur de \(c\). En comptant de deux façons les régions et les points d'intersection intérieurs aux cercles, on obtient

\[\lvert \mathcal{R}_{\text{imp}} \rvert \equiv \sum_{c \in \mathcal{C}} R_c \pmod 2 \quad \text{et} \quad \lvert \mathcal{P}_{\text{imp}} \rvert \equiv \sum_{c \in \mathcal{C}} P_c \pmod 2.\]

Pour chaque cercle \(c\), appliquons la formule d'Euler aux régions (simplement connexes) intérieures à \(c\). Il y a \(2X_c\) points d'intersection sur \(c\), qui le découpent en \(2X_c\) arcs. En comptant l'extérieur de \(c\) comme une seule région, la formule d'Euler donne \((R_c + 1) + (P_c + 2X_c) = (A_c + 2X_c) + 2\), donc

\[R_c + P_c = A_c + 1. \tag{2}\]

De plus, quatre arcs partent de chaque point d'intersection intérieur à \(c\), et un seul arc part vers l'intérieur depuis chaque point d'intersection situé sur \(c\). En comptant de deux façons les extrémités des arcs intérieurs, on obtient \(2A_c = 4P_c + 2X_c\), donc

\[A_c = 2P_c + X_c. \tag{3}\]

Les relations (2) et (3) donnent

\[R_c - P_c = X_c + 1. \tag{4}\]

En sommant (4) sur tous les cercles,

\[\sum_{c \in \mathcal{C}} R_c - \sum_{c \in \mathcal{C}} P_c = \sum_{c \in \mathcal{C}} X_c + \lvert \mathcal{C} \rvert,\]

d'où

\[\lvert \mathcal{R}_{\text{imp}} \rvert - \lvert \mathcal{P}_{\text{imp}} \rvert \equiv \sum_{c \in \mathcal{C}} X_c + n \pmod 2. \tag{5}\]

Dans \(\sum_{c} X_c\), chaque paire de cercles sécants est comptée deux fois (une fois pour chacun des deux cercles), donc \(\sum_{c} X_c \equiv 0 \pmod 2\), ce qui prouve l'affirmation. \(\square\)

Insérons maintenant les petits arcs aux croisements comme dans la première solution, et supposons qu'il n'y ait qu'une seule orbite \(b\).

Montrons d'abord que les régions impaires sont à l'intérieur de la courbe \(b\) et les régions paires à l'extérieur. Prenons une région \(r \in \mathcal{R}\) et un point \(x\) intérieur à \(r\), et traçons une demi-droite \(y\) issue de \(x\) qui ne passe par aucun point d'intersection des cercles et n'est tangente à aucun cercle. On sait que \(x\) est à l'intérieur de \(b\) si et seulement si \(y\) coupe \(b\) un nombre impair de fois (figure 10). Si un cercle \(c\) contient \(x\) en son intérieur, il coupe \(y\) en un seul point ; sinon, il coupe \(y\) en \(2\) ou \(0\) points. Donc \(y\) coupe \(b\) un nombre impair de fois si et seulement si \(x\) est contenu dans un nombre impair de cercles, c'est-à-dire si et seulement si \(r\) est impaire.

Considérons maintenant un point d'intersection \(p\) de deux cercles \(c_1\) et \(c_2\), et un petit voisinage de \(p\). Supposons \(p\) contenu dans \(k\) cercles. Quatre régions se rencontrent en \(p\). Soit \(r_1\) la région extérieure à \(c_1\) et à \(c_2\), \(r_2\) la région intérieure à \(c_1\) et à \(c_2\), et \(r_3\), \(r_4\) les deux autres, chacune intérieure à exactement un des cercles \(c_1\), \(c_2\). La région \(r_1\) est contenue dans les mêmes \(k\) cercles que \(p\) ; la région \(r_2\) est contenue aussi dans \(c_1\) et \(c_2\), donc dans \(k + 2\) cercles ; chacune des régions \(r_3\) et \(r_4\) est contenue dans \(k + 1\) cercles. Une fois les petits arcs insérés en \(p\), les régions \(r_1\) et \(r_2\) sont reliées, et les régions \(r_3\) et \(r_4\) restent séparées en \(p\) (figure 11). Si \(p\) est un point impair, \(r_1\) et \(r_2\) sont impaires : deux régions impaires sont reliées en \(p\). Si \(p\) est pair, ce sont deux régions paires qui sont reliées en \(p\).

Considérons les régions impaires et leurs liaisons aux points impairs comme un graphe : les régions impaires sont les sommets, et chaque point impair donne une arête reliant deux sommets (figure 12). Comme \(b\) est une seule courbe fermée, ce graphe est connexe et sans cycle : c'est un arbre. Le nombre de sommets dépasse donc de \(1\) le nombre d'arêtes :

\[\lvert \mathcal{R}_{\text{imp}} \rvert - \lvert \mathcal{P}_{\text{imp}} \rvert = 1. \tag{6}\]

Les relations (1) et (6) montrent ensemble que \(n\) est impair. \(\blacksquare\)

Remarque

Pour tout \(n\) impair, il existe au moins une configuration de \(n\) cercles avec une seule orbite. La figure 13 en montre une avec \(5\) cercles. En général, si l'on fait tourner un cercle d'angles \(k \cdot \frac{360^\circ}{n}\) (\(k = 1, 2, \ldots, n - 1\)) autour d'un point intérieur autre que son centre, le cercle et ses images forment ensemble une seule orbite.