Énoncé

Tout d’abord, voici l’énoncé du problème, tel que posé aux lycéens (cliquer pour afficher l’image). On donne une traduction édulcorée de la question 2 — qui nous intéressera dans cet article — juste après.

Deux lycéens, Clara et Carl, jouent au jeu suivant.

Clara dispose de $n$ disques, tous de même rayon. Elle les pose un par un dans le plan, de telle manière que tout point du plan est recouvert par au plus $k$ disques. À chaque fois que Clara pose un disque, Carl colore ce disque, de telle manière que deux disques se chevauchant aient deux couleurs différentes. Le but de Carl est d’utiliser le moins de couleurs possible pour ce coloriage : on appelle $C_2(n,k)$ le nombre minimum de couleurs pour lequel Carl est sûr de pouvoir colorier les disques, peu importe comment Clara les place.

Question : essayer d’estimer les nombres $C_2(n,k)$.

Un premier exemple

Regardons ce qui se passe lorsque Clara joue de la manière suivante (à lire de gauche à droite et de haut en bas !) :

On se convainc facilement que lorsque Clara joue de cette manière, Carl a besoin d’au moins 4 couleurs pour colorier les disques : au bout du cinquième tour, Carl a forcément déjà utilisé 3 couleurs, et il y a au moins un disque dont les deux voisins sont de deux couleurs différentes. Clara utilise alors ce disque comme pivot, et dessine trois autres disques autour. Forcément, l’un au moins de ces disques est d’une couleur différente des trois couleurs utilisées jusque là. Un petit calcul (ou au choix un petit raisonnement géométrique) permet de démontrer qu’on peut effectivement utiliser n’importe lequel des 5 premiers cercles comme pivot, et en placer trois autres autour comme sur le dernier dessin.

On vient de démontrer la proposition suivante :

Notons que dans cet exemple tous les cercles sont de même rayon, mais les règles permettent aussi à Clara de choisir des cercles de rayons différents si elle le souhaite.

Le lecteur attentif aura remarqué que les résultats du jeu sont bien différents si Carl n’effectue le coloriage qu’une fois que Clara a posé tous les disques. Dans ce cas, et pour cette configuration, Carl n’a besoin que de trois couleurs, comme sur le dessin suivant :

Cette subtilité de la règle du jeu a induit en erreur bien des équipes lors du tournoi !

Un majorant de $C_2(n,k)$

L’équipe a aussi obtenu un majorant du nombre $C_2(n,k)$. Pour cela, elle s’est inspirée d’un problème d’IMO 2003 (l’Olympiade Internationale de Mathématiques, une autre compétition internationale de mathématiques, qui consiste quant à elle à résoudre des problèmes dans un temps beaucoup plus court) [2] pour démontrer le lemme (ou résultat intermédiaire) suivant :

Preuve de ce lemme

Soit $D$ un disque quelconque, dont le centre est noté $O$. Comme tous les disques ont le même rayon, on peut supposer que celui-ci est toujours égal à 1. On commence par subdiviser le plan en 7 parties, l’une étant le disque, les autres étant les ensembles $T_i$ comme sur le dessin suivant.

Plus précisément, on trace 6 demi-droites du plan, partant toutes de $O$, telles que deux demi-droites consécutives forment un angle de $60º$. Chaque ensemble $T_i$ est l’ensemble des points qui sont situés entre deux demi-droites consécutives, et en dehors de $D$. On trace aussi six segments, en pointillés bleus sur la figure, dont les extrémités sont les points situés sur les demi-droites et à distance $2$ de $O$. On appelle $P_i$ les milieux de ces segments. Le lecteur pourra montrer que la longueur de chacun de ces segments est elle aussi $2$.

On va montrer que si un disque $D'$ a son centre dans $T_i$ et intersecte le cercle initial $D$, alors $D'$ contient le point $P_i$. Découpons chaque région $T_i$ en deux régions $U_i$ (en bleu sur le dessin suivant) et $V_i$ (en rouge), séparées par le segment en pointillés bleus du dessin précédent.

On montre alors facilement que si le centre de $D'$ se situe dans la région $U_i$, alors $D'$ contient le point $P_i$ (autrement dit, tout point de la région $U_i$ est à distance au plus 1 du point $P_i$).

Supposons maintenant que le centre de $D'$ se situe dans la région $V_i$. On appelle $Q$ le centre de $D'$, et $R$ l’intersection entre le segment $[OQ]$ et le cercle bordant le disque initial $D$, comme sur le dessin précédent.

On remarque alors que d’une part, $\widehat{QP_iR} \geq \widehat{CP_iB}=60º$ et d’autre part, $\widehat{P_iRO} \geq \widehat{P_iBO}=120º$, donc $\widehat{P_iRQ} \leq 60º$. Par conséquent, $\widehat{QP_iR} \geq \widehat{P_iRQ}$. En considérant le triangle $QP_i R$, on en déduit que $QR \geq QP_i$. Mais puisque le disque $D'$ intersecte le disque $D$, le rayon de $D'$ est supérieur à la distance $QR$. Donc le rayon de $D'$ est supérieur à la distance $QP_i$, si bien que le disque $D'$ contient le point $P_i$.

On a donc démontré que pour tout nombre $i$ entre 1 et 6, le nombre de disques $D'$ ayant leur centre dans la région $T_i$ et intersectant le disque initial $D$ est inférieur à $k$. De plus, puisque tous les disques ont le même rayon, le nombre de disques ayant leur centre dans le disque initial $D$ est inférieur à $k-1$ (regarder ce qui se passe au point $O$). Par conséquent, le nombre de disques $D'$ intersectant le disque initial $D$ est inférieur à $(k-1) + 6k=7k-1$.

De ce lemme, on déduit alors le résultat suivant :

En effet, supposons que Carl ait choisi $7k$ couleurs. À chaque fois que Clara place un disque, le lemme nous dit que celui-ci possède au plus $7k-1$ voisins. En particulier (puisque $7k-1<7k$), il y a une couleur parmi les $7k$ que Carl a choisi au départ qui ne figure pas parmi les couleurs des disques adjacents à ce nouveau disque. Carl peut alors colorier ce nouveau disque avec cette couleur. Ainsi de suite, à chaque tour, Carl peut colorier le disque que vient de poser Clara à l’aide d’une des $7k$ couleurs de départ.

Ces deux démonstrations ne sont que des extraits de la solution donnée par l’équipe : les élèves ont aussi traité le cas des dimensions 1 et supérieure à trois, ainsi que celui où Alice a la possibilité de choisir le rayon des disques qu’elle pose. L’équipe s’est rendu compte au milieu du tournoi que l’une de ses démonstrations concernant ce dernier cas était fausse ; ça n’a pas empêché Henry — l’élève de l’équipe qui a présenté ce problème à l’oral — de remporter le prix du meilleur présentateur (« best reporter ») ! Pour les plus curieux, la solution complète de l’équipe se trouve ici (on pourra trouver les autres solutions et rapports des équipes sur cette page du site officiel de l’ITYM), et voici le diaporama utilisé par l’équipe lors de sa présentation orale :