La matemática detrás de los juegos de ingenio y las redes sociales

Königsberg fue una ciudad alemana fundada a comienzos del siglo XIII, que tras la segunda Guerra Mundial pasó a formar parte de la entonces Unión Soviética y fue rebautizada como Kaliningrado. Pero independientemente de sus ajetreos históricos, este enclave tuvo un papel protagónico en un problema matemático clásico: los puentes de Königsberg.

El planteo es simple. Dentro de los límites de la ciudad, el río Pregel se bifurca y reconecta de tal modo que genera una isla en el interior de la urbe. Este sector está comunicado con el resto de la localidad por siete puentes. ¿El desafío? Saber si era posible recorrer todos una sola vez, partiendo y terminando en el mismo lugar.

En 1736, el matemático y físico Leonhard Euler demostró la imposibilidad de transitar un camino con esas condiciones y de esa manera dio uno de los primeros impulsos a lo que actualmente se conoce como Teoría de Grafos, un área de la geometría que estudia las propiedades de los objetos formados sólo por puntos y segmentos que los unen.

Lo que hizo Euler fue “modelizar” el planteo, esto es, convertir un problema de la vida cotidiana en uno matemático. Para ello, sustituyó las zonas de tierra firme con un conjunto de puntos y trazó todas las conexiones posibles de los puentes con una serie de líneas.

A partir del análisis de este caso, Euler descubrió que la característica excluyente para poder efectuar el trayecto es que todos los vértices del gráfico sean pares (es decir, el número de aristas que confluyen en él sea par) o que a lo sumo existan dos vértices impares (donde converja una cantidad impar de aristas).

“Este principio obedece a que si se quiere recorrer todos los puentes exactamente una vez, indefectiblemente los vértices deben ser pares, porque se ingresa por una arista y se sale por la otra. Esto se aplica a todos los vértices, excepto en el que se empieza o termina”, explica Leandro Cagliero, docente de la Facultad de Matemática, Astronomía y Física de la Universidad Nacional de Córdoba e investigador del área Teoría de Lie.

Desde los puentes de Königsberg hasta las redes sociales, pasado por los recorridos del transporte público, las vías férreas, el tendido eléctrico, las rutas que conectan ciudades y las antenas telefónicas, la Teoría de Grafos aporta soluciones a complicaciones de la vida real.

“Una situación concreta que puede resolver esta rama de la geometría es identificar el camino más corto que debe efectuar una noticia en Facebook para llegar a todos los usuarios de la red”, señala Cagliero. Y completa: “Si todos mandan una noticia a la totalidad de sus contactos, entonces cada uno recibirá miles de veces la misma información. La idea es conocer, con buena aproximación, el mínimo número de personas a las que cada usuario debe remitirle el texto de modo que todos los integrantes de la comunidad se enteren del tema y accedan al mensaje una única vez”.

Pintando mapas

La Teoría de Grafos está relacionada con una rama de la geometría denominada “Topología”, que estudia las propiedades que se mantienen invariables cuando los objetos geométricos se mueven como si fueran de goma.

En matemática, otro de los problemas topológicos tradicionales fue enunciado por Francis Guthrie en 1852, pero resuelto recién 1976, y con la ayuda de una computadora, por Kenneth Appel y Wolfgang Haken, de la Universidad de Illinois. En este caso, el reto era saber cuál era el mínimo número de colores necesarios para pintar las regiones de cualquier mapa, de manera que cada una tuviera un matiz diferente del que poseían sus zonas adyacentes (en este caso, las áreas limítrofes deben compartir una frontera, no basta con que se unan en un punto).

Guthrie, estudiante del University College de Londres, había elaborado una conjetura sobre el tema mientras trabajaba en la cartografía de Inglaterra y pensaba que cuatro colores eran suficientes. Su postulado, conocido como el “Teorema de los cuatro colores”, fue analizado por un sinnúmero de matemáticos de su época.

En 1879, Alfred Kempe, un abogado y matemático, anunció que había logrado demostrar la validez del teorema: su verificación fue publicada en la revista Nature de julio de ese año. Sin embargo, una década más tarde Percy Heawood encontró un error en esa demostración.

Si bien posteriormente se probó con relativa facilidad que cualquier mapa puede ser coloreado a lo sumo con seis tonalidades, e incluso con cinco, la demostración de que sólo cuatro son suficientes demoró mucho más. Recién en 1976, Appel y Haken pudieron hacerlo, pero con la ayuda de un ordenador. De todos modos, todavía algunos matemáticos consideran que la conjetura no ha sido rigurosamente demostrada, ya que no consideran válido el uso de la computadora para su resolución.

En la vida diaria, un caso cotidiano de coloreo es el Sudoku, un juego de ingenio japonés que consiste en distribuir estratégicamente números del uno al nueve en las 81 casillas de una cuadrícula. La condición es que en ninguna hilera –vertical u horizontal– se repita un mismo dígito. Se trata de un traspolación del coloreo de mapas, donde los números pueden ser reemplazados por matices.