En juillet dernier a eu lieu le Tournoi International des Jeunes Mathématiciens, ou ITYM, à l’université de Sofia (Bulgarie). Le principe ? Des équipes d’environ 6 lycéens, venues des quatre coins du monde, s’attaquent à des problèmes ouverts dont les énoncés sont publiés en ligne quelques mois avant le début de la compétition. Puis ces équipes se rencontrent et s’affrontent sous forme de joutes verbales face à un jury.
Il existe un tournoi similaire en France, le Tournoi Français des Jeunes Mathématiciennes et Mathématiciens — ou \(\mathbb{TFJM}^2\) — qui est qualificatif pour le tournoi international (voir aussi cet article de Pierre Pansu).
À l’occasion de la publication d’une première version des problèmes du \(\mathbb{TFJM}^2\)— (disponible à cette adresse) —, voici un exemple de problème posé lors de l’ITYM 2015, et d’une partie de la solution proposée par l’équipe France 1, qui a remporté le tournoi 3Il s’agit donc d’une équipe d’un très bon niveau. De nombreuses équipes avec un bagage mathématique plus modeste participent à la version française du tournoi : pas besoin d’être un crack pour concourir !. Un journal de bord des équipes françaises lors de cette semaine à Sofia a déjà été publié sur le site d’Animath. Voir aussi le live-tweet de la finale.
Énoncé
Tout d’abord, voici l’énoncé du problème, tel que posé aux lycéens. 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 :
Proposition
Pour tout entier \(n\) supérieur à 8, on a
\[C_2(n,2)\ge 4.\]
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) 4Le problème C2 de cette liste . pour démontrer le lemme (ou résultat intermédiaire) suivant :
Lemme
Si tout point du plan est contenu dans au plus \(k\) disques, alors chaque disque intersecte au maximum \(7k-1\) autres disques.
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 :
Proposition
Pour tous les entiers \(n\) et \(k\), on a
\[C_2(n,k)\leq 7k.\]
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 ici le diaporama utilisé par l’équipe lors de sa présentation orale.
Post-scriptum
Toute l’équipe tient à remercier les organisateurs de l’ITYM pour cette très belle compétition, ainsi que l’association française Animath qui a mis en place et financé une partie du séjour.
ÉCRIT PAR
Pierre-Antoine Guihéneuf
Maître de conférences - IMJ-PRG - Sorbonne Université
