El teorema de los cuatro colores

El problema de los cuatro colores

Yo sé que usted nunca tuvo que colorear un mapa desde que dejó el colegio primario. Y ni siquiera estoy tan seguro de que hubiera sido el caso. De hecho, no creo que los chicos de hoy tengan que colorear mapas “a mano”, aunque uno nunca sabe. 

El hecho es que hay un teorema que tuvo a los matemáticos muchos años sin encontrar la solución. Y se trató de lo siguiente: supongamos que uno tiene un mapa. Sí, un mapa. Un mapa cualquiera, que ni siquiera tiene que corresponder con la realidad de una región. 

La pregunta es, “¿cuántos colores hacen falta para colorearlo?”. Sí: ya sé. Uno tiene entre sus “pinturitas” o en la computadora, muchísimos colores. ¿Por qué preguntarse cuántos colores distintos son necesarios, si uno puede usar muchos más de los que necesita? ¿Para qué podría servir calcular una “cota” máxima? Y en todo caso, ¿qué tiene que ver el número cuatro? 

El teorema de los 4 colores: Si G es un grafo plano, entonces X(G) ≤4

La Conjetura de los Cuatro Colores surgió de la siguiente manera: Francis Guthrie era un estudiante de una universidad en Londres. Uno de sus profesores era Augustus De Morgan. 

Francis le mostró a su hermano Frederick (que también había sido estudiante de De Morgan) una conjetura que tenía con respecto a la coloración de unos mapas y, como no podía resolver el problema, le pidió a su hermano que consultara al renombrado profesor. 

De Morgan, quien tampoco pudo encontrar la solución, le escribió a Sir William Rowan Hamilton, en Dublín, el mismo día que le hicieron la pregunta, el 23 de octubre de 1852: 

“Un estudiante me pidió que le diera un argumento sobre un hecho que yo ni siquiera sabía que era un hecho, ni lo sé aún ahora. El estudiante dice que si uno toma una figura (plana) cualquiera y la divide en compartimentos pintados con diferentes colores, de manera tal que dos adyacentes no tengan un color en común, entonces él sostiene que cuatro colores son suficientes”. 

Hamilton le contestó el 26 de octubre de 1852 y le dijo que no estaba en condiciones de resolver el problema. 

De Morgan continuó pidiendo asistencia a la comunidad matemática, pero nadie parecía encontrar una respuesta. 

Cayley, por ejemplo, uno de los matemáticos más famosos de la época, enterado de la situación, planteó el problema a la Sociedad de Matemática de Londres, el 13 de junio de 1878, y preguntó si alguien había resuelto la Conjetura de los Cuatro Colores. 

El 17 de julio de 1879, Alfred Bray Kempe anunció en la revista Nature que tenía una demostración de la Conjetura. Kempe era un abogado que trabajaba en Londres y que había estudiado matemáticas con Cayley en Cambridge. Cayley le sugirió a Kempe que enviara a publicar su Teorema al American Journal of Mathematics en donde fue publicado en 1879. A partir de ese momento, Kempe ganó un prestigio inusitado y su demostración fue premiada cuando lo nombraron miembro de la Sociedad Real (Fellow of the Royal Society) en donde actuó como tesorero por muchísimos años. Es más: lo nombraron “Caballero de la Reina” en 1912. 

Kempe publicó dos pruebas más del ahora Teorema de los Cuatro Colores, con versiones que mejoraban las demostraciones anteriores. Sin embargo, Percy John Heawood, en 1890 encontró errores en las demostraciones de Kempe. Si bien mostró por qué y en dónde se había equivocado Kempe, Heawood probó que con cinco colores alcanzaba para colorear cualquier mapa. Kempe aceptó el error ante la sociedad matemática londinense y se declaró incompetente para resolver el error en la demostración, en su demostración. 

Todavía en 1896, el famoso Charles De la Vallée Poussin encontró también el error en la demostración de Kempe, aparentemente ignorando que Heawood ya lo había encontrado antes. Heawood dedicó 60 años de su vida a colorar mapas y a encontrar potenciales simplificaciones del problema (la más conocida dice que si el número de aristas alrededor de cada región es divisible por 3, entonces el mapa se puede colorear con cuatro colores), pero no pudo llegar a la prueba final. 

El problema seguía sin solución. Muchos científicos en el mundo le dedicaron buena parte de sus vidas a probar la Conjetura sin suerte. Y obviamente, hubo mucha gente interesada en probar lo contrario. Es decir: encontrar un mapa que no se pudiera colorear con cuatro colores. 

Recién en 1976 (sí, 1976, hace sólo 40 años) la Conjetura tuvo solución y pasó a ser, nuevamente, el Teorema de los Cuatro Colores. La demostración corrió por cuenta de Kenneth Appel y Wolfgang Haken, quien con el advenimiento de las computadoras, lograron probar el resultado. Ambos trabajaban en la Universidad de Illinois en Urbana, en la localidad de Champaign. 

Kenneth Appel, demostró el teorema de los cuatro colores junto a W. Haken en 1976

Usaron más de 1200 horas de las computadoras más rápidas que había en la época hasta poder demostrar la conjetura. Tanto es así, que el Teorema de los Cuatro colores constituye el primer caso en la historia de la matemática, en donde la computadora ha tenido una incidencia tan fuerte, como que permitió que un resultado que venía evadiendo a los matemáticos durante más de un siglo fuera resuelto. 

Naturalmente, la demostración trajo gran desazón en el mundo de la matemática, no porque se esperara que el resultado fuera falso (en realidad, todo lo contrario) sino porque era el primer caso en donde la máquina (en algún sentido) estaba superando al hombre. ¿Cómo no poder encontrar una demostración mejor? ¿Cómo no poder encontrar una demostración que no dependiera de un agente externo? 

Es que los cálculos más optimistas establecen que para poder comprobar lo que hicieron Appel y Haken “a mano”, por una persona que le dedicara 60 horas por semana, necesitaría ¡cien mil años! para cumplir con la misma tarea. Los detalles de la demostración fueron publicados en dos papers que aparecieron en 1977. Muchos matemáticos, aún hoy, no aceptan como válida esa demostración. En todo caso, aceptan decir que hay indicios muy fuertes para suponer que el Teorema es cierto, pero hasta que no haya una demostración que no requiera el uso de las computadoras, varios integrantes de la comunidad no dan por cerrado el caso. 

Lo notable es que los seres humanos, dos en este caso, lograron reducir el problema a casos particulares. Muchos casos, que quizás hubieran llevado varias vidas para comprobar. Las computadoras hicieron el resto, pero lo que quiero enfatizar acá es que sin el hombre, las computadoras no hubieran sabido qué hacer, ni para qué.

Solo hacen falta 4 colores para colorear un mapa, por complejo que sea. Compruébelo: http://t.co/KvnSpHvWi7 #ja140 pic.twitter.com/b3CNnehPSg

— Jamessi (@jamessi_) 21 de junio de 2015

Por Adrian Paenza

Funtes relacionadas en este blog.

Historia del Problema de los cuatro colores.

[VÍDEO] En Derivando

A simple vista no parece un problema matemático, ¡pero lo es! "¿Se puede colorear un mapa con cuatro colores distintos de tal manera que dos regiones adyacentes no tengan el mismo color? Vamos a salir de dudas con el famoso: Teorema de los cuatro colores"

Sobre la demostración

Una crítica que habla sobre la elegancia de la misma, comentada en la época de su publicación, dice:

«una buena prueba matemática es similar a un poema —¡pero esto es una guía telefónica!».

Fallecimiento de Kenneth Appel (2013)

Bueno estuve actualizando esta entrada antes de la respectiva publicación y encontré en Gaussianos.com a cerca del fallecimiento de Kenneth Appel, que se había enterado gracias a este post de Marta Macho en ZTFNews. Kenneth Appel, matemático estadounidense, falleció el pasado 19 de abril a la edad de 80 años. Aunque hizo alguna aportación a la teoría de grupos, se le conoce principalmente por su demostración junto a Wolfgang Haken del teorema de los cuatro colores. En este obituario (en inglés) tienes más información.