Tres investigadores demostraron hace diez años que siempre es posible resolver el popular juego con un máximo de 20 movimientos
JAVIER ARAMAYONA | HUGO PARLIER | ÁGATA A. TIMÓN
Cuando Ernố Rubik (Budapest, 1944) creó su famoso cubo en 1974, motivado por su pasión por la geometría espacial, no podía sospechar que lo que acababa de inventar sería uno de los objetos de diseño más icónicos y además el juguete más vendido de todos los tiempos. Y aun menos podría haber imaginado que, antes de convertirse en un fenómeno comercial, el cubo serviría de inspiración para la comunidad matemática, suscitando una serie de preguntas que resultaron tan complicadas de responder como fáciles de enunciar. Posiblemente la más importante de estas se resolvió justo hace 10 años, en julio de 2010. Entonces, tres investigadores demostraron que siempre es posible solucionar el juego con 20 movimientos o menos, independientemente de la posición de partida. Para ello utilizaron una combinación de matemáticas teóricas y el equivalente a 35 años de trabajo de un ordenador convencional, culminando un esfuerzo de investigación de más de 30 años.
¿Cómo puede un juguete motivar trabajos de investigación tan sofisticados? Una primera respuesta viene dada por los gigantescos números que encierra: hay 43 252 003 274 489 856 000 maneras de reordenar el cubo. Es difícil entender la magnitud de esta cifra. Es un número tan enorme que es imposible que la humanidad haya sido capaz siquiera de ver todas las configuraciones admisibles. Efectivamente, si los 1000 millones de cubos que se estima que se han producido desde 1980 hubieran sido utilizados desde ese año, a una velocidad de tres movimientos por segundo y sin pausas para comer ni para dormir, se habrían alcanzado, como mucho, 4 000 000 000 000 000 000 posiciones distintas. Aunque son muchísimas, aun son menos del 10% de todas las configuraciones posibles.
De hecho, ni los ordenadores más potentes son capaces de procesar esta cifra y, precisamente por ello, el razonamiento matemático se vuelve esencial. Así, el conjunto de configuraciones del cubo se puede interpretar como un grafo, es decir, algo parecido a un mapa de metro, una red social o una red neuronal, en la que hay nodos (estaciones de metro, personas o neuronas) y conexiones entre ellos (túneles que unen las estaciones, “amistad” entre personas de la red o sinapsis). En el cubo de Rubik, los nodos son las configuraciones y dos configuraciones están unidas si se puede pasar de la una a la otra con una rotación de una cara del cubo.
Con esta visualización en mente, resolver el juego se corresponde con encontrar un camino en el grafo que una la configuración en cuestión con el estado ganador. Esto es, una sucesión de estados que empieza en la disposición de partida y acaba en el estado en el que cada cara es de un solo color. Este camino existe siempre, desde cualquier posición, y, de hecho, como hay una cantidad finita (¡aunque enorme!) de configuraciones, habrá un número máximo D de pasos que permiten resolver cualquier configuración. La pregunta es: ¿cuál es el valor de D?
¿Cuál es el valor de D? Esta cifra recibió el misterioso nombre de Número de Dios, y determinar su valor exacto supuso muchos años de investigación
Esta cifra recibió el misterioso nombre de Número de Dios, y determinar su valor exacto supuso muchos años de investigación. En 1979, David Singmaster demostró que era como mucho 277 usando técnicas algebraicas, pero no fue hasta que Morwen Thistlethwaite dio con una interpretación algebraica más sofisticada que la estimación se redujo drásticamente a 52. Más o menos al mismo tiempo, se probó que había configuraciones que requerían, como poco, 18 movimientos para ser resueltas. Así, en 1980 ya se sabía que el valor del número de Dios estaba entre 18 y 52.
Tras 15 años de investigación, en 1995 se demostró que D estaba entre 20 y 29. Y al fin, en julio 2010, con la ayuda de los superordenadores de Google, Tomas Rokicki, Herbert Kociemba y John Dethridge probaron que el número de Dios es 20. Para ello redujeron el conjunto de configuraciones que era necesario considerar, de tal manera que un (súper) ordenador pudo determinar el número máximo de movimientos para resolver cada una de estas.
La investigación matemática desarrollada para resolver este inocente problema tiene aplicaciones muy diversas (la comprensión y desarrollo de los ordenadores, las redes de transporte…), algunas, incluso, todavía desconocidas. De hecho, aunque existe un algoritmo de Dios que describe la manera óptima de resolver cada configuración del cubo, su implementación práctica en ordenadores no es efectiva –es decir, no resuelven el cubo en el menor número de pasos–, lo que muestra lo poco que se entiende todavía sobre el tema.
Javier Aramayona es científico titular del Consejo Superior de Investigaciones Científicas en el Instituto de Ciencias Matemáticas (ICMAT)
Hugo Parlier es profesor de la Universidad de Luxemburgo
Ágata A. Timón es responsable de Comunicación y Divulgación del ICMAT
Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que transforma café en teoremas”.