Le coloriage de cartes

Colorier une carte sans que deux régions voisines aient la même couleur, avec le moins de couleurs possible. La page tire des cartes au hasard, signale les fautes directes et calcule le minimum. Deux couleurs suffisent pour des rectangles superposés ; quatre suffisent toujours, et c'est un théorème de 1976.

On choisit une couleur, puis on clique sur les régions d'une carte tirée au hasard, de $8$ à $26$ régions. La page ne signale que les frontières séparant deux régions voisines de même couleur, donne un indice sur demande, et annonce à la fin le plus petit nombre de couleurs possible, qu'elle calcule exactement.

Ce que cela signifie : une carte découpée par des rectangles superposés se colorie avec $2$ couleurs, selon la parité du nombre de rectangles qui contiennent chaque région ; la page le démontre. Une région entourée d'un anneau de $5$ autres exige $4$ couleurs. Le théorème des quatre couleurs (Appel et Haken, 1976), admis, dit que $4$ suffisent toujours ; la page démontre que $6$ suffisent, en admettant qu'une région a toujours au plus $5$ voisines.

Le piège le plus courant est de croire que $4$ couleurs ne sont nécessaires que si $4$ régions se touchent deux à deux : la roue à cinq quartiers montre le contraire.