1. Cuatro colores bastan, y tres no siempre alcanzan
La regla para colorear es sencilla: dos regiones que comparten un tramo de frontera deben llevar colores distintos. Si solo se tocan en un punto, como las esquinas de un tablero de ajedrez, no cuentan como vecinas[4]. Con esa regla, tres colores no siempre bastan. Dibuja un círculo, pártelo en tres sectores como una pizza (A, B y C) y rodéalo con un anillo (D). Los tres sectores tocan el anillo y también se tocan entre sí en el centro. Por eso, cada región toca a las otras tres, así que necesitas cuatro colores distintos.
¿Habrá mapas que pidan cinco o más? El teorema de los cuatro colores dice que no, siempre que el mapa esté dibujado en un plano (o en una esfera). Hoy se acepta como teorema, aunque la forma de demostrarlo siguió discutiéndose[4]. La condición del plano importa: sobre la superficie de un donut (un toro) existen mapas que necesitan siete colores[4]. Falta ver cómo se llegó a esa certeza, y qué tiene de raro la prueba.
2. Cómo empezó la pregunta en 1852 y por qué probar mapas no demuestra nada
Según MacTutor, el sitio de historia de las matemáticas de la Universidad de St Andrews, la pregunta llegó a la matemática por un estudiante, Francis Guthrie, que se la planteó a su hermano Frederick. Frederick se la llevó a su profesor Augustus De Morgan. El 23 de octubre de 1852, el mismo día en que se la plantearon, De Morgan escribió a su colega William Rowan Hamilton, en Dublín, contándole la duda: ¿se podría inventar un mapa que necesitara cinco colores o más?[1] Hamilton le contestó tres días después que no pensaba ponerse pronto con aquel «cuaternión de colores»[1].
Pintar mil mapas y comprobar que cuatro colores alcanzan no resuelve el problema. Quien afirma algo sobre todos los mapas posibles necesita una explicación que demuestre que funciona para todos, porque el mapa número mil uno podría ser justo el que falla.
3. Una prueba aplaudida en 1879 que tenía un fallo, descubierto 11 años después
En 1879 el matemático Alfred Kempe anunció una demostración en la revista Nature (17 de julio) y publicó el artículo ese mismo año[1]. Fue muy elogiada. En 1890 Percy Heawood demostró que tenía un error[1]. Wikipedia señala que el fallo tardó unos 11 años en aparecer[4].
Heawood no se quedó solo en destruir. Con la idea de Kempe, que sí servía en parte, demostró que cinco colores siempre bastan (el teorema de los cinco colores)[1]. Entre cuatro y cinco hay solo un color de diferencia, pero ese último color resistió hasta 1976.
4. 1976: Appel y Haken usan cálculo automático para revisar miles de casos
Kenneth Appel y Wolfgang Haken, de la Universidad de Illinois, anunciaron la solución el 21 de junio de 1976[4]. Su razonamiento se apoya en una idea de «supongamos lo contrario». Si existiera un mapa que no se pudiera pintar con cuatro colores, habría uno con el menor número posible de regiones. Para descartarlo hay que probar dos cosas:
- Inevitabilidad: todo mapa así contiene alguna pieza de una lista finita de «configuraciones» (pequeños grupos de regiones vecinas).
- Reducibilidad: si un mapa contiene una de esas piezas, se puede encoger esa parte para obtener un mapa más pequeño; y de una coloración con cuatro colores del mapa pequeño se obtiene una del grande.
Si todas las piezas de la lista son reducibles, el mapa más pequeño que fallaba no puede existir. Las fuentes dan cifras algo distintas: MacTutor habla de unas 1.500 configuraciones y de unas 1.200 horas de cálculo[1]; Wikipedia cuenta 1.834 configuraciones reducibles, luego reducidas a 1.482, con más de mil horas de cálculo, y añade que la parte de inevitabilidad ocupaba más de 400 páginas, revisadas a mano[4]. Sea cual sea la cifra exacta, era una cantidad de casos que ninguna persona podía repasar sola.
5. ¿Cuenta como demostración algo que una persona no puede revisar paso a paso?
Había que fiarse de la máquina. Robertson, Sanders, Seymour y Thomas escribieron en 1994 que la prueba de Appel y Haken «no ha sido plenamente aceptada» y que había dudas por dos razones.[2]. Gonthier recuerda que fue la primera prueba de un problema antiguo hecha con un programa, con un análisis de casos que, literalmente, llegaba a mil millones de casos que no se podían hacer a mano[3].
Hubo dos respuestas. En 1994 (versión revisada en 1997) Robertson y sus colegas dieron otra prueba, también con ayuda de la máquina, pero más simple. Según Wikipedia, redujo las configuraciones a 633, aunque las dos partes siguen necesitando cálculo automático[2][4]. Y Georges Gonthier tradujo la demostración al lenguaje del asistente de pruebas Coq, que comprueba cada paso lógico. Entonces solo hay que confiar en un núcleo pequeño del programa, y no en toda la cadena de programas y máquinas[3][4].
Hoy la mayoría de los matemáticos acepta el teorema. Sin embargo, la prueba de los cuatro colores abrió un debate sobre cuánto puede confiarse en una demostración que depende del cálculo automático.
6. Cómo comprobar tú mismo la idea de los cuatro colores
Puedes explorar el problema con lápices y papel. Dibuja un mapa con muchas regiones irregulares y píntalo con cuatro colores; cuando te atasques, prueba a cambiar el color de una región vecina para ver si puedes colorear la que te falta, una idea parecida a la que usó Kempe. Después piensa en esto: hemos dibujado cuatro regiones que se tocan todas entre sí. ¿Puedes dibujar cinco regiones planas que se toquen todas entre sí? Inténtalo y mira por qué se atasca; es la puerta de entrada al teorema de los cinco colores. Si quieres leer más, la página de MacTutor cuenta la historia con calma[1] y el informe de Gonthier muestra cómo funciona una prueba comprobada por una máquina[3].