Pavages du plan : quand deux couleurs peuvent-elles suffire ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Bienvenue à toutes et à tous pour cette nouvelle exploration. Alors aujourd'hui, on va parler d'un sujet qui a l'air vraiment tout bête au premier abord.

Intervenant 20:11

Oui, on pourrait presque croire à un jeu d'enfant en fait.

Intervenant 10:15

C'est ça. Imaginez, vous êtes en 1852. Un jeune cartographe se pose une question limite digne d'une cour de récréation. Combien de crayons de couleurs il faut, au minimum, pour colorier n'importe quelle carte du monde sans que deux pays qui se touchent aient la même couleur.

Intervenant 20:32

Et ils pensaient sûrement régler ça en quelques heures sur un coin de table.

Intervenant 10:36

Sauf qu'il a fallu plus d'un siècle, l'invention des premiers supercalculateurs et même une sorte de crise existentielle chez les mathématiciens pour en venir à bout.

Intervenant 20:45

Exactement. Et c'est ce contraste qui est passionnant. Notre mission aujourd'hui, en s'appuyant sur l'article « colorier les pavés » du plan, c'est vraiment de décortiquer ça. On va voir comment une activité super basique force la science à se réinventer.

Intervenant 11:01

Alors, décortiquons tout ça. On va partir d'un simple collier de perles pour finir par modéliser le chaos d'une vraie carte géographique.

Intervenant 21:08

Voilà le programme.

Intervenant 11:09

Plongeons directement dans le vif du sujet, le fameux théorème des quatre couleurs. Ce truc affirme que quatre couleurs, c'est toujours suffisant pour colorier n'importe quelle carte plane.

Intervenant 21:19

Tant que les régions sont d'un seul tenant, oui.

Intervenant 11:22

Oui, voilà, 100 morceaux séparés. Mais la question a été posée au milieu du XIXe siècle et la première vraie démonstration, elle, n'arrive qu'en 1976. Et là, d'après notre source, c'était un vrai scandale.

Intervenant 21:34

Ah oui, le mot scandale n'est pas trop fort. Cette preuve de Kenneth Appal et Wolfgang Haken, elle a provoqué une vraie rupture. Parce qu'avant, en 1976, une preuve mathématique, c'était un raisonnement humain.

Intervenant 11:48

Quelque chose qu'on pouvait lire au tableau, quoi.

Intervenant 21:50

C'est ça, ligne par ligne. Mais eux, ils ont utilisé un ordinateur pour tester des milliers de configurations incontournables. La machine a mouliné pendant des centaines d'heures avant de dire, en gros, c'est bon.

Intervenant 12:03

Mais pourquoi ça ne faisait pas consensus ? Une preuve mathématique n'est pas censée être

Intervenant 22:07

absolue. Le problème, c'est que vérifier manuellement tout ce que l'ordinateur a fait, ça prendrait des vies entières. Donc, on devait faire confiance à une boîte noire. Et si la machine avait eu un bug ?

Intervenant 12:19

Ah, je vois. Si une carte perforée de l'époque était mal lue, tout s'effondrait.

Intervenant 22:23

Voilà. C'est pour ça qu'en 2005, Georges Gontier et Benjamin Werner ont publié une nouvelle démonstration en utilisant la vérification formelle.

Intervenant 12:33

Attendez, utiliser un ordinateur pour vérifier un autre ordinateur, c'est pas un peu le serpent qui se mord la queue ?

Intervenant 22:39

Alors, on pourrait le croire, mais c'est différent. Ils n'ont pas fait tester Descartes à la machine, ils lui ont appris les lois de la logique mathématique. C'est le programme lui-même qui a été prouvé sans faille logique par l'ordinateur.

Intervenant 12:53

D'accord, donc on ne valide pas des milliers d'exemples, on valide la logique même du raisonnement.

Intervenant 22:58

Exactement, et c'est ça qui a fini par mettre tout le monde d'accord.

Intervenant 13:01

Super clair. Bon, si quatre couleurs suffisent, notre article fait remarquer qu'elles ne sont pas toujours nécessaires. Parfois trois, voire deux suffisent. Mais pour comprendre pourquoi, il faut oublier nos cartes géographiques hyper complexes.

Intervenant 23:13

Oui, il faut réduire la dimension, passer de la surface à une simple ligne.

Intervenant 13:18

C'est là que ça devient vraiment intéressant. L'article utilise l'analogie du collier de perles.

Intervenant 23:23

C'est une excellente image.

Intervenant 13:24

Imaginez que chaque pays est une perle sur un fil. La règle, c'est deux perles qui se touchent ne peuvent pas avoir la même couleur. Si mon fil est ouvert, tendu sur la table, j'ai juste besoin de deux couleurs. Bleu rouge, bleu rouge.

Intervenant 23:37

Et ça peut durer à l'infini comme ça. Ce qui est fascinant ici, c'est l'introduction de la contrainte spatiale. Que se passe-t-il si vous fermez le collier ?

Intervenant 13:46

Ah ! Eh bien, la première perle et la dernière se retrouvent collées.

Intervenant 23:50

C'est ça. Et là, tout dépend de la parité.

Intervenant 13:53

La parité. Donc paire ou impaire.

Intervenant 23:55

Voilà. Si votre collier a un nombre pair de perles, disons 100, puisque vous avez alterné, la centième sera de couleur opposée à la première.

Intervenant 14:04

Donc, je ferme le collier et le rouge touche le bleu. Aucun problème.

Intervenant 24:10

Exactement, deux couleurs suffisent. Mais si votre collier admet un nombre impair de perles, disons 101 perles.

Intervenant 14:17

Aïe ! Là, la centunième sera de la même couleur que la première. Donc, si je ferme la boucle, j'ai deux perles bleues qui se touchent.

Intervenant 24:26

Et voilà ! La boucle force le contact de deux éléments identiques. La seule solution, c'est d'utiliser une troisième couleur pour cette dernière perle.

Intervenant 14:34

C'est génial ! Donc cette règle de parité sur une simple ligne fermée, c'est ça qui dicte tout le reste.

Intervenant 24:41

Tout à fait. C'est la clé absolue pour comprendre ce qui se passe quand on étale ses formes sur un plan, en deux dimensions.

Intervenant 14:47

Alors passons à la 2D justement. Imaginons un monde parfait, ce qu'on appelle des pavages réguliers. Le meilleur exemple visuel, c'est le nid d'abeilles, avec ses hexagones identiques.

Intervenant 24:58

Oui, prenons le nid des balibs. On va utiliser le concept de pivots et couronnes.

Intervenant 15:03

Ok. Comment ça marche ?

Intervenant 25:06

On isole un hexagone central qu'on appelle le pivot, numéroté 0. Ensuite, on regarde les hexagones qui l'entourent, qui touchent ses bords. C'est sa couronne.

Intervenant 15:15

Donc, dans un nid d'abeilles, mon hexagone central a très exactement six voisins. Ma couronne a six cellules.

Intervenant 25:23

Et six sépaires.

Intervenant 15:25

Ah, je vois où vous voulez en venir.

Intervenant 25:27

En appliquant la règle du collier fermé, la couronne nécessite seulement deux couleurs, disons du vert et du bleu alternés.

Intervenant 15:34

Bleu, vert, bleu, vert, bleu, vert, ça marche. Mais le pivot au milieu y touche à la fois le bleu et le vert.

Intervenant 25:41

Exactement ! Donc il lui faut une troisième couleur, du rouge par exemple. Bilan des courses, trois couleurs suffisent pour tout un nid d'abeilles, à l'infini.

Intervenant 15:49

C'est fou ! Mais attendez, est-ce que la géométrie exacte des hexagones a de l'importance ? Si je dessine des hexagones tout déformés ?

Intervenant 25:58

Eh bien, pas du tout ! Et c'est là qu'intervient une branche magnifique des mathématiques, la théorie des graphes.

Intervenant 16:04

Les graphes, c'est-à-dire des points et des lignes.

Intervenant 26:07

C'est ça ! On transforme chaque cellule en un sommet, un simple point, et chaque frontière en une arête, un trait qui relie deux points. Le graphe prouve que ce qui compte, ce ne sont pas les distances ou les angles, ce sont juste les connexions.

Intervenant 16:22

Le local devient global, en gros, sans se soucier de la géométrie pure.

Intervenant 26:26

Tout à

Intervenant 16:26

fait. Et la flexibilité de ce concept permet des trucs assez étonnants. L'article prend l'exemple des quadrilatères, les formes à quatre côtés. On pourrait les agencer comme les hexagones, avec une couronne de six pavés, donc trois couleurs.

Intervenant 26:39

Oui, c'est la configuration classique.

Intervenant 16:41

Mais il y a une autre façon de les agencer où la couronne autour du pivot compte huit pavés. Huit, c'est pair. Donc, on a besoin de deux couleurs pour la couronne et d'une troisième pour le centre, non ?

Intervenant 26:53

Eh bien, surprise ! Dans cet agencement précis, la forme centrale, le pivot, ne partage une vraie frontière qu'avec quatre des huit pavés. Elle touche les quatre autres uniquement par la pointe, par les coins,

Intervenant 17:06

Et un coin, ce n'est pas une frontière.

Intervenant 27:08

Exactement. Donc le pivot peut partager la couleur d'un des pavés qu'il ne touche que par un coin. Résultat, deux couleurs suffisent.

Intervenant 17:17

Wow, deux couleurs pour tout un plan de quadrilatère. Bon, c'est très beau dans un monde parfait de pavage isométrique. Mais les vraies cartes, c'est loin d'être régulier. Il y a des grands pays, des petits, des formes bizarres.

Intervenant 27:28

Et oui, c'est le chaos. Et c'est là qu'apparaît la fameuse quatrième couleur.

Intervenant 17:32

Montrez-nous comment ça arrive, étape par étape.

Intervenant 27:35

Imaginez un pavage irrégulier. On prend une cellule pivot, en rouge, on regarde sa couronne, et là, à cause de l'irrégularité, elle a 7 voisines.

Intervenant 17:45

7 ?

Intervenant 27:46

Un nombre impair. Retour au problème du collier mal fermé.

Intervenant 17:50

C'est exactement ça. On commence à colorier la couronne. Cellule 1 en bleu, 2 en vert, 3 en bleu, jusqu'à la sixième en vert. Mais voilà, la cellule 7, pour boucler la couronne, elle touche la cellule 1.

Intervenant 28:04

Donc elle touche du bleu. Elle touche du vert de la cellule 6. Et comme c'est la couronne, elle touche le pivot rouge.

Intervenant 18:11

Cela soulève une question importante. Comment ferme-t-on la boucle ?

Intervenant 28:15

Il n'y a plus de couleur dispo. Il faut obligatoirement sortir un pot de jaune.

Intervenant 18:19

Voilà la quatrième couleur. Elle est indispensable ici. Mais du coup, ça crée un effet domino, non ? Si on décale notre regard, qu'on prend la cellule 1 en bleu comme nouveau pivot, sa nouvelle couronne va inclure de nouvelles cellules. Le jaune va poser problème. Il faudrait une cinquième couleur.

Intervenant 28:34

C'est l'angoisse de tout mathématicien, mais non. Le théorème des quatre couleurs tient bon grâce à ce qu'on appelle les permutations ou chaînes de Kemp.

Intervenant 18:43

Comment ça marche ?

Intervenant 28:44

Si une nouvelle couronne semble exiger une cinquième couleur, le système nous permet d'inverser deux couleurs dans une zone voisine. On échange tout le bleu et le rouge d'un côté, ça libère le jaune de l'autre, sans créer de conflit.

Intervenant 18:58

C'est brillant ! Les couleurs dansent et s'équilibrent pour ne jamais dépasser quatre. Mais je pose un ultime défi. Et si une zone de la carte n'existe pas ? S'il y a un gros trou dans le plan ?

Intervenant 29:08

Alors là, qu'est-ce que tout cela signifie quand la réalité est pleine de trous ? Eh bien curieusement, ça se comporte un peu comme le cas des deux couleurs.

Intervenant 19:16

Vraiment ?

Intervenant 29:16

Ça ne complique pas la chose ?

Intervenant 19:18

Pas du

Intervenant 29:18

tout ! Si une cellule manque, l'absence agit un peu comme un élastique qu'on relâche. La couronne s'allonge et contourne simplement le trou.

Intervenant 19:26

Donc au lieu d'avoir un nœud hyper connecté, on a juste une grande frontière qui s'étire.

Intervenant 29:31

C'est ça. Le vide supprime des contraintes frontalières, il ne les ajoute pas.

Intervenant 19:35

Et si un jour on découvre une île au milieu de ce trou ?

Intervenant 29:38

Si la cellule réapparaît, elle sera simplement coloriée avec une des quatre couleurs pour maintenir la palette grâce aux réarrangements qu'on a évoqués. Donc régularité, chaos ou même des trous, le théorème nous garantit que c'est mathématiquement possible.

Intervenant 19:52

C'est d'une élégance folle. Si je résume, on part de la simple alternance des perles d'un collier Et ça donne naissance à une théorie des graphes capable de cartographier les découpages les plus chaotiques avec juste quatre crayons.

Intervenant 210:05

Tout à fait. Mais si on relie cela à une vision plus large, je vous laisse méditer là-dessus.

Intervenant 110:11

Je vous écoute.

Intervenant 210:12

Le théorème des quatre couleurs est absolu pour un plan plat, en 2D. Mais que se passerait-il si notre carte était dessinée sur une surface différente ?

Intervenant 110:22

C'est-à-dire ?

Intervenant 210:22

Par exemple, sur la surface d'un donut, un tord en mathématiques. L'espace s'y replie, les pays peuvent se connecter par l'intérieur du trou. Sur un tel objet, ou sur une forme en 3D où les régions s'entremêlent, quatre couleurs ne suffisent plus du tout.

Intervenant 110:38

Attendez,

Intervenant 210:39

vraiment ? Oui. Est-ce que la topologie de l'univers lui-même dicte le nombre de couleurs dont on aurait besoin pour le cartographier ? Je vous pose la question.

Intervenant 110:49

Oh waouh ! C'est une réflexion carrément vertigineuse. Essayez de visualiser une carte politique sur un donut, ça donne presque le tournis. Merci beaucoup pour toutes ces explications, c'était passionnant.

Intervenant 211:01

Avec grand plaisir.

Intervenant 111:02

Merci à toutes et à tous pour votre écoute attentive de ce numéro du podcast du magazine Tangente. On se donne rendez-vous très vite pour une prochaine exploration approfondie.