De acuerdo a la Wikipedia, en 1852, el estudiante Francis Guthrie, planteó el problema de colorear un mapa con solamente cuatro colores. En términos generales, se establece el problema como: “Dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes, de forma que no queden regiones adyacentes con el mismo color”. Cabe señalar que las regiones adyacentes comparten no solo un punto, sino todo un segmento de borde (frontera) en común.
Por ejemplo, se sabe que tres colores son suficientes para mapas simples, pero en algunos casos ya es necesario un cuarto color, y esto ocurre cuando una región a colorear queda encerrada por un número impar de regiones que se tocan formando un ciclo. Antes del problema de los cuatro colores, ya se había formulado el problema de colorear un mapa con cinco colores, cuya demostración resulta corta y elemental. La prueba la hizo Headwood en el siglo XIX.
Sin embargo, la conjetura, atribuida a Guthrie se le comunicó a Augustus de Morgan. Esta se hizo famosa por la declaración de Arthur Caley, en 1878, en el sentido que ya estaba trabajando en ella. 120 años después de haber descubierto el teorema de los cuatro colores, fue resuelto por Kenneth Appel y Wolfang Haken.
El teorema de cuatro colores fue demostrado con la ayuda de una computadora. Sin embargo, los matemáticos habrían esperado una demostración analítica, como la que vemos en los libros de cálculo, de teoría de números, etcétera. En este caso, la computadora, el algoritmo utilizado y el compilador usado podrían ponerse en tela de juicio como buena la demostración. Aparentemente hay muchos detalles que no pueden ser revisados por los seres humanos. La cuestión es que aquí se usa el poder de la fuerza bruta para dar con todos los posibles casos. Así entonces, sólo queda aceptar la exactitud del programa en el cual se ejecutó la prueba.
Además, dicen los matemáticos más puros, es que la demostración no tiene elegancia: “una buena prueba matemática es similar a un poema —¡pero esto es una guía telefónica!”
Pero como sea, ya a alguien se le ocurrió hacer un juego basado en este curioso teorema de la teoría de grafos. ¿Hasta qué nivel puede usted colorear un mapa sin que dos regiones adyacentes tengan el mismo color? Al momento de escribir esto, voy en el nivel 11. Se pasa un buen rato.
Referencias: