Ya lo decía Carl Sagan hace mas de 30 años "No existen preguntas estúpidas". El motivo de esta afirmación se debía básicamente a que cualquier pregunta, por trivial o superficial que parezca puede dar origen a un gran descubrimiento. Y de esto mismo se trata el post, de una pregunta "estúpida" que dio origen a una brillante teoría matemática.
De niños seguramente todos hemos coloreado algún mapa, ya sea por deber de la escuela o por simple pasatiempo. Un problema común al realizar esta tarea era la cantidad de colores que teníamos a disposición, pues deseábamos que nuestro mapa fuera tan colorido como fuera posible, pero ¿alguna vez te preguntaste cuántos colores eran suficientes para que cualesquiera países colindantes tuvieran colores distintos? Bueno, esto mismo se preguntó el matemático Francis Guthrie en 1852, recién graduado de la University College of London. Esta simple pregunta dio origen a uno de los problemas matemáticos más famosos, peculiares y controversiales de la historia.
Mapa de los Estados Unidos de América en el que se muestran los 4 estados que colindan en un solo punto: Utah (azul), Colorado (verde claro), Arizona (amarillo) y Nuevo México (verde).
De acuerdo a su experiencia, Guthrie conjeturó que serían necesarios solo 4 colores para colorear cualquier "buen" mapa. Con "buen mapa" quiso que ningún país podría encerrar a otros, ni que dos países tuvieran como frontera un solo punto, o que un país estuviera formado por partes separadas. Dado este criterio, por ejemplo, el mapa de Estados Unidos no es del todo un buen mapa, pues los estados de Utah, Colorado, Arizona y Nuevo México se unen en un solo punto, y además, el estado de Michigan está conformado por dos partes desconectadas (ve la imagen).
Al no poder estar seguro de su conjetura, Guthrie se lo preguntó a su hermano Frederik (quien estaba realizando sus estudios en Matemáticas). Como él también ignoraba la respuesta, recurrió a su mentor Augustus De Morgan (famoso por sus leyes en lógica), pero este último tampoco pudo dar respuesta a la cuestión. No fue sino hasta 1878 que el problema fue presentado de manera formal en la Sociedad Matemática de Londres. Un año despúes, Alfred Kempe, abogado y miembro de la sociedad presentó una supuesta prueba en la que afirmaba que tal como Guthrie había propuesto, cuatro era el número de colores suficientes para colorear cualquier buen mapa. Sin embargo, 11 años después se encontró un error en su argumento, y lamentablemente no fue fácil arreglarlo. No obstante, Kempe dio el primer gran paso hacia la demostración, tanto así que la gran mayoría de los avances que le siguieron, estaban basados en su trabajo. Más aún, nunca se había podido diseñar un mapa que requiriera de cinco o más colores… pero esto no significaba que no existiera.
Mapa de las 212 regiones de la República de Eslovenia coloreado con cuatro colores.
Matemáticos en Estados Unidos como George Birkhoff y Philip Franklin, y Heinrich Heesch en Alemania, lograron hacer mejoras al método de Kempe, y para no tratar con un infinito número de mapas, consideraron más bien conjuntos de mapas equivalentes, de manera que si la conjetura se probaba para uno de ellos, automáticamente lo hacía para sus equivalentes. Algunos avances que hicieron fueron afirmar que ningún mapa con más de 36 países necesita más de 4 colores y que el número de mapas a estudiar era de unos 10 000.
Convencido de que el problema tenía solución, Heesch decidió atacar el problema de una manera completamente inusual: por medio de ordenadores. Para ello, él y uno de sus estudiantes escribieron un programa de computadora que analizaba las posibles formas de colorear un mapa y determinar si requería de más de cuatro colores. Sin embargo, incluso con la ayuda de ordenadores, el tiempo de cómputo necesario para analizar todas las posibilidades era enorme (¡hasta 11 años!), y se dieron cuenta que comúnmente encontraban muchos errores que debían de ser corregidos manualmente. A pesar de no haber conseguido el éxito deseado, esta idea determinó el rumbo de la prueba final.
A inicios de 1970 Kenneth Appel y Wolfgang Haken comenzaron a estudiar el problema y lograron diseñar un algoritmo eficaz que acortaba por mucho el tiempo de cómputo. Finalmente, a mediados de 1976 y despúes de innumerables pruebas y errores, analizaron, en la Universidad de Illinois, unas 1500 configuraciones suficientes para mostrar la conjetura. Después de 1200 horas de cálculos (¡más de 7 semanas!), los resultados del ordenador fueron que no existían mapas que necesitaran más de 4 colores. Así, 124 años despúes, habían probado el teorema de los 4 colores.
Mapa creado por Martin Gardner y publicado en 1975 como broma del día de los inocentes. Fuente: Carnegie Mellon University.
La conjetura estaba demostrada, pero hubo cierto descontento acerca de la manera en la que se logró, pues en lugar de haber sido resuelta con algún elegante argumento matemático, se empleó la "fuerza bruta" de las computadoras. Además, se generó cierta desconfianza al no poder analizarse manualmente los cálculos realizados por el ordenador. Pero no importaba el método usado, la prueba era válida.
Desde entonces se han diseñado complejos mapas que aseguran necesitar más de 4 colores, pero estas aseveraciones han resultado ser falsas o simples bromas, como este publicado por Martin Gradner en Scientifc American en el que retaba a los lectores… ¿eres capaz de colorearlo con solo 4 colores?
Así que ahora ya sabes, si alguna vez necesitas colorear un mapa y solo posees 4 colores para hacerlo, puedes estar seguro de que es posible.
[/size] 
Comentar es agradecer.
Apoya la inteligencia colectiva.
Ayúdame a llegar a los 500 seguidores.
Ayúdame a recuperar la vieja directspace.
Dale a "Seguir"
Fuente: K. Appel, W. Haken, "La solución del problema de los cuatro colores", Investigación y Ciencia (edición en español de Scientific American), No.15, Diciembre de 1979.
0 comentarios:
Publicar un comentario