Resuelven un problema matemático imposible durante 40 años

Un israelí de origen ruso ha resuelto un problema matemático que estaba pendiente de solución desde que se planteó hace casi cuarenta años.

El autor del hallazgo es Avraham Trakhtman, de 63 años, que emigró en los 70 a Israel desde la región de los Urales.

Con sólo su cerebro, un lápiz y un papel, el emigrante ha resuelto el ‘Problema de la Ruta Coloreada’ (Road Coloring Problem), que permanecía sin solución desde que lo planteó en 1970 un equipo de matemáticos dirigido por el profesor Binyamin Weis.

Aunque tiene varias versiones, la formulación más simple del problema es la siguiente: ¿Como alguien que llega por primera vez a una ciudad cuyas calles no tienen nombre puede encontrar una casa con indicaciones de «ahora a la izquierda, ahora a la derecha»?.

La respuesta de Trakhtman a ese enigma será publicada próximamente por el Diario Israelí de Matemáticas pero ya ha comenzado a circular entre los medios especializados.

Uno de quienes ya la conocen es el matemático Stuart Margolis, profesor de la Universidad Bar Ilan, que calificó la solución de «brillante, producto de un cerebro privilegiado», y destacó que su autor tiene un carácter «extremadamente tímido y modesto».

En el mundo de la teoría de grafos y los autómatas finitos, un viejo rompecabezas conocido como el Problema de la Ruta Coloreada (o Road Coloring Problem en inglés) ha sido uno de los desafíos más persistentes. Planteado en 1970 por los matemáticos Roy L. Adler, L. W. Goodwyn y Benjamin Weiss, este problema permaneció sin resolución durante 37 años, atrayendo el interés de expertos en dinámica simbólica, grafos y teoría de autómatas.

La pregunta central era sencilla en su enunciado, pero profunda en sus implicaciones: dado un grafo dirigido finito, fuertemente conectado y aperiódico (es decir, donde el máximo común divisor de las longitudes de sus ciclos es 1), con el mismo grado de salida en todos los vértices, ¿es siempre posible colorear las aristas con un número fijo de colores de manera que exista una secuencia de colores que lleve a todos los caminos posibles al mismo vértice, independientemente del punto de partida?

En términos más intuitivos, imagine un laberinto de calles unidireccionales donde cada intersección tiene el mismo número de salidas. El problema busca asignar colores a las calles (por ejemplo, rojo o azul) de forma que, siguiendo una misma secuencia de colores —como «rojo-rojo-azul»—, cualquiera termine en el mismo lugar, sin importar desde dónde empezó. Esto se conoce como una coloración sincronizante.

La solución llegó en 2007, de la mano del matemático israelí de origen ruso Avraham Naumovich Trahtman.

Tras emigrar a Israel en los años 90 y enfrentar dificultades para encontrar empleo académico —incluso trabajó como vigilante nocturno—, Trahtman resolvió el problema en apenas ocho páginas escritas a lápiz. Su prueba, publicada en 2009 en el Israel Journal of Mathematics, confirmó que sí existe siempre tal coloración bajo las condiciones mencionadas.

El resultado, ahora conocido como el Teorema de la Coloración de Rutas, no solo cerró una conjetura de larga data, sino que abrió puertas a algoritmos eficientes para encontrar dichas coloraciones, con aplicaciones en robótica, teoría de códigos y sincronización de sistemas.

Colegas como Stuart Margolis, de la Universidad Bar-Ilan (donde Trahtman finalmente obtuvo un puesto), describieron la solución como «brillante«, destacando la modestia y perseverancia del matemático.

Este avance recuerda que, en matemáticas, las grandes respuestas a menudo llegan de forma inesperada, incluso desde quien trabaja en la sombra.

El Problema de la Ruta Coloreada ya no es un enigma: es un teorema probado.