INTRODUCCIÓN
Los orígenes de este problema son muy antiguos. Los cartógrafos renacentistas sabían ya que les bastaban cuatro colores para colorear sus mapas de manera que dos países vecinos quedaran coloreados de distintos color, logrando así que sus mapas fueran claros y fáciles de entender.
Sin embargo, hasta el siglo XIX, a nadie se le había ocurrido que este hecho tuviera que ver con matemáticas y mucho menos que se podía o debía demostrar.
ENUNCIADO DEL TEOREMA
En un plano o en una esfera no se necesitan más de cuatro colores para colorear un mapa de manera que dos regiones vecinas, es decir, que compartan una frontera y no únicamente un punto, no queden coloreadas del mismo color.
Este problema se propuso en el año 1852 y no pudo resolverse sino hasta el año 1976.
HISTORIA DEL PROBLEMA
Parece ser que el llamado "problema de los cuatro colores" se convirtió formalmente en un problema matemático cuando en 1850 un estudiante inglés de Edimburgo, Francis Guthrie, a quien le gustaba dibujar y colorear mapas, se dio cuenta de que siempre podía iluminar correctamente los mapas sin usar más de cuatro colores. Intuyendo que esto podía ser demostrado, se lo contó a su hermano Frederick (que más tarde sería químico), quien había estudiado con un prestigioso matemático inglés de la época llamado Augustus De Morgan. Frederick se lo comunicó en 1852 a De Morgan quien no supo solucionar el problema pero le pareció suficientemente interesante como para enviarle una carta a otro prestigiado matemático inglés: Sir William Hamilton, quien decidió no hacerle caso al problema, hecho que nunca sabremos si sucedió porque no pudo resolverlo o porque le pareció intrascendente.
Durante muchos años, matemáticos y no matemáticos, expertos y novatos intentaron resolver el problema de los cuatro colores, es decir, demostrar que bastan cuatro colores para dar una coloración correcta a cualquier mapa. El problema de los cuatro colores se hizo tan famoso en el medio matemático, que en 1878 el matemático inglés Arthur Cayley lo propuso oficialmente a la Sociedad Matemática de Londres (London Mathematical Society), una de las sociedades de matemáticos más importantes del mundo en esa época, como un problema a resolver.
En 1879, el jurista y matemático inglés Sir Alfred Kempe publicó la que él creía ser una demostración. Un año más tarde hacía aparecer en la revista Nature un artículo con el algo infatuado título «Cómo iluminar un mapa con cuatro colores». Durante una decena de años, los matemáticos creyeron el problema resuelto, entonces en 1890, P. J. Heawood localizó un error fatal en la demostración de Kempe.Se entusiasmó Heawood tanto con el problema, que toda su vida la dedicó a estudiarlo a fondo. Por más de sesenta años trabajó en él desde ángulos muy distintos, obteniendo resultados interesantes que hicieron avanzar considerablemente la topología, pero no consiguió resolver el problema original. Entre otras cosas averiguó que para un mapa cualquiera en la superficie de un neumático (cuerpo geométrico denominado toro en Matemáticas), siete colores bastan, que para un mapa en la cinta de Möbius bastan seis...
Varios matemáticos más dieron demostraciones que resultaron tener errores, pero lo que sí se logró con el paso de los años y el trabajo de tanta gente, fue demostrar dos cosas fundamentales:
De manera que aunque no se había probado nada respecto a los cuatro colores por lo menos ya se sabía que con tres faltaba y con cinco sobraba, así el número cuatro era el candidato ideal...había entonces que probarlo o refutarlo.
En 1950 se sabía que cualquier mapa de menos de 36 países se puede colorear con cuatro colores. En los años cincuenta, Heinrich Heesch, profesor en Hannover, empezó a pensar que las ideas de Kempe, junto con la ayuda del computador, podrían tal vez conducir a una solución, pero, aunque presentía cómo se podría hacer la cosa, aún estaba lejos de la realización de su plan de trabajo. Desde 1950 a 1970 Heesch fue desarrollando las técnicas que han conducido a la solución.
Finalmente en 1976 (¡124 años después de que se había propuesto el problema!) dos matemáticos de la Universidad de Illinois en Estados Unidos, Kenneth Appel y Wolfgang Haken, usando una computadora Cray de segunda generación, analizaron 1900 posibles arreglos de regiones en el plano, o sea, analizaron 1900 tipos distintos de mapas. La computadora tardó 1,200 horas en correr un programa que tenía miles de líneas de largo, y para todos los mapas encontró una coloración en la que a lo más se usaban cuatro colores. ¡El problema había sido resuelto! ¿O NO?
Muchos matemáticos aceptaron esto como una prueba irrefutable, pero muchos otros argumentaron que eso no era una demostración matemática, la máquina había comprobado que una gran cantidad de mapas podían colorearse usando a lo más cuatro colores, ¿pero que tal sí existía un mapa, que la computadora no hubiera contemplado, que no podía colorearse de esa forma?
De nuevo surgieron objeciones. El proceso del ordenador, es decir los pasos internos del ordenador no podían seguirse ni comprobarse cuando la máquina los hacía; y para verificarlos "a mano", eran tantos, que habría hecho falta toda una vida para realizarlos. De modo que algunos matemáticos han tenido muchas reservas con respecto a esta demostración.La discusión continuó por veinte años, hasta que en 1996, los matemáticos Neil Robertson, Daniel Sanders, Paul Seymour y Robin Thomas, de la Escuela de Matemáticas del Instituto Tecnológico de Georgia, en Estados Unidos, publicaron una demostración, aparentemente correcta, del "teorema de los cuatro colores". Y así acaba la historia, pues hasta ahora nadie la ha refutado...
EJEMPLOS
Veamos un par de ejemplos:
Este mapa está bien coloreado pues dos países vecinos nunca están del mismo color. Los dos países amarillos sólo se tocan en un punto y por eso no se consideran vecinos. Lo mismo pasa con los dos países rojos.
En cambio, este mapa, no está bien coloreado pues hay dos países vecinos que están coloreados de azul.
Decir que bastan cuatro colores no quiere decir que siempre será necesario usarlos todos, hay mapas que pueden colorearse con tres e inclusive con dos colores, lo que quiere decir es que nunca será necesario usar cinco o más colores.
Este mapa se puede colorear con solo dos colores
Pero, en cambio éste no se puede colorear con dos colores, en este mapa es necesario usar 3 colores.
¿Podrías averiguar por qué?
Colorea estos mapas.
Para cada uno de ellos contesta las siguientes preguntas:
¿Cuántos colores usaste para colorear el mapa?
¿Cuál es el mínimo número de colores que se puede usar para colorearlo?
¿Qué cambios podrías hacerle al mapa para que se necesitaran menos colores al colorearlo?
¿Cuáles fueron los mapas más sencillos de colorear?
¿Cuáles fueron los más difíciles?
¿Podrías colorear este mapa con cuatro colores?
