Los siete puentes de Königsberg
Imagine que usted es miembro de un gremio de artesanos en extinción conocido como los coloreadores de mapas, y tiene ante sí un mapa plano de las Reticuladas Regiones de Convolúcide. El servicio de publicaciones de la universidad que le ha contratado pasa una mala época y usted se pregunta si podrá colorear el mapa con, a lo sumo, cuatro colores, asegurando, por supuesto, que los países vecinos que tengan un trozo de frontera común estén pintados en distinto color. El teorema de los cuatro colores garantiza que usted podrá cumplir con esta tarea sin importar cuantos países haya ni como estén dispuestos, siempre y cuando sean regiones conexas (esto es, no puede haber un pedazo de Esquizostán aquí y otro mil kilómetros más allá).
La conjetura de que para un mapa plano basta con cuatro colores fue formulada a mediados del siglo XIX, pero a pesar del interés que se puso en ello, quedó sin resolver hasta 1976, cuando los matemáticos norteamericanos Kenneth Appel y Wolfgang Haken demostraron que bastaban efectivamente cuatro colores. Anteriormente se había podido demostrar que como máximo hacían falta siete colores para pintar mapas sobre la superficie de un toro (una figura en forma de cámara de neumático), pero como la gente no suele dibujar mapas sobre roscones, este resultado carecía del atractivo natural del teorema de los cuatro colores.
Para demostrar el teorema de los cuatro colores hace falta un ordenador para poder examinar la miríada de posibilidades asociadas a los diversos tipos de configuraciones de mapas. Se trata de un nuevo progreso que, a primera vista, está reñido con la idea misma de demostración matemática. Tal y como se ha entendido tácitamente desde el tiempo de los griegos, las demostraciones han de ser comprensibles y verificables por los humanos. Además han de ser lógicamente convincentes. (Véase la entrada sobre QED). Una demostración como la del teorema de los cuatro colores, que precisa de un uso tan generalizado de ordenadores, no es comprensible ni verificable en el mismo sentido que otras demostraciones matemáticas. Ni tampoco es lógicamente cerrada. Aunque la probabilidad de error en una configuración dada sea mínima, el número de permutaciones y ordenaciones que hay que examinar es tan inmenso que sólo podemos concluir que el teorema es probablemente verdadero. Pero «probablemente verdadero» no es lo mismo que «demostrado concluyentemente».
Algunos matemáticos han observado que en la teoría de grupos hay algunos teoremas tan complicados y largos que se les podrían plantear las mismas objeciones aunque no hagan falta ordenadores para demostrarlos. Como quiera que uno considere este asunto, resulta claro que la demostración del teorema de los cuatro colores no es elegante, convincente ni natural. Ciertamente, no forma parte de lo que el matemático Paul Erdös llama El Libro de Dios, un conjunto de demostraciones ideales que tienen estas propiedades. A pesar de todo, es una solución impresionante de un viejo problema.
Desgraciadamente, las secuelas matemáticas que ha traído el resultado no han sido tan impresionantes como las de otro viejo enigma planteado por Leonhard Euler, el problema de los puentes de Königsberg. Euler empezó su clásico artículo de 1736 (que muchos toman como punto de partida de la combinatoria) hablando acerca de la distribución de la ciudad de Königsberg, en Prusia oriental. La ciudad se asienta en las riberas del río Pregel, con dos islas en medio. Las diversas partes de la ciudad estaban unidas por siete puentes y los domingos la gente solía pasearse por ellas. La cuestión que se planteaba era si los habitantes de esa ciudad podían salir de su casa y volver a ella después del paseo habiendo atravesado cada puente del río una sola vez. Euler demostró que tal ruta no existía. La idea fundamental de la demostración consistía en que el número de entradas de dicha ruta a cada parte de la ciudad tendría que ser igual al número de salidas, lo cual implicaría que cada parte de la ciudad ha de tener un número par de puentes, condición que no se daba en Königsberg.
Los siete puentes de Königsberg
Euler representó las distintas partes de la ciudad por puntos y los puentes que las unían por líneas. El conjunto de puntos y líneas (o de vértices y aristas) resultante forman un grafo, y en el resto de su artículo Euler estudió el problema general siguiente: ¿en qué grafos de este tipo es posible encontrar un camino que pase sólo una vez por cada línea hasta regresar al punto de partida? (Obsérvese que, contrariamente a lo que sucede en el caso de Königsberg, es posible encontrar dicho camino para un grafo en Estrella de David, construido por superposición de dos triángulos, uno apuntando hacia arriba y otro un poco más caído apuntando hacia abajo. Nótese también que de cada vértice de este último grafo parte un número par de aristas).
Grafo de la ciudad según Euler
Esta manera aparentemente ingenua de representar relaciones matemáticas por medio de puntos y líneas que los unen es actualmente un útil indispensable en la teoría de grafos. Puede servir, por ejemplo, para representar la red de relaciones entre un grupo de personas (las líneas unen a los que se conocen), el árbol de todos los posibles resultados de una sucesión de elecciones, los emparejamientos en rueda de un torneo deportivo, las conexiones de un circuito integrado y muchas otras cosas. Por contra, el teorema de los cuatro colores parece ser un callejón sin salida.
Es imposible predecir si un problema traerá nuevos progresos y sugerirá nuevas ideas o si llevará a una vía muerta. ¿Cuál de los dos acertijos siguientes es un callejón sin salida?
Tómese un entero positivo y, si es par, divídase por 2, pero si es impar multiplíquese por 3 y añádasele 1. Aplíquese la misma regla al entero resultante e itérese el proceso. La sucesión generada a partir de 11 es: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, …, mientras que la generada por 92 es: 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, … La cuestión es si cualquier número positivo acaba por caer en el ciclo 4-2-1 y, aunque se cree que esto es cierto, nadie ha podido demostrarlo todavía.
El segundo problema se puede formular en términos de invitados a un pequeño banquete. La cuestión es la siguiente: ¿Cuál es el menor número de comensales necesario para asegurar que al menos 3 de ellos se conozcan entre sí o al menos 3 de ellos no se conozcan? (Se supone que si Marta conoce a Jorge, entonces Jorge conoce a Marta). Se puede ver fácilmente que la respuesta es 6 tomando uno de los invitados al banquete, Juan. Como conoce o no conoce a cada uno de los otros 5 invitados, seguro que conoce por lo menos a 3 de ellos o no conoce por lo menos a 3 de ellos. Supongamos que Juan conoce a 3 comensales (en el caso de que no conozca por lo menos a 3 el razonamiento sigue un camino análogo) y pensemos en las posibles relaciones entre ellos. Si algún par entre ellos se conocen, éstos y Juan forman un grupo de 3 comensales que se conocen entre sí. Y por otra parte, si ninguno de los 3 conocidos de Juan conoce a los otros dos, ellos mismos ya forman un grupo de 3 comensales que no se conocen. Por tanto 6 son suficientes. Para ver que 5 comensales no bastan, imaginemos otra vez a Juan en una reunión de esta clase donde conoce exactamente a 2 de los otros 4 comensales y que cada uno de ellos conoce a una persona distinta de las que Juan no conoce.
No hay ningún conjunto de 3 personas que se conozcan entre sí, ni tampoco un conjunto de 3 personas que no se conozcan
En un metanivel la pregunta es: ¿cuál de las dos preguntas conduce a algo más y cuál no? La respuesta es que, aunque desde un punto de vista práctico ninguna de las dos sirve de gran cosa, la primera es un callejón sin salida (al menos por ahora), mientras que la segunda lleva a una rama completamente nueva de la combinatoria, la teoría de Ramsey. Recibe este nombre por el matemático inglés Frank Ramsey y se ocupa de encontrar el mínimo número de elementos necesarios que satisfacen varias condiciones combinatorias simples. Hay un sinnúmero de problemas que son terriblemente fáciles de enunciar y aún no están resueltos, siquiera por la fuerza bruta de los métodos informáticos. Uno de tales problemas es la generalización del problema anterior que pregunta el mínimo número de comensales necesarios para garantizar que haya al menos 5 invitados que se conozcan entre sí o al menos 5 que no se conozcan.
Un ejercicio final. El teorema de los cuatro colores dice que como máximo hacen falta cuatro colores para pintar cualquier mapa plano. Hay varios mapas pequeños esencialmente distintos que muestran que por lo menos hacen falta cuatro colores. Dibuje uno.
Mapa que precisa de cuatro colores. Cuatro colores son siempre suficientes