Teoría de grupos y el cubo de Rubik

Vamos allá.

La teoría de grupos es una rama de las matemáticas que pertenece al marco más general del álgebra abstracta. En el álgebra abstracta se estudian estructuras matemáticas de cualquier tipo de la forma más general posible. El hecho de que el estudio sea tan general y abstracto es que podemos aplicarlo después a cualquier caso concreto que obedezca a alguna de esas estructuras. Esto permite ver similitudes entre cosas matemáticas que, a priori, parecen completamente distintas e independientes.

En este artículo voy a hablar de teoría de grupos. Un grupo es una estructura matemática, muy general, y muy básica. La definimos de la siguiente manera: Un grupo es una estructura matemática formada por dos cosas. La primera es un conjunto cualquiera de elementos: , y la segunda es una operación binaria de los elementos del grupo: . Esta notación significa que la operación recoge dos elementos de , y devuelve otro elemento. Por ejemplo la operación suma en los números naturales es una operación binaria, recoge dos elementos del conjunto (dos números) y devuelve un tercer elemento (su suma) , ó en nuestra notación: Utilizamos el símbolo para mantener generalidad. Pues bien, el par es un grupo si la operación cumple las siguientes condiciones:

1. Existe un elemento de : , tal que para todo en . Este elemento se llama elemento neutro.
2. La operación es asociativa , para todos en .
3. Para todo elemento en , existe un elemento, llamado inverso, y que denotaremos por , tal que

Pues bien, eso es todo. Por ejemplo, los números enteros, con la suma, forman estructura de grupo, ya que la suma cumple las tres condiciones: existe un elemento neutro de la suma: el , la suma es asociativa , y para todo elemento existe un inverso tal que , que en el caso de la suma es el opuesto : . Este grupo, además es conmutativo, puesto que , estos grupos se llaman abelianos.

Por último, definimos subgrupos de un grupo como un subconjunto de , tal que por si mismo también forma estructura de grupo con la misma operación.

Ejemplos de grupos hay muchísimos más, y muy interesantes, más cosas que forman estructura de grupos: las permutaciones de un conjunto con la composición, las rotaciones de un objeto, las funciones continuas sobre un intervalo con la suma, o la multiplicación, el conjunto de partes de un conjunto con la diferencia simétrica, los automorfismos de un grafo, los endomorfismos de un espacio vectorial con la composición, y uno del que hablaremos aquí, que será muy familiar a todo el mundo: los movimientos del cubo de Rubik.

Este último es del que nos ocuparemos, en concreto nos ocuparemos de calcular ordenes de subgrupos cíclicos, que paso a explicar.

Lo primero, comprobar que los movimientos del cubo de Rubik forman un grupo con la composición de movimientos: es evidente que hay un elemento neutro, que es no hacer ningún movimiento, y también es evidente que hay un elemento opuesto para todo movimiento, que es repetir lo que has hecho yendo hacia atrás. La asociatividad no es tan trivial, pero si se piensa un poco en lo que supone físicamente en el cubo el agrupar paréntesis, sí parece más claro: si tenemos tres movimientos, que se ejecutan de derecha a izquierda (esto es estándard en funciones): supone que primero hacemos el movimiento c, luego el b y luego el a. Pues bien supone primero hacer , y luego hacer , es decir, luego y por último , pero tener es exactamente lo mismo, pues supone primero realizar , es decir, primero , luego , y por último , es decir realizamos el mismo movimiento y por lo tanto el resultado es el mismo, luego la operación as asociativa.

Ahora veamos un poco de notación: para referirnos al cubo, usaremos la notación normal inglesa: los giros de las caras vienen dados por U (up), F (front), D (down), B (back , R (right), L (left). Los giros se hacen siempre de 90 grados, y en el sentido de las agujas del reloj. Si tenemos UF, entonces giramos primero la cara superior 90 grados, y luego la cara frontal. Llamaremos también a los giros en el sentido contrario a las agujas del reloj mediante una prima: U’ significa girar la cara superior 90 grados en el sentido contrario a las agujas del reloj, y U2 o , significa girar la cara 180 grados. Evidentemente U’=UUU, UU’=U’U=0=.

Está claro que, aunque no conocemos el tamaño, el número de combinaciones posibles del cubo es finito, independientemente de que sea grande. Le podemos poner una cota, por ejemplo la siguiente: todas las combinaciones, puesto que las posiciones relativas de los centros son constantes, vienen dadas por permutaciones de las 8 esquinas ( combinaciones), permutaciones de las 12 aristas ( combinaciones), rotaciones de las esquinas (hay 3 por cada esquina: combinaciones), y rotaciones de las aristas (2 por cada arista: combinaciones), por lo tanto el número de combinaciones posibles es menor que .

Estos grupos con un número finito de elementos tienen muchas propiedades muy interesantes, y una de las importantes por su elementariedad e impacto sobre la teoría es el conocido como teorema de Lagrange, que no demuestro, y que dice así:

Teorema de Lagrange:

Sea un grupo finito y un subgrupo , se cumple que

Lo explico, es el número de elementos de , y es el número de elementos de . La letra ‘o’ es de ‘órden’. es una cosa conocida como índice del subgrupo, y hace referencia a las clases de equivalencia resultantes de una relación de equivalencia definida en el grupo, y que no trataré en este artículo, por no tener mucha relevancia en lo que vamos a ver. Lo único que hay que saber es que, puesto que los órdenes del grupo y del subgrupo han de ser enteros, este índica también es un número entero, y tenemos que , y esto es algo realmente sorprendente: el órden de un subgrupo es siempre un divisor del orden del grupo.

Veamos otra definición: si tenemos un grupo finito , y un elemento , el subgrupo generado por , que se denota por , es el grupo que se obtiene de multiplicar por si mismo repetidas veces: $latex \langle a\rangle = \lbrace a,a^2,a^3,a^4,… \rbrace$. Este grupo debe ser finito pueto que por las propiedades del grupo, debe pertenecer a , y es finito, además por el teorema de Lagrange su orden debe dividir al orden de . Para demostrar que es grupo basta ver que la operación es interna , con , y que contiene a la unidad para esto basta considerar la función de los naturales al subgrupo dada por , puesto que el subgrupo es finito y los naturales no, la función no es inyectica, y hay dos números distintos tal que , tenemos entonces que . Y por lo tanto al multiplicar por si mismo veces obtenemos la unidad, el inverso se puede encontrar fácilmente. Se cumple además que el primer número n que cumple que ,  es el orden del subgrupo. Estos grupos generados por un único elemento se conocen como grupos cíclicos. En el artículo daré un programa para calcular el orden del grupo cíclico generado por un movimiento determinado por fuerza bruta.

Las consecuencias de todo esto son realmente interesantes, aunque difíciles de apreciar cuando uno se encuentra con ellas de golpe, como puede pasarle a quien lea este artículo sin haber visto nunca lo que es un grupo. Podemos, sin embargo, ver su impacto sobre el cubo de Rubik: Si tenemos un movimiento cualquiera, por ejemplo UFUF’, podemos calcular su grupo cíclico aplicándolo repetidas veces, y sabemos que puesto que pertenece a un grupo finito, llegará un momento en el que lleguemos a la configuración inicial, es decir, si empezamos con el cubo resuelto, llegaremos al cubo resuelto. Sabemos además por Lagrange que este orden es un divisor del orden del grupo completo, pero esto no sirve de poco porque el grupo completo tiene más de 30 trillones de elementos. Sin embargo resulta  que estos ordenes son muy bajos para muchos movimientos, y de hecho el mayor de todos es poco más de 1200. Por ejemplo, el movimiento de arriba, UFUF’, tiene orden 5, de modo que si lo aplicas 5 veces llegarás a la configuración inicial, es decir: . Pruébalo, ten en cuenta que la cuarta letra es F’, F invertida, el movimiento UFUF tiene un orden distinto, y mayor (105).

Aquí es donde entra mi objetivo, que era crear un programa, que mediante fuerza bruta, calcula el orden de un movimiento: lo aplica continuamente hasta que llega al cubo resuelto. El programa es estándard 100% y está hecho en C++. No es ni de lejos lo más elegante en cuanto a aplicación de movimientos, ya que cada uno está configurado por separado, pero funciona bien. Tiene la opción de meter movimientos por teclado y mediante un archivo de texto.

Aquí está el código: http://pastebin.com/z9pNRpTP

Lo explico un poco. Al empezar nos da la opción de introducir movimientos por teclado o mediante un archivo de texto. En el primer caso pasa a recoger datos del teclado, al introducir un movimiento en notación estándar (Los giros invertidos son Xi, no X’), lo aplica repetidamente mediante la función apply(), y va mirando si el cubo está resuelto mediante check(), si lo está muestra el número de veces que ha tenido que aplicarlo (el orden del subgrupo cíclico). La función apply lo único que hace es llamar a las funciones oneMove(), que realiza el movimiento, o oneMovei(), que hace el invertido.

La segunda opción principal permite introducir un archivo de texto en el que los movimientos han de ir uno en cada linea, y en principio no hay un límite de movimientos, más que el límite de memoria. Nos pide introducir el nombre del archivo (su ruta), y luego nos dice si queremos que muestre resultados en la consola o los guarde en un archivo. La primera opción muestra primero WOW: n, siendo n el número de movimientos, y después los números. La segunda nos pide introducir el nombre del archivo y luego los va guardando.

Podemos intentar clasificar movimientos. Los siguientes dos programas de Scilab generan todos los posibles movimientos compuestos por desde 2 hasta n movimientos simples, y los guarda en un archivo. Lo único que hace es formar recursivamente todas las combinaciones de movimientos que midan menos de n. Esto lo he hecho para n=6 y se generan alrededor de 3 millones de movimientos, en un archivo txt de 34 megas (por simetrías sobran muchas, pero esto era más simple de programar):

http://pastebin.com/y5EkmfBA

http://pastebin.com/vLwdJevn

El primero es un Script y el segundo una función, para que funcionen debemos abrir ambos en el editor de Scilab, ejecutar la función, y luego el script, cambiando en este último el valor de la variable n al que nosotros queramos. Pues bien, para n=6 obtenemos 3 y pico millones de movimientos, y el programa nos devuelve un archivo con el orden de cada movimiento en una linea. Este archivo pesa bastante y no se abre bien con el excel, pero el Scilab tiene un función muy cómoda para leer este tipo de archivos: fscanfMat. Un histograma de los datos revela lo siguiente:

Como vemos, la mayor parte de ellos está en ordenes bajos, y la mayor parte de los movimientos se encuentra en la primera clase, correspondiente a ordenes de 12, o menores. Un histograma con clases de longitud uno revela lo siguiente:

El orden que más se repite es 63. También se observa que el mayor orden es 1260. Un estudio más profundo revela que este es en realidad el orden más alto que podemos conseguir (1260), y un ejemplo de movimiento con ese orden es: $latex RUUD’BD’$, de manera que hay que repetir ese 1260 veces para volver al principio.

Un par de movimientos más para terminar el artículo:

El movimiento URiUiLFRiFiLDRiDiLBRiBiL tiene orden 3 y es un movimiento curioso, si le copiamos al final los 8 primeros movimientos obtenemos otro: URiUiLFRiFiLDRiDiLBRiBiLURiUiLFRiFiL de orden 2, y que lo que hace es  cambiar aristas y esquinas de manera que cuatro centros quedan opuestos, lo puedes probar con un cubo de verdad o quitar el comentario a la linea 80 del código de C++ (showCube) e introducirlo, veremos que el programa muestra el cubo despegado, con números en vez de colores. Otro que intercambia todas las aristas dejando las esquinas en su sitio, de orden 2: UUDDFFBBRRLL.

Hasta aquí este artículo… hay resultados mucho más profundos e interesantes en teoría de grupos que no he mencionado, y de los que se puede leer en cualquier libro sobre grupos, en concreto grupos finitos, tenemos los teoremas de estructura, los teoremas de isomorfía, el teorema de Cayley, del que se puede deducir que todo grupo finito representa las simetrías de algo… El libro Abstract Algebra, de Dummit & Foote, suele ser bastante recomendado, aunque yo no lo conozco.