Las matem¨¢ticas del cubo de Rubik

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 ¨Ces decir, no resuelven el cubo en el menor n¨²mero de pasos¨C, 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¡±.

Puedes seguir a MATERIA en Facebook, Twitter, Instagram o suscribirte aqu¨ª a nuestra newsletter