Magazine Science

Des p'tits problèmes de coloriage ?

Publié le 30 novembre 2008 par Olivier Leguay

a003-099.gifLes mathématiciens aiment colorier. Peut-être n'ont-ils pas eu le temps de le faire à l'école, alors ils rattrapent le temps perdu.
Dès 1852, l'un d'entre eux se demanda combien il fallait de couleurs pour colorier tous les pays de n'importe quelle carte sans que deux pays voisins n'aient la même couleur. Le problème est capital car dans le cas contraire on ne pourrait plus distinguer ces deux pays après coloriage. Il pensa que quatre devait être suffisant. Beaucoup de mathématiciens prirent aussi leurs crayons de couleurs et se mirent d'accord sur le nombre : 4 doit convenir mais ils ne s'accordèrent qu'à moitié sur la preuve car celle-ci faisait intervenir un bien étrange "personnage": un ordinateur. Bref après quelques guéguerres internes sur le style, l'incontournable boite aux quatre crayons nécessaire pour colorier toutes les cartes imaginables de l'univers s'appelle désormais "Théorème des quatre couleurs".

Je t'ai apporte des crayons

Malgré  la difficulté de la preuve et des conversations qui lui étaient associée, les mathématiciens s'ennuyaient un peu. C'est ainsi qu'en 1950, un certain Edward Nelson, agé de seulement 18 ans, lança un autre coloriage encore en vogue pour les occuper.
D'un air sans doute amusé, il soumit à la communauté, le petit problème suivant :

Combien faut-il de couleurs différentes pour colorier chaque point du plan, de façon que deux points distants d'une unité n'aient pas la même couleur?

Si les mathématiciens étaient troublés, ce n'était pas parce qu'ils se demandaient avec quel type de crayon ils allaient réaliser cet étrange travail mais plutôt pourquoi est-ce qu'ils avaient seulement réussi à démontrer qu'il fallait au moins 4 couleurs et au plus 7 pour réaliser cette activité presque manuelle? Ils ne parvenaient pas à donner le nombre exact de couleurs minimal dont ils avaient besoin pour colorier les points du plan avec cette contrainte: 4,5,6 ou 7?

My son's color pencils

Alors d'où vient la difficulté? Certainement de la théorie des ensembles à laquelle on peut adjoindre différentes versions de l'axiome du choix ou au contraire  l'en priver.

L'axiome du choix dit qu'il est possible de prélever des éléments d'ensembles différents et de construire un autre ensemble. Si l'idée parait simpliste lorsque les ensembles sont finis, elle ne l'est pas lorsqu'ils deviennent infinis.

m4-18.jpg
Bertrand Russel, nous donne une vague idée de ce que peut-être l'axiome du choix au quotidien :

Pour choisir une chaussette plutôt que l'autre pour chaque paire d'une collection infinie, on a besoin de l'axiome du choix. Mais pour les chaussures, ce n'est pas la peine.

Explication :

  • Quand on dispose d'une paire de chaussettes quelconque, on n'a aucun moyen a priori de distinguer une chaussette de l'autre, ce sont des objets a priori identiques et même si chaque matin on arrive à choisir laquelle on va mettre en premier, on serait bien en peine de trouver un procédé général qui nous permette de renouveler l'exploit éternellement.
  • Pour les chaussures, il existe un moyen de choisir qui marche tout le temps (une fonction de choix naturelle) : choisir toujours la chaussure gauche (ou droite) puisqu'il y a toujours une chaussure gauche et une chaussure droite.

Cet axiome du choix est vraiment un élement trouble-fête. Il avait déjà permis à un mathématicien de s'enrichir.

Il s'est aussi mis sur le chemin de deux mathématiciens Soifer et Shelah qui parvinrent à démonter qu'en utilisant deux versions différentes de cet axiome, il fallait pour résoudre le même problème de coloriage, soit 2 couleurs, soit une infinité! C'est le grand écart.

Tout cela pour vous dire que les mathématiciens ont vraiment des "gros problèmes de coloriage"!

Inspiré de - Coloriages irréels - Complexités de Jean-Paul Delahaye aux éditions Pour la Science

Pour compléter sur l'axiome du choix :

Du choix dans la dissection -  sur le blog Choux romanesco et intégrale curviligne


Vous pourriez être intéressé par :

Retour à La Une de Logo Paperblog

Ces articles peuvent vous intéresser :

A propos de l’auteur


Olivier Leguay 1825 partages Voir son profil
Voir son blog

l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte

Dossier Paperblog