Un enigma sobre carreteras de un solo sentido, y los colores pintados en ellas.
Avraham Trahtman (1944–2024), matemático de la Universidad Bar-Ilan, resolvió en 2007 un problema de combinatoria conocido como el problema de la coloración de carreteras, planteado en 1970 por Roy Adler y Benjamin Weiss y enunciado como conjetura en 1977 por Adler, Goodwyn y Weiss. Su demostración se publicó en el Israel Journal of Mathematics en 2009. Associated Press informó del resultado en marzo de 2008. Murió en Jerusalén el 17 de julio de 2024.
Imagine una red de carreteras de un solo sentido. El mismo número de carreteras sale de cada cruce, dos, digamos, y desde cualquier cruce alguna ruta conduce a todos los demás. Las longitudes de las rutas cerradas de la red no comparten ningún factor común mayor que uno. Ahora pinte las carreteras de modo que las que salen de un cruce lleven todas colores distintos: en cada cruce, una roja y una azul.
Un viajero parte de algún cruce y sigue una lista de colores, tomando en cada cruce la carretera del color indicado. La pregunta, planteada en 1970 y enunciada como conjetura en 1977, era si las carreteras pueden pintarse siempre de modo que una sola lista de colores lleve a todo viajero, desde el cruce en que haya comenzado, al mismo cruce.
Según el relato de la AP, docenas de personas lo habían intentado y fracasado. Weiss, que lo había planteado, pasó ocho años en ello él mismo.
En 2007 Avraham Trahtman, entonces de sesenta y tres años y enseñando en la Universidad Bar-Ilan, lo resolvió. La AP informó que escribió la solución a lápiz, en ocho páginas cortas, y que le había llevado un año. Un colega, Stuart Margolis, llamó al resultado inesperado y contraintuitivo. Weiss dijo que le daba gran alegría ver su problema resuelto.
Para cualquier red de este tipo, las carreteras pueden colorearse de modo que una lista de colores, seguida desde cualquier cruce, termine en el mismo cruce.
Trahtman siguió trabajando en una pregunta vecina: cuán larga debe ser la lista más corta de ese tipo, para una red de n cruces. Jan Černý la planteó en 1964, y un recuento de Mikhail Volkov, publicado en agosto de 2025, todavía la enumera como no resuelta. Trahtman publicó varios textos afirmando haberla demostrado. Volkov registra que en un correo electrónico dirigido a él con fecha del 10 de febrero de 2024, Trahtman escribió que había encontrado un error en esa demostración y esperaba corregirlo.