De la recherche en maths au lycée
Le tournoi international des jeunes mathématiciens
Où on donne une partie d’une solution de l’équipe France 1
Le 15 décembre 2015 Voir les commentaires
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 [1]. 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 (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 :
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 :
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.
Notes
[1] Il 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, le $\mathbb{TFJM}^2$ : pas besoin d’être un crack pour concourir !
[2] Le problème C2 de cette liste.
Partager cet article
Pour citer cet article :
Équipe France 1 du tournoi international, Pierre-Antoine Guihéneuf — «Le tournoi international des jeunes mathématiciens» — Images des Mathématiques, CNRS, 2015
Laisser un commentaire
Actualités des maths
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
-
1er avril 2022Prix D’Alembert 2022 attribué à Jean-Michel Blanquer
-
10 mars 2022Géométries non euclidiennes mais dynamiques
-
6 mars 2022Contrôle et apprentissage automatique (streaming, 10/3)
-
24 février 2022Bienvenue au CryptoChallenge 2022 « Qui a volé les plans d’Ada Lovelace ? »
Commentaire sur l'article