[RécréaSciences] - Quel nombre maximum de couleurs peut-on utiliser pour colorier une carte sans que 2 pays avec une frontière commune ne soient de la même couleur ?

Publié par Centre•Sciences, le 11 juillet 2019   240

Xl 2019 07 quatre couleur

Ce problème est connu sous le nom du théorème des quatre couleurs. Il resta un problème non résolu pendant plus d'un siècle. En 1852, Francis Guthrie, mathématicien sud-africain essayait de colorier les cartes des cantons d’Angleterre de telle sorte que deux cantons voisins soient de couleurs différentes et remarqua que seulement 4 couleurs étaient suffisantes.
En bon mathématicien, se pose alors la question de la démonstration et de la généralisation du problème.
Prenez une carte de France par exemple et vous pourrez sans problème colorier les régions avec 10 couleurs, puis 8, puis 6. Avec 5 puis 4 couleurs, il faut commencer à réfléchir à l’organisation des couleurs entre elles
Mais à 3 cela coince souvent. Très rapidement on comprend qu’il faut intégrer une 4e couleur pour éviter que 2 couleurs ne se touchent.

Francis Guthrie expose le problème à son ancien professeur, Auguste De Morgan qui le soumet à Arthur Cayley qui rédigera le premier article décrivant les difficultés du problème. Deux premières démonstrations furent publiées, respectivement par Alfred Kempe en 1879 et Peter Guthrie Tait en 1880. Mais elles se révélèrent erronées.

En 1976, les Américains, Kenneth Appel et Wolfgang Haken, affirment avoir démontré le théorème. La démonstration rend perplexe les mathématiciens car pour la première fois une démonstration mathématique utilise un ordinateur. Le problème de la démonstration du théorème se trouve alors déplacé vers le problème de la validation.

En 2005, le logiciel Coq développé par l’Inria a permis à un ordinateur de complètement vérifier le théorème des quatre couleurs : il faut au MAXIMUM quatre couleurs pour colorier une "bonne" carte. Par exemple, 4 pour un tétraèdre mais 3 pour un cube... Cherchez d’autres exemples où 3 couleurs suffisent.

Texte avec la collaboration de Philippe Grillot et Stéphane Cordier, Institut Denis Poisson.

En complément, voir également les vidéos :

"Deux (deux ?) minutes pour... le théorème des 4 couleurs" mise en ligne sur le compte YouTube El Jj le 21 octobre 2016.

"Le théorème des 4 couleurs — Science étonnante #4" mise en ligne sur le compte YouTube ScienceEtonnante le 22 février 2015

"Retour sur le théorème des 4 couleurs — Carte Postale #2" mise en ligne sur le compte YouTube ScienceEtonnante le 19 août 2016


>> Copyright image de Une : Vincent Burille (Zinzo)



RécréaSciences - Éveiller notre curiosité scientifique tout en nous amusant : c'est le pari de ce rendez-vous avec Centre•Sciences, Centre de promotion de la Culture Scientifique Technique et Industrielle de la région Centre-Val de Loire.

Retrouvez d'autres RécréaSciences sur le site de Centre•Sciences et régulièrement dans l'émission "Terre de Sciences" diffusée sur RCF Loiret.