Shortlist 2018, C7¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : India
Concepts : Graphes : degrés, chemins, arbres · Double comptage · Coloriages et pavages
Solution officielle : Shortlist officielle 2018 (avec solutions), p. 34 (page 36 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Consider \(2018\) pairwise crossing circles no three of which are concurrent. These circles subdivide the plane into regions bounded by circular edges that meet at vertices. Notice that there are an even number of vertices on each circle. Given the circle, alternately colour the vertices on that circle red and blue. In doing so for each circle, every vertex is coloured twice, once for each of the two circles that cross at that point. If the two colourings agree at a vertex, then it is assigned that colour; otherwise, it becomes yellow. Show that, if some circle contains at least \(2061\) yellow points, then the vertices of some region are all yellow.
Indices : les idées clés
- Arguments de parité : les deux points d'intersection de deux cercles sont tous deux jaunes ou tous deux non jaunes ; un « triangle » d'arcs de trois cercles a un nombre impair de sommets jaunes.
- Graphes : formule d'Euler et degrés ; le graphe des cercles a \(n(n-1)\) sommets de degré \(4\) et \(n(n-1) + 2\) faces (solution 1) ; un graphe à \(t\) sommets et plus de \(t - 1\) arêtes contient un cycle (solution 2).
- Double comptage des incidences sommet–face (solution 1) : si chaque face a au moins deux sommets non jaunes, il y a au plus \(n(n-1)/2 - 1\) sommets jaunes.
- Coloriages (solution 2) : on colorie les cercles en blanc et noir de sorte que deux cercles se coupent en des points jaunes si et seulement s'ils ont la même couleur.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions).
Solution 1¶
Posons \(n = 2018\). Nous allons montrer que si chaque région a au moins un sommet non jaune, alors chaque cercle contient au plus \(n + \lfloor \sqrt{n-2} \rfloor - 2\) points jaunes. Ici, cette quantité vaut \(2018 + 44 - 2 = 2060\), ce qui contredit l'hypothèse.
Considérons le graphe plan naturel \(G\) associé à la configuration des \(n\) cercles. Fixons un cercle \(C\), notons \(k\) le nombre de points jaunes sur \(C\), et cherchons une minoration du nombre total de sommets jaunes de \(G\) en fonction de \(k\) et \(n\). Il se trouve que \(k\) est pair et que \(G\) a au moins
sommets jaunes. La preuve repose sur les deux lemmes suivants.
Lemme 1. Si deux cercles de la configuration se coupent en \(x\) et \(y\), alors \(x\) et \(y\) sont tous deux jaunes ou tous deux non jaunes.
Preuve. Les nombres de sommets intérieurs aux quatre arcs que \(x\) et \(y\) déterminent sur les deux cercles ont tous la même parité. Précision ajoutée : sur chaque cercle, \(y\) a la même couleur que \(x\) si et seulement si le nombre de sommets strictement entre \(x\) et \(y\) est impair ; ce changement de couleur (ou non) est donc le même sur les deux cercles, et l'accord des deux couleurs en \(x\) se transmet à \(y\). \(\square\)
En particulier, chaque cercle contient un nombre pair de sommets jaunes.
Lemme 2. Si \(\overset{\frown}{xy}\), \(\overset{\frown}{yz}\) et \(\overset{\frown}{zx}\) sont des arcs de trois cercles deux à deux distincts de la configuration, alors le nombre de sommets jaunes dans \(\{x, y, z\}\) est impair.
Preuve. Soient \(C_1, C_2, C_3\) les trois cercles ; on peut supposer que \(C_2\) et \(C_3\) se coupent en \(x\), \(C_3\) et \(C_1\) en \(y\), et \(C_1\) et \(C_2\) en \(z\). Soient \(k_1, k_2, k_3\) les nombres de sommets intérieurs aux trois arcs considérés (portés respectivement par \(C_1, C_2, C_3\)). Tout cercle de la configuration distinct des \(C_i\) coupe le cycle \(\overset{\frown}{xy} \cup \overset{\frown}{yz} \cup \overset{\frown}{zx}\) en un nombre pair de points (rappelons que trois cercles ne sont jamais concourants), et les auto-intersections du cycle sont comptées deux fois ; la somme \(k_1 + k_2 + k_3\) est donc paire.
Notons \(Z_1\) la couleur que \(z\) reçoit de \(C_1\), et définissons de même les autres couleurs (\(X_2, X_3, Y_1, Y_3, Z_2\)). D'après ce qui précède, le nombre de paires bicolores dans la liste \((Z_1, Y_1)\), \((X_2, Z_2)\), \((Y_3, X_3)\) est impair (une paire est bicolore exactement quand le \(k_i\) correspondant est pair, et un nombre impair des \(k_i\) est pair). Comme le nombre total de changements de couleur le long du cycle \(Z_1 - Y_1 - Y_3 - X_3 - X_2 - Z_2 - Z_1\) est pair, le nombre de paires bicolores dans la liste \((X_2, X_3)\), \((Y_1, Y_3)\), \((Z_1, Z_2)\) est impair, et c'est exactement le nombre de sommets jaunes parmi \(x, y, z\). \(\square\)
Démontrons maintenant la minoration \((*)\). D'après le lemme 1, les \(k\) sommets jaunes de \(C\) se regroupent par paires, qui sont les points où \(C\) est coupé par \(k/2\) cercles de la configuration. D'après le lemme 2 (appliqué à \(C\) et à deux de ces cercles), ces cercles se coupent deux à deux en points jaunes, ce qui fournit \(2\binom{k/2}{2}\) autres sommets jaunes. Enfin, les \(n - k/2 - 1\) cercles restants coupent \(C\) en des sommets non jaunes (lemme 1), et le lemme 2 montre à nouveau que ces cercles se coupent deux à deux en points jaunes, ce qui fournit encore \(2\binom{n - k/2 - 1}{2}\) sommets jaunes. Il y a donc au moins \((*)\) sommets jaunes.
Ensuite, \(G\) est un graphe plan à \(n(n-1)\) sommets de degré \(4\) ; il a exactement \(2n(n-1)\) arêtes et exactement \(n(n-1) + 2\) faces (régions), face extérieure comprise (par la formule d'Euler pour les graphes planaires).
Lemme 3. Chaque face de \(G\) a autant de sommets rouges que de sommets bleus. En particulier, chaque face a un nombre pair de sommets non jaunes.
Preuve. On parcourt une fois le bord d'une face dans l'ordre circulaire, en regardant les couleurs que chaque sommet reçoit des deux cercles qui s'y coupent : on en déduit que les couleurs des sommets non jaunes alternent. \(\square\)
Par conséquent, si chaque région a au moins un sommet non jaune, elle en a au moins deux. Comme chaque sommet de \(G\) est de degré \(4\), le double comptage des incidences sommet–face montre que \(G\) a au moins \(n(n-1)/2 + 1\) sommets non jaunes, donc au plus \(n(n-1)/2 - 1\) sommets jaunes. (En fait, le lemme 3 montre qu'il y a au moins \(n(n-1)/4 + 1/2\) sommets rouges, et autant de bleus.)
Enfin, avec la minoration \((*)\),
c'est-à-dire \(\left(k - (n-2)\right)^2 \leq n - 2\), d'où \(k \leq n + \lfloor \sqrt{n-2} \rfloor - 2\), comme annoncé au premier paragraphe. \(\blacksquare\)
Solution 2¶
Les deux premiers lemmes de la solution 1 montrent que les cercles de la configuration se répartissent en deux classes : on prend un cercle \(C\) et tous les cercles qui coupent \(C\) en des points jaunes pour former une classe ; les cercles restants forment l'autre classe. Le lemme 2 montre que deux cercles d'une même classe se coupent en des points jaunes, et que deux cercles de classes différentes se coupent en des points non jaunes.
Appelons blancs et noirs les cercles des deux classes. Une région est dite jaune si tous ses sommets sont jaunes. Soient \(w\) et \(b\) les nombres de cercles blancs et noirs ; on a \(w + b = n\). Supposons \(w \geq b\) et qu'il n'y a aucune région jaune. On a évidemment \(b \geq 1\), sinon toutes les régions seraient jaunes. Les cercles blancs découpent le plan en \(w(w-1) + 2\) régions plus grandes, appelées régions blanches. Les bords des régions blanches découpent chaque cercle noir en arcs noirs. Comme il n'y a pas de région jaune, chaque région blanche contient au moins un arc noir.
Considérons une région blanche contenant \(t \geq 1\) arcs noirs. Montrons que le nombre de points où ces \(t\) arcs se coupent ne dépasse pas \(t - 1\). Pour cela, considérons le multigraphe dont les sommets sont ces arcs noirs, deux sommets étant reliés par une arête pour chaque point où les arcs correspondants se coupent. Si ce graphe avait plus de \(t - 1\) arêtes, il contiendrait un cycle, puisqu'il a \(t\) sommets ; ce cycle correspondrait à un contour fermé formé de sous-arcs noirs, situé à l'intérieur de la région considérée. Ce contour délimiterait à son tour au moins une région jaune, ce qui est impossible.
Soit \(t_i\) le nombre d'arcs noirs dans la \(i\)-ème région blanche. Le nombre total d'arcs noirs est \(\sum_i t_i = 2wb\), et ces arcs se coupent en \(2\binom{b}{2} = b(b-1)\) points. D'après ce qui précède,
ou, de façon équivalente, \((w - b)^2 \leq w + b - 2 = n - 2\), ce qui équivaut à \(w - b \leq \lfloor \sqrt{n-2} \rfloor\). Par conséquent \(b \leq w \leq \left(n + \lfloor \sqrt{n-2} \rfloor\right)/2\), donc chaque cercle porte au plus \(2(w-1) \leq n + \lfloor \sqrt{n-2} \rfloor - 2\) sommets jaunes : contradiction. \(\blacksquare\)