El teorema de los cuatro colores

El teorema de los cuatro colores

2 Flares Twitter 2 Facebook 0 Google+ 0 Pin It Share 0 Email -- 2 Flares ×

El “teorema de los cuatro colores” asegura que solamente se necesitan cuatro colores diferentes para colorear un mapa cualquiera, de tal modo que dos regiones cualesquiera, que compartan una frontera común, tengan colores diferentes. Todos hemos visto algún mapa pintado de esa manera, pero por sencillo que parezca, determinar formalmente qué cuatro colores bastaban para colorear cualquier mapa ha mantenido ocupados a los más importantes matemáticos durante casi un siglo y medio. Esta es la historia.

A menudo los problemas que parecen demasiado simples resultan ser un hueso duro de roer cuando se intenta obtener una demostración matemática o una generalización que incluya todos los casos posibles. El coloreado eficiente de mapas es uno de ellos, y ha dado lugar al llamado “teorema de los cuatro colores”, que dice más o menos lo siguiente: "En un plano o en una esfera no se necesitan más de cuatro colores para colorear un mapa de forma que dos regiones adyacentes, es decir, que compartan una frontera ―una línea, el punto no cuenta― no queden coloreadas del mismo color". Seguramente has visto a lo largo de tu vida una gran cantidad de mapas, y sin importar la complejidad del mismo, siempre deben haberte mostrado los países o regiones que representan  usando solamente cuatro colores diferentes. Los fabricantes de mapas y los cartógrafos  sabían ya desde la época del renacimiento que les bastaban esa cantidad de colores para evitar que dos estados vecinos quedasen pintados con el mismo color, pero hasta el siglo XIX nadie creyó que este sistema tuviese relacionado con las matemáticas y -mucho menos aún- podía encontrarse una demostración que confirmase que era válido para cualquier tipo o tamaño de mapa.

El teorema de los cuatro colores

El asunto de los cuatro colores se convirtió formalmente en un problema matemático recién en 1850. El responsable de otorgar esa “categoría” al problema que enfrentaban los cartógrafos fue un estudiante inglés llamado Francis Guthrie, quien intuyó que el mecanismo empleado podía ser demostrado. Dado que el problema superaba su formación matemática, lo comentó con su hermano Frederick, quien había sido alumno del prestigioso matemático inglés Augustus De Morgan. Nacido en la India en 1806, De Morgan fue el primer presidente de la Sociedad de Matemáticas de Londres y tutor de la genial Ada Lovelace. Fue además el autor de las leyes fundamentales del álgebra de la lógica que llevan su nombre (“La negación  de la conjunción es equivalente a la disyunción  de las negaciones” y “La negación de la disyunción es equivalente a la conjunción de las negaciones”), por lo que a priori parecía la persona indicada para demostrar este teorema, que fue inicialmente conocido con el nombre de “problema de Guthrie”. Sin embargo, no pudo hacerlo.

El teorema de los cuatro colores

Lejos de olvidarse del problema que su alumno le había planteado, De Morgan consideró que “el problema del coloreado de mapas” era lo suficientemente interesante como para enviarle una carta a su colega Sir William Hamilton, quien era famoso por postular la estructura de los números cuaterniónicos. La leyenda cuenta que un día de 1843 Hamilton paseaba por el puente de Brongham, que cruza el canal Real de Dublín y, de repente, en un momento de inspiración, comprendió la estructura de los cuaterniones. De inmediato grabó sobre una piedra utilizando su navaja la idea. Los cuaterniones resultarían fundamentales para edificar la física relativista y cuántica, y para demostrar el teorema propuesto por Lagrange según el cual cualquier número entero puede escribirse como la suma de 4 cuadrados perfectos. Hamilton estaba en la cumbre de su carrera -todavía no había sido afectado por la adicción al alcohol que terminaría enterrándolo en 1865- por lo que De Morgan tenía la esperanza de fuese capaz de demostrar el “teorema de los cuatro colores”. Sin embargo, el matemático nunca se ocupó del problema, o bien lo intentó y no pudo resolverlo.

El teorema de los cuatro colores

Pero De Morgan nunca se olvidó del asunto, y con frecuencia se lo mencionaba a otros matemáticos. Incluso algunos historiadores creen que él es en realidad el autor de artículo anónimo incluido en  un ejemplar de 1860 de la revista Athenaeum que trata del problema de los cuatro colores, que se considera la primera referencia publicada sobre de dicha conjetura.  En 1860 el teorema ya había cruzado el océano, y varios matemáticos norteamericanos se habían puesto a trabajar para resolverlo. El filósofo y científico Charles Sanders Pierce fue uno de los que primero se ocupó de él en ese continente. En 1878 el matemático Arthur Cayley publicó un artículo llamado “On the colourings of maps”, en el que exponía a sus colegas el problema y enunciaba las dificultades que tenía su demostración. Al año siguiente la revista Nature anunció que el problema de los cuatro colores había sido resuelto por el abogado inglés Alfred Bray Kempe. Su demostración de que las regiones de un mapa plano cualquiera pueden pintarse con cuatro colores se incluyó en un ejemplar de la revista American Journal of Mathematics ese mismo año, y durante algún tiempo el problema se consideró resuelto. Habían transcurrido casi 30 años, durante los cuales las mentes más brillantes de la época atacaron el problema, para llegar a esta solución. Sin embargo, el fin de esta historia aún estaba por llegar.

El teorema de los cuatro colores

Alfred Bray Kempe fue nombrado Fellow de la Royal Society gracias a su trabajo, y se dedicó a ampliar los alcances de su artículo original. Otros matemáticos también colaboraron en esta tarea, y presentaron demostraciones alternativas. Incluso Lewis Carroll se interesó en el asunto y terminó desarrollando un juego para dos personas en la que cada jugador diseñaba un mapa con determinadas características, que el otro debía colorear ajustándose al uso de cuatro colores. Pero la dicha de Kempe se vio amenazada cuando en 1890 Percy John Heawood encontró un grave error en la demostración de abogado. Heawood escribió un artículo (“Map-colour theorem”) y presentó un mapa de 18 regiones que a, pesar de poder ser coloreado con solo cuatro colores, demostraba que el trabajo de Kempe distaba mucho de ser general. Poco tiempo después, un mapa “rebelde” de solo 9 regiones terminó con lo que quedaba de la demostración de Kempe. Nuevamente estábamos como en 1850, aunque  Heawood demostró que cualquier mapa puede colorearse con cinco colores y que tres no son suficientes, el número empírico de cuatro utilizado por los cartógrafos desde hacia siglos seguía resistiéndose a los esfuerzos de la comunidad matemática.

El teorema de los cuatro colores

Todo este revuelo sirvió para que el problema adquiriese tanta fama que se lo propuso a través de la  London Mathematical Society (Sociedad Matemática de Londres) como “un problema importante a resolver.”En 1976, ciento veinticuatro años después de que Guthrie les complicase la vida a cinco o seis generaciones de matemáticos, dos especialistas de la Universidad de Illinois (EEUU) utilizaron un ordenador Cray para colorear 1900 tipos de mapas distintos y -luego de trabajar durante 1200 horas- se comprobó que no era posible dibujar un mapa que no se pudiese pintar con solo cuatro colores. Pero, a pesar de su esfuerzo, Kenneth Appel y Wolfgang Haken no habían conseguido una demostración en el sentido matemático, solo utilizaron la “fuerza bruta” del Cray para comprobar una gran cantidad de mapas. Nunca podríamos estar seguros de la inexistencia de un retorcido diseño que escapase al teorema de los cuatro colores. Este dilema siguió torturando a los matemáticos durante dos décadas más, hasta que por fin -en 1996- Neil Robertson, Daniel Sanders, Paul Seymour y Robin Thomas, todos de la Escuela de Matemáticas del Instituto Tecnológico de Georgia (EEUU) encontraron una demostración que, al menos hasta hoy, es aceptada por todos sus colegas. Hubo que esperar 150 años para que el teorema de los cuatro colores, un problema que todos los cartógrafos habían resuelto en la práctica, pudiese ser demostrado matemáticamente.


  • ZeK005

    Muy buen dato y esto es asi ya que no existen en el mundo puntos donde se junten muchas fronteras al mismo tiempo (ejemplo el punto tripartito entre Paraguay, Brasil y Argentina). En este caso, los 3 paises deben tener colores distintos.
    Si existiera en el mundo (y no se si existen) una cuadruple frontera, entonces se necesitarian 4 colores obligatoriamente. Extrapolando se nota obviamente que si llegara a existir una quintuple frontera seria SI O SI necesario usar 5 colores. Entonces la pregunta resulta en…. ¿Existen puntos geograficos en el mundo que 4 o mas regiones compartan al mismo tiempo?

    • jp10

      EN un capitulo de los Simpsons, los simpson se unieron de las manos para que cada simpson estuviera en un estado.

      • Andros Emperor

        Aparte de que ese comentario no tiene nada que ver con el tema, la broma en esa escena de los Simpsons, está en que no hay ningún punto en EEUU en el que se crucen las fronteras de 5 estados. Así que lo que hacen es imposible de realizar en la práctica.

    • Ariel Palazzesi

      Hola Zek005!
      El tema queda resulto en el enunciado el problema:

      "En un plano o en una esfera no se necesitan más de cuatro colores para colorear un mapa de forma que dos regiones adyacentes, es decir, que compartan una frontera ―una línea, el punto no cuenta― no queden coloreadas del mismo color".

      Fijate que el "punto" no se considera. En caso de que 8 paises (o el número que quieras) tengan un solo punto en común (como el centro de una pizza cortada en 8 porciones), bastarian solo 2 colores….uno para un pais, el siguiente con el otro, y luego repetir hasta terminar. No se si soy claro sin mostrarte un dibujo, pero el problema de la "quintuple frontera" no existe, por que si o si deberia ser un punto, y esa situación está excluida en el enunciado.

      Un abrazo.

    • luchovl2

      Me parece que no, porque dice que no se consideran los puntos como fronteras, sólo líneas adyacentes.
      "que compartan una frontera ―una línea, el punto no cuenta―"

  • jesús

    Supongo que se refieren a mapas reales. Pues si es posible dibujar un mapa que no pueda ser dibujado con cuatro colores. Acabo de hacerlo ahora mismo.

    • jesús

      Corrigo mi comentario anterior, cometí un error asignando colores a mi mapa fictisio. Hasta ahora si que me parece imposible llegar a dibujar un mapa que necesite más de 4 colores.

  • Sebastianmr6

    El mapa donde está Brasil está malo, Venezuela y Brasil comparten el mismo color.

    • Cienfuegos

      Y Bolivia!

    • cristiano

      Es que Brasil tiene planes de expandir su territorio…

  • cronosferatu

    http://i30.tinypic.com/5osej4.jpg

    -El pais nº 4 rodeo a los demas paises.
    -Luego de una guerra entre los paises nº 2 y 3; 3 le permitio a 2 un pedazo de su tierra infertil para que 2 pueda hacer negocios con 4.
    -Pais nº 1 esta pintado ahi xD, aun en frontera con pais 3.
    -Pais ?, no sabe de que color pintarse.

    Creo que este mapa esta bien hecho, aun que tal vez haya algun error por ahi (dibujando el mapa me encontre con varios errores que tuve q arreglar).

    • Ariel Palazzesi

      Hola!
      Simplemente, pintas el del "?" de color violeta, y el bloque violeta que te queda a la derecha lo p¡ntas de marrón….. :)

      Creo que el error que cometiste fue pintar primero el cuadrado de violeta, y luego dibujar el interior. ;)

      Saludos!

      • lito

        si hacemos eso el pais 4 al ser marron toparia con el pais 2 que ya es marron, el coloco en su enunciado que el pais 4 rodea a todos los demas paises

    • Ardemion

      ya q me da lata ponerle colores y hacer un dibujo xD, lo digo con numeros
      [...]
      al final una imagen vale m{as que 1000 palabras XD

      http://i32.tinypic.com/2v1olzc.jpg

      saludos

    • ELF

      Efectivamente es correcto. Sin embargo el teorema se aplica a "países disjuntos", vamos que todos sus territorios forman una única área respecto a todos los demás. En tu caso el país 3 no cumple. ¿Existe algo así en el mapamundi político? Pues ni idea, aunque es cierto que hay situaciones parecidas a la que presentas en las que un territorio de un país queda completamente rodeado por el de un país vecino. Como prueba un botón: España tiene un pequeño territorio en el norte que está completamente rodeado por el territorio de Francia.
      Sin embargo todo esto no invalida el teorema.

  • mtqhatos

    Siguiendo la idea de cronosferatu aqui hay otra imagen

    http://i26.tinypic.com/2vba8sl.jpg

  • gunn

    A mi lo que me parece raro es que seamos capaces de crear un software que pinte 1900 mapas usando 4 colores, y no entendamos por qué el algoritmo que los pinta no puede hacerlo con 3 y que sobren colores si se usan 5. Es como crear una inteligencia artificial sin entender como funciona la mente humana. Me desconcierta.

  • Capitan Obvio

    Verdaderamente un pequeño gran detalle…. JAMAS, habia puesto atencion en los mapas coloreados que efectivamente muchos tienen solo 4 colores. Hoy he leido neoteo y he aprendido algo.

  • victor141516

    Acabo de hacer este mapa y no puede dibujarse con 4 colores:
    http://img85.imageshack.us/img85/1641/78428218.png

  • ecoronel

    Detrás de todo este tema de los mapas y el coloreo, existe toda un universo de teoría sobre grafos planares y coloreo, para aquellos que estén interesados pueden echarle un vistazo.

  • Vurucled

    Que curioso, yo de niño buscaba algo así (siempre perdía la mayoría de mis colores)… pero resulta que vivo en el estado de Oaxaca, en México, y colindamos con 4 estados distintos (Puebla y Veracruz al norte, Chiapas al este y Guerrero al oeste). Supongo que hay muchos casos como este, así que creo que esto de los 4 colores es insuficiente..
    http://www.pickatrail.com/jupiter/location/north_america/mexico/map/oaxaca.gif

    • Vurucled

      Perdón por el doble post, pero si se fijan en el mapa, hay estados que colindan hasta con otros 7 XD

      • jiman

        en el caso de la republica mexicana aplica perfectamente el teorema quieres ver la solucion???

        vicke_bass@hotmail.com

    • Ariel Palazzesi

      Hola Vurucled
      Dices que "colindamos con 4 estados distintos (Puebla y Veracruz al norte, Chiapas al este y Guerrero al oeste). Supongo que hay muchos casos como este, así que creo que esto de los 4 colores es insuficiente…"…pero estas equivocado: no hay ningun impedimento para colorear ese mapa con solo cuatro colores ;)
      Saludos!

      • Vurucled

        jajaja, es verdad, creo que tengo que encender bien mi cerebro antes de comentar X..D

    • DAZER

      hola compadrito!
      Primeramente un coordial, saludo, no pensaba encontrar algún "paisa". =D
      Bien, asi es nuestor estado y repleto a esto el DF,es algo con lo que tienes que plasmar con mas colores, ya que sus adyacentes son mucho mas que 3.
      Saludos, pero de cualquier manera es aplicable en muchisimos casos.

      =//DjCobra//-

      • DAZER

        te avientas los dibujos con arcoris
        jaja
        en diferentes formas!
        jajaja, saludos! Todo está en la mente, y la posibilidades son infinitas!
        Salu2!

  • Ardemion

    creo q luego de todo esto es necesario comentar algo.
    ESTO ESTÁ MATEMÁTICAMENTE DEMOSTRADO!
    jamás encontrarán un mapa que no pueda colorearse con al menos 4 colores, entiendanlo xD, es matemática, es así. fin.

    saludos ^^

    • abc

      Peru tiene 5 fronteras…

      • Eldras

        Pero no son adyacentes. ASi que dejando un color de por medio se pueden pintar dos del mismo color y que se sigan distinguiendo las distintas regiones.

  • Johnny

    Hola, si esta demostrado matematicamente, entonces debe haber una solución para el problema planteado por cronosferatu, en su mapa de ejemplo.

    Me parecion un buen punto.

  • Shingi

    El problema de cronosferatu esta resuelto… el teorema matematico indica que con 4 colores se puede pintar una seria de regiones que colinden, regiones separadas por limites claro esta, si ven el mapa de cronosferatu el pais que marca como rojo(3) tiene dos regiones diferentes, por ende se pueden pintar de colores diferentes como lo muestra Ardemion…

    la matematica del teorema no identifica si dos o mas regiones son un solo pais, solo que las regiones sean separas unas de las otras

    • mtqhatos

      y este como lo pintan, no veo modo de pintarlo con solo cuatro colores

      http://i26.tinypic.com/2vba8sl.jpg

      • albert_1714

        la zona azul de arriba a la izquierda la pintas de rojo y ya está resuelto…

      • mtqhatos

        ups, no lo había visto

        bueno ahora si me doy por vencido, extraña curiosidad esto de los colores, más que nada porque cuatro.

  • Cronosferatu

    Es cierto, es imposible encontrar un mapa con regiones colindantes que no se pueda pintar con solo 4 colores.

    Pero al intentarlo me encontre con esto xD:

    http://i31.tinypic.com/2n00oer.png

    Si se fijan la unica forma de pintar (?) segun el teorema es hacerlo con el color verde….
    Pero si lo hacemos..

    http://i32.tinypic.com/4sz6v4.png

    Parece que la otra region con color verde y (?) pertenecen a una misma; en este caso seria necesario pintarlo con otro color. (claro que si la region de color rojo sera mucho mas delgado se notaria mas, si me entienden)

  • Kniffe

    Bored.

    • PentagramaX

      troll a la vista!!!!

  • Crezio
    • mandybejar

      lo pintas se naranja

  • Ongas

    ¿Alguna demostración de este Teorema es ademas método de coloreado?
    Si no es asi, creo que tengo un método de coloreado/demo. ¿le interesa a alguien echar un vistazo?

  • pedro

    En un plano hay 4 cuadrados contiguos y alineados, cada uno con un color distinto, y bajo estos hay un rectángulo cuyo lado superior limita con todos esos cuadrados. Si se ocupan 4 colores en todas las áreas, ¿es posible que el rectángulo no repita ninguno de los colores de los cuadrados?