50 clés pour comprendre les maths
122
toute carte pouvait recevoir cinq couleurs. Le résultat aurait été génial si l’on avait
pu construire une carte qui ne pouvait pas se satisfaire de quatre couleurs. Les
mathématiciens étaient bien embarrassés : fallait-il quatre ou cinq couleurs ?
Le problème de base des quatre couleurs concernait les cartes dessinées sur une surface plane ou sphérique. Qu’en était-il des cartes
tracées sur une surface telle qu’un donut, surface intéressante
pour les mathématiciens davantage pour sa forme que pour ses
qualités gustatives. Heawood montra que sept couleurs étaient à
la fois nécessaires et suffisantes pour colorier toute carte sur une
telle surface. Il prouva même un résultat pour un donut à plusieurs trous (avec un nombre t de trous), dans lequel il
comptait le nombre de couleurs suffisant pour colorier la carte, bien qu’il ne réussît pas à prouver que
c’était le nombre minimum de couleurs nécessaires.
Voici un tableau pour les premières valeurs de t de
Heawood :
Nombre de trous, t 1 2 3 4
5
6
7
8
Nombre minimum
de couleurs, C
7 8 9 10 11 12 12 13
Et en général, C = [1/2 (7 + √(1 + 48t)]. Les crochets désignent la partie entière du
terme qu’ils encadrent. Par exemple, lorsque t = 8, C = [13,3107…] = 13. Heawood
a démontré sa formule pour t ≥ 1. Mais si l’on succombe à la tentation de prendre
la valeur « interdite » t = 0, on obtient C = 4.
Le problème est-il résolu ? 50 ans plus tard, le problème, apparu en 1852,
n’avait toujours pas été résolu. Au xx
e siècle, l’intelligence de l’élite mathématique
du monde entier se trouvait complètement désemparée.
On fit quelques progrès, tant et si bien qu’un mathématicien prouva qu’il suffisait de
quatre couleurs pour représenter jusqu’à 27 pays sur une carte ; un autre fit mieux et
affirma la même chose pour 31 pays, et un autre pour 35. Cette avancée par petites
touches, si elle s’était poursuivie, aurait pu continuer à l’infini. En fait, les observations faites par Kempe et Cayley dans leurs tout premiers articles fournirent une
meilleure méthode : les mathématiciens comprirent que l’on pouvait se contenter
de vérifier la configuration de certaines cartes pour s’assurer qu’il suffisait de quatre
couleurs. Mais le trop grand nombre de cartes posait problème puisqu’au début, il y
en avait des centaines à vérifier. Cette vérification ne pouvait pas être faite à la main
mais par chance, le mathématicien allemand Wolfgang Haken, qui avait travaillé sur
le problème pendant de nombreuses années, réussit à s’assurer le concours du mathématicien et spécialiste en informatique Kenneth Appel. Des méthodes ingénieuses
diminuèrent le nombre de configurations qui ne dépassèrent pas 1500. En juin 1976,
au terme de nombreuses nuits blanches, le travail était accompli, et avec l’aide de leur
fidèle ordinateur IBM 370, ils avaient résolu ce problème magnifique.
Le donut simple
ou « tore »
Un tore à deux
trous
122
toute carte pouvait recevoir cinq couleurs. Le résultat aurait été génial si l’on avait
pu construire une carte qui ne pouvait pas se satisfaire de quatre couleurs. Les
mathématiciens étaient bien embarrassés : fallait-il quatre ou cinq couleurs ?
Le problème de base des quatre couleurs concernait les cartes dessinées sur une surface plane ou sphérique. Qu’en était-il des cartes
tracées sur une surface telle qu’un donut, surface intéressante
pour les mathématiciens davantage pour sa forme que pour ses
qualités gustatives. Heawood montra que sept couleurs étaient à
la fois nécessaires et suffisantes pour colorier toute carte sur une
telle surface. Il prouva même un résultat pour un donut à plusieurs trous (avec un nombre t de trous), dans lequel il
comptait le nombre de couleurs suffisant pour colorier la carte, bien qu’il ne réussît pas à prouver que
c’était le nombre minimum de couleurs nécessaires.
Voici un tableau pour les premières valeurs de t de
Heawood :
Nombre de trous, t 1 2 3 4
5
6
7
8
Nombre minimum
de couleurs, C
7 8 9 10 11 12 12 13
Et en général, C = [1/2 (7 + √(1 + 48t)]. Les crochets désignent la partie entière du
terme qu’ils encadrent. Par exemple, lorsque t = 8, C = [13,3107…] = 13. Heawood
a démontré sa formule pour t ≥ 1. Mais si l’on succombe à la tentation de prendre
la valeur « interdite » t = 0, on obtient C = 4.
Le problème est-il résolu ? 50 ans plus tard, le problème, apparu en 1852,
n’avait toujours pas été résolu. Au xx
e siècle, l’intelligence de l’élite mathématique
du monde entier se trouvait complètement désemparée.
On fit quelques progrès, tant et si bien qu’un mathématicien prouva qu’il suffisait de
quatre couleurs pour représenter jusqu’à 27 pays sur une carte ; un autre fit mieux et
affirma la même chose pour 31 pays, et un autre pour 35. Cette avancée par petites
touches, si elle s’était poursuivie, aurait pu continuer à l’infini. En fait, les observations faites par Kempe et Cayley dans leurs tout premiers articles fournirent une
meilleure méthode : les mathématiciens comprirent que l’on pouvait se contenter
de vérifier la configuration de certaines cartes pour s’assurer qu’il suffisait de quatre
couleurs. Mais le trop grand nombre de cartes posait problème puisqu’au début, il y
en avait des centaines à vérifier. Cette vérification ne pouvait pas être faite à la main
mais par chance, le mathématicien allemand Wolfgang Haken, qui avait travaillé sur
le problème pendant de nombreuses années, réussit à s’assurer le concours du mathématicien et spécialiste en informatique Kenneth Appel. Des méthodes ingénieuses
diminuèrent le nombre de configurations qui ne dépassèrent pas 1500. En juin 1976,
au terme de nombreuses nuits blanches, le travail était accompli, et avec l’aide de leur
fidèle ordinateur IBM 370, ils avaient résolu ce problème magnifique.
Le donut simple
ou « tore »
Un tore à deux
trous