el cubo de Rubik y otros pasatiempos matematicos

1

EL CUBO DE RUBIK Y OTROS PASATIEMPOS ´ MATEMATICOS Pedro Alegr´ıa ([email protected])

´ INDICE 1. Introducci´on. 2. Grupos de permutaciones. 3. Puzzles de permutaciones. 4. Elementos de teor´ıa de grupos. 5. Grafos de Cayley. 6. Estructura del grupo del cubo de Rubik.

2

1.

´ INTRODUCCION.

El cubo m´agico, con su desconcertante habilidad para sembrar la confusi´on de forma instant´anea nos proporciona un ejemplo excelente de acci´on de un grupo sobre un conjunto. Probablemente ya habr´a visto ud. el rompecabezas incluso es posible que tenga uno propio. Pero, en caso negativo, ha aqu´ı una breve descripci´on. Se trata de un cubo dividido en 27 cubos pequeˆ nos dispuestos de 3 por cada arista. Dentro hay un mecanismo ingenioso que mantiene unidos a los cubitos de tal manera que se pueda girar cada una de las caras del cubo m´agico alrededor de su centro. Las caras visibles de los cubitos est´an coloreadas; en su disposici´on primitiva cada cara del cubo m´agico, formada por nueve cuadraditos, es monocroma y las seis caras tienen colores diferentes. Si se gira una cara y luego otra y otra, despu´es de cuatro o cinco movimientos los colores aparecen completamente revueltos. Invariablemente surgen dos preguntas. La primera es ¿c´omo funciona? Dejamos al lector el trabajo de descubrirlo por su cuenta. Necesitar´a la imaginaci´on desbordante del inventor del cubo, el Profesor Ern¨o Rubik de Budapest, si quiere encontrar una respuesta por la v´ıa del pensamiento. La segunda es ¿c´omo se puede resolver?, o sea, ¿qu´e reglas sencillas y f´acilmente memorizables, sirven para devolver al cubo a su disposici´on original partiendo de cualquier configuraci´on?. Aunque en la actualidad existen muchos algoritmos v´alidos distintos no deseamos desilusionarle d´andole detalles. Estas p´aginas intentan indicar el papel que juega la teor´ıa de grupos en el estudio del cubo m´agico. En ellas se maneja el cubo como una ilustraci´on excelente de la teor´ıa de acciones de grupos sobre conjuntos. Seg´ un escribi´o el propio Ern¨o Rubik: “Para m´ı este objeto es un ejemplo admirable de la belleza rigurosa, de la gran riqueza de las leyes naturales; es un ejemplo sorprendente de las posibilidades admirables del esp´ıritu humano para probar su rigor cient´ıfico y para dominar esas leyes... Es el ejemplo de la unidad de lo verdadero y de lo bello, lo que para m´ı significan la misma cosa. Todo esto podr´ıa parecer exagerado a prop´ osito de un simple juguete, pero conf´ıo en que quienes, aprovechando sus posibilidades, intenten penetrar en este mundo cient´ıfico y asimilarlo, har´ an descubrimientos y ser´ an de mi opini´ on. Mi convicci´ on ´ıntima es que jugando con ´el, reflexionando sobre ´el, podemos alcanzar algo de la l´ ogica pura del Universo, de su esencia sin l´ımites, de su movimiento perpetuo en el espacio y en el tiempo.” Ah´ı est´an las palabras de ese hombre que naci´o en Budapest (Hungr´ıa) en 1.944, hijo de ingeniero mec´anico y mujer de letras (poetisa y artista), que estudi´o Bellas Artes, obtuvo el diploma de Ingeniero, diploma de “designer” (Artes Decorativas) y se dedic´o a la ense˜ nanza en la Escuela Superior... De c´omo surgi´o su idea de crear el juego, y c´omo se ha desarrollado en nuestros d´ıas dan fe las numerosas p´aginas de Internet dedicadas al Cubo. S´olo mencionar´e como dato curioso que las posiciones aproximadas y posibles en uno de ellos que tenga 3 × 3 eran de unas: 43,252,003,274,489,856,000. Aunque recomponerlo es, con la ayuda de un libro, bastante f´acil.

3

2.

GRUPOS DE PERMUTACIONES.

Una afirmaci´on no exagerada dice que los grupos miden la simetr´ıa. El estudio de las simetr´ıas de figuras geom´etricas ilustran esta afirmaci´on. El cubo de Rubik y otros puzzles similares ponen de manifiesto esta simetr´ıa a trav´es de manipulaciones mec´anicas. Una buena excusa para estudiar los grupos de permutaciones y, por extensi´on, los grupos finitos, puede ser el construir un modelo te´orico para resolver puzzles del tipo del cubo de Rubik. Como dijo Hilbert, el arte de hacer matem´aticas es escoger un buen ejemplo del cual aprender. As´ı que en nuestro caso, el ejemplo es el famoso (aunque ya no tanto) cubo de Rubik. A lo largo de este libro se ha puesto de manifiesto, y todav´ıa insistiremos m´as en ello, que la teor´ıa de grupos subyace en una sorprendente variedad de situaciones aparentemente alejadas entre s´ı. B´asicamente, siempre que observemos alg´ un tipo de simetr´ıa, no debemos sorprendernos que en esencia tengamos un grupo que sirva de modelo. No s´olo el cubo de Rubik tiene muchas simetr´ıas, la cristalograf´ıa, la f´ısica de las part´ıculas, incluso la distribuci´on de las plantas en una siembra, son algunos ejemplos donde se presentan simetr´ıas. Ya Einstein se preguntaba c´omo las matem´aticas, siendo al fin y al cabo un producto del pensamiento humano independiente de la experiencia, est´an tan admirablemente adaptadas a los objetos reales. Observemos algunos detalles b´asicos sobre el cubo de Rubik y otros puzzles que hacen adecuado el estudio de los grupos de permutaciones para obtener un contexto unificado de planteamiento y resoluci´on de los mismos. Los pasatiempos que citaremos tienen en com´ un lo siguiente: se trata de puzzles que consisten en varias piezas m´oviles conectadas a un mecanismo que controla sus posibles movimientos, y que tienen las cinco caracter´ısticas siguientes: 1. Las piezas m´oviles pueden enumerarse de forma que cada movimiento del puzzle corresponde a una u ´nica permutaci´on de los n´ umeros {1, 2, . . . , n} que utilizamos para distinguir cada pieza. 2. Si una permutaci´on del conjunto anterior corresponde a m´as de un movimiento del puzzle, entonces las dos posiciones alcanzadas por los dos movimientos deben ser indistinguibles. 3. Cada movimiento tiene un inverso, es decir existe otro movimiento que recompone el puzzle a la posici´on de la que se hab´ıa partido. 4. Si dos movimientos corresponden a dos permutaciones cualesquiera, la secuencia de los dos movimientos consecutivos corresponde a la composici´on de las permutaciones. 5. Cada puzzle debe tener una posici´on final (o soluci´on) que quien lo realiza puede, en principio, alcanzar.

4

3. 3.1.

PUZZLES DE PERMUTACIONES. Puzzle del quince de Sam Loyd.

Se trata de un cuadrado 4 × 4 con los quince primeros n´ umeros naturales (se elimina el n´ umero 16).

Cada cuadrado numerado representa un bloque deslizante que s´olo puede moverse al cuadrado en blanco. Cada movimiento consiste en deslizar un cuadrado numerado sobre el cuadrado en blanco. Si representamos el cuadrado en blanco con el n´ umero 16, un movimiento ser´a una determinada permutaci´on del conjunto {1, 2, . . . , 16}. Debemos observar que no toda posici´on inicial tiene soluci´on (entendiendo por soluci´on conseguir que cada cuadrado alcance una posici´on determinada). Por ejemplo, las posiciones de las figuras siguientes no pueden alcanzarse desde una hasta la otra.

Vamos a detenernos un momento en la entretenida historia que afecta a este juego. A finales de la d´ecada de 1870, el puzzle hizo furor en los Estados Unidos y la fiebre se extendi´o r´apidamente, como una plaga. Tambi´en en Europa hubo muchos aficionados a este juego, y en cualquier lugar se ve´ıa a gente completamente absorta en el juego. R´apidamente se organizaron concursos y desaf´ıos en relaci´on a este puzzle. 5

En 1880 la fiebre alcanz´o su punto culminante, pero pronto se enfri´o al entrar en escena las armas de la Matem´atica. La teor´ıa matem´atica que subyace en el puzzle prob´o que s´olo la mitad de los problemas que pod´ıan plantearse ten´ıa soluci´on, independientemente de la estrategia utilizada. Se vi´o claro entonces por qu´e los organizadores de los concursos ofrec´ıan esas enormes recompensas a quienes resolvieran ciertos problemas. El inventor del puzzle fue Sam Loyd, un conocido autor de numerosos problemas de ingenio y multitud de puzzles. Curiosamente, no pudo patentar su invento pues la regulaci´on existente ped´ıa que se enviara un modelo sobre el que se pudiera fabricar a partir de ´el un prototipo. Cuando se le pregunt´o en la Oficina de Patentes si se pod´ıa resolver, ´el contest´o que era matem´aticamente imposible. Se le contes´o que, al no ser un modelo que funcionara, no pod´ıa patentarse, lo que satisfizo a Loyd. La explicaci´on a esto es que Loyd construy´o su modelo con las quince piezas en orden salvo las dos u ´ltimas, la 14 y la 15, que las coloc´o intercambiadas. El problema que planteaba era conseguir que todas las piezas estuvieran en orden, s´olo deslizando las piezas en el cuadro. Los 1000 d´olares ofrecidos a quien primero diera la soluci´on no se entregaron nunca; sin embargo, el inter´es de la gente dio pie a numerosas an´ecdotas al respecto. Veamos cu´ales son los posibles movimientos en este puzzle. En figura suponemos que u, d, l, r, representan los n´ umeros de arriba, abajo, izquierda y derecha del cuadrado libre, respectivamente, y ∗ representa cualquier otro n´ umero.

Hay cuatro movimientos b´asicos: U = colocar la pieza u en el lugar de 16, (u, 16). D = colocar la pieza d en el lugar de 16, (d, 16). L = colocar la pieza l en el lugar de 16, (l, 16). R = colocar la pieza r en el lugar de 16, (r, 16). Es f´acil verificar que las cinco propiedades que definen un puzzle de permutaci´on se verifican en este ejemplo. Como todos los movimientos son reversibles y cualquier sucesi´on de ellos puede dar como resultado la posici´on I (todas las piezas en orden creciente) o la posici´on II (todas las piezas en orden

6

salvo la 14 y la 15 que est´an intercambiadas), toda la variedad de distribuciones de los n´ umeros se puede dividir solamente en dos clases disjuntas. Ahora bien, para saber si una posici´on inicial pertenece a una clase o a la otra, basta contar el n´ umero de inversiones entre las piezas (alteraciones en su orden natural, sumando el n´ umero de la fila del cuadro vac´ıo). Si dicho n´ umero es par, pertenece al modelo resoluble I, y si es impar, al irresoluble II. En general, si el tablero del juego tiene n filas y m columnas, el grafo del puzzle es siempre bipartito, es decir tiene dos componentes conexas, una de ellas formada por permutaciones pares y otra formada por permutaciones impares.

3.2.

Anillos h´ ungaros.

Este puzzle consiste en dos o m´as c´ırculos que se entrecruzan, cada uno de los cuales tiene piezas numeradas (o coloreadas), algunas de las cuales pueden pertenecer a m´as de un c´ırculo. Un movimiento del puzzle consiste en girar un c´ırculo y, por tanto, todas las piezas contenidas en ´el. Las piezas est´an igualmente espaciadas y las que est´an en m´as de un c´ırculo pueden moverse a lo largo de cualquiera de dichos c´ırculos. El objetivo del juego es, como usualmente, colocar las piezas en su posici´on original. Por simplicidad, consideraremos el puzzle que consiste en s´olo dos c´ırculos, con seis piezas contenidas en cada uno de ellos, como se indica en la figura.

Las piezas con los n´ umeros 5 y 10 pueden moverse a lo largo de cualquier c´ırculo. Observemos que cada movimiento corresponde a una u ´nica permutaci´on de los n´ umeros {1, 2, . . . , 10}. Por ejemplo, girar el c´ırculo de la izquierda en sentido antihorario corresponde a la permutaci´on i = (1, 2, 3, 4, 5, 10) y gr´aficamente a la figura siguiente:

7

Sin embargo, al girar el de la derecha en el mismo sentido, la permutaci´on es d = (5, 6, 7, 8, 9, 10) lo que corresponde a la figura:

El producto de ambas permutaciones no es conmutativo, pues id = (1, 2, 3, 4, 6, 7, 8, 9, 10) di = (1, 2, 3, 4, 5, 6, 7, 8, 9).

8

Se puede probar que una combinaci´on de estas dos permutaciones da un 3-ciclo, lo que, seg´ un la teor´ıa de estos grupos, permite deducir que el puzzle tiene soluci´on para cualquier posici´on inicial.

3.3.

Equator.

Este puzzle consiste en tres bandas circulares situadas en una misma esfera, cada una de las cuales tiene 12 piezas cuadradas y cada banda intersecta a las dem´as seg´ un un ´angulo de 90 grados. Cada par de c´ırculos se intersecta en dos puntos o nodos y en cada tal nodo existe una pieza del puzzle compartida por las dos bandas circulares. Hay pues un total de 6 nodos y el n´ umero total de piezas m´oviles es pues 3 × 12 − 6 = 30. Sobre la esfera se pinta un mapa de la tierra. La banda longitudinal recorre el ecuador, una banda vertical pasa a trav´es de Norteam´erica y la otra a trav´es de Europa y Africa. Un movimiento del puzzle consiste en girar una de las bandas en cualquier direcci´on. Sucesivos movimientos pueden cambiar la orientaci´on de una pieza. Cuando las 30 piezas est´an colocadas de modo que el puzzle es un mapa correcto de la Tierra, decimos que el puzzle est´a resuelto. Para mayor facilidad en el dibujo, utilizaremos la proyecci´on de Mercator para representar el glo-

bo terrestre. El puzzle tiene entonces las siguientes piezas, en la posici´on resuelta:

El n´ umero 1 corresponde as´ı al polo norte y el 7 al polo sur. Veamos c´omo un movimiento afecta a la posici´on de una pieza. Por ejemplo, un movimiento del ecuador corresponde a una u ´nica permutaci´on del conjunto {1, 2, 3, . . . , 30}. Ahora bien, una pieza, aun estando en su lugar, puede tener cualquier orientaci´on. Para asignar una orientaci´on, que es simplemente una indicaci´on sobre el ´angulo en que la pieza est´a girada, daremos un entero 0, 1, 2 ´o 3. En primer lugar, si una pieza no est´a en su posici´on correcta, le daremos una orientaci´on de 0. Si est´a en su posici´on correcta, la orientaci´on ser´a 0, 1, 2 ´o 3 dependiendo del a´ngulo que forma con la orientaci´on correcta, seg´ un el esquema siguiente:

Por ejemplo, a una pieza que se encuentra girada 90 grados en sentido contrario a las agujas del reloj de su orientaci´on correcta, le asignaremos como orientaci´on un 3. En general, las piezas del puzzle se pueden representar mediante el producto cartesiano del conjunto de posiciones {1, 2, . . . , 30} y el del conjunto de orientaciones {0, 1, 2, 3}: S = {(m, n) : 1 ≤ m ≤ 30, 0 ≤ n ≤ 3}. 9

1 2 3 4 5 6 7

23 24

Cada movimiento corresponde a una u ´nica permutaci´on del conjunto S, lo que equivale tambi´en a una permutaci´on del conjunto T = {1, 2, . . . , 120}. Una u ´ltima observaci´on: si una pieza est´a correctamente orientada, la pieza de sus ant´ıpodas tambi´en est´a correctamente orientada. Esquema de la estrategia de soluci´on: En primer lugar, ignora la orientaci´on de las piezas. Trata de colocar las piezas en su posici´on correcta. Una interesante propiedad de este puzzle es que un programa de ordenador utilizado en teor´ıa de grupos, el GAP, es muy eficiente para resolver esta parte de la soluci´on (sobre todo porque no es tan eficiente para resolver el correspondiente problema del cubo de Rubik). A continuaci´on, debemos conseguir la orientaci´on correcta mediante una lista de movimientos de los nodos (puntos donde los c´ırculos se intersectan) dise˜ nados para este prop´osito. No incluiremos aqu´ı dicha lista pues no es nuestro objetivo en este libro divulgativo.

3.4.

Materball.

Se trata de una esfera con 32 piezas de 8 colores distintos. Supondremos que la esfera est´a en una posici´on fija en el espacio, centrado en el origen. Un camino geod´esico del polo norte al polo sur se llamar´a l´ınea longitudinal y un camino geod´esico cerrado paralelo al ecuador se llamar´a l´ınea latitudinal. Hay 8 l´ıneas longitudinales y 3 latitudinales. En coordenadas esf´ericas, las l´ıneas longitudinales forman ´angulos que son m´ ultiplos de π/4, es decir, α = nπ/4, n = 1, . . . , 8, y las l´ıneas latitudinales est´an a ´angulos β = nπ/4, n = 1, 2, 3.

3.5.

Cubo de Rubik 2 × 2.

El cubo de Rubik de bolsillo tiene seis caras, cada una de las cuales tiene 2 × 2 = 4 facetas, que hacen un total de 24.

10

Fijemos una orientaci´on del cubo de Rubik en el espacio. De este modo, podemos etiquetar cada una de las seis caras como f (front), b (back), l (left), r (right), u (up), d (down), como en el dibujo. Tiene 8 cubos m´oviles. Cada cara del cubo est´a asociada a un corte de 4 subcubos que comparten una faceta con la cara. Cada cara, junto con los cuatro cubos que forman su corte, puede girarse 90 grados en el sentido de las agujas del reloj. Denotaremos este movimiento por la letra may´ uscula correspondiente a la letra que indica la cara. Por ejemplo, F indica el movimiento que gira la cara de enfrente 90 grados en el sentido de las agujas del reloj. Las 24 facetas del cubo las nombraremos como indica la figura:

Cada una de ellas puede representarse por tres letras, xyz, donde x es la cara en la que se encuentra, e y, z indican las dos caras adyacentes a ella. De este modo, tenemos: Cara de enfrente: 9 = flu, 10 = fru, 11 = fld, 12 = frd; Cara de atr´as: 17 = bru, 18 = blu, 19 = brd, 20 = bld; Cara derecha: 13 = rfu, 14 = rbu, 15 = rfd, 16 = rbd; Cara izquierda: 5 = lbu, 6 = lfu, 7 = lbd, 8 = lfd; Cara superior: 1 = ulb, 2 = urb, 3 = ulf, 4 = urf; Cara inferior: 21 = dlf, 22 = drf, 23 = dlb, 24 = drb.

3.6.

Cubo de Rubik 3 × 3.

Mucho se ha escrito sobre el cubo de Rubik. Aqu´ı u ´nicamente introduciremos alguna notaci´on b´asica para hacer patente que el cubo es de hecho un puzzle de permutaci´on.

11

El cubo de Rubik tiene seis caras, cada una de las cuales tiene 3 × 3 = 9 facetas, para un total de 54 facetas. Denotaremos cada una de ellas como 1, 2, 3, . . . , 54 como sigue:

Entonces, los generadores correspondientes a las seis caras del cubo pueden escribirse en notaci´on c´ıclica disjunta como:

12

F

= (17, 19, 24, 22)(18, 21, 23, 20)(6, 25, 43, 16)(7, 28, 42, 13)(8, 30, 41, 11);

B = (33, 35, 40, 38)(34, 37, 39, 36)(3, 9, 46, 32)(2, 12, 47, 29)(1, 14, 48, 27); L = (9, 11, 16, 14)(10, 13, 15, 12)(1, 17, 41, 40)(4, 20, 44, 37)(6, 22, 46, 35); R = (25, 27, 32, 30)(26, 29, 31, 28)(3, 38, 43, 19)(5, 36, 45, 21)(8, 33, 48, 24); U

= (1, 3, 8, 6)(2, 5, 7, 4)(9, 33, 25, 17)(10, 34, 26, 18)(11, 35, 27, 19);

D = (41, 43, 48, 46)(42, 45, 47, 44)(14, 22, 30, 38)(15, 23, 31, 39)(16, 24, 32, 40). El tama˜ no del grupo generado por estas permutaciones es 227 · 314 · 53 · 72 · 11 = 43,252,003,274,489,856,000. La notaci´on para las facetas ser´a similar a la usada para el cubo de Rubik 2 × 2. Las facetas de las esquinas tendr´an la misma notaci´on y las de los ejes se denotar´an por xy, donde x es la cara en que se encuentra la faceta e y es la cara de la que la faceta es borde. Tomando como orden el sentido de las agujas del reloj y empezando con la esquina superior derecha de cada cara:

Delante: 19 = f ru, 21 = f r, 24 = f rd, 23 = f d, 22 = f ld, 20 = f l, 17 = f lu, 18 = f u; Detr´as: 35 = blu, 37 = bl, 40 = bld, 39 = bd, 38 = brd, 36 = br, 33 = bru, 34 = bu; Derecha: 27 = rbu, 29 = rb, 32 = rbd, 31 = rd, 30 = rf d, 28 = rf, 25 = rf u, 26 = ru; Izquierda: 11 = lf u, 13 = lf, 16 = lf d, 15 = ld, 14 = lbd, 12 = lb, 9 = lbu, 10 = lu; Encima: 3 = urb, 5 = ur, 8 = urf, 7 = uf, 6 = uf l, 4 = ul, 1 = ulb, 2 = ub; Debajo: 43 = drf, 45 = dr, 48 = drb, 47 = db, 46 = dlb, 44 = dl, 41 = dlf, 42 = df. El cubo central (invisible) y cada uno de los seis cubos en el centro de cada cara permanecen invariables con cada movimiento del puzzle; por lo tanto estos proporcionan el sistema de ejes fijos de la figura. Adem´as todo movimiento permuta v´ertices en v´ertices y ejes en ejes. Algunas variantes del cubo de Rubik como la de la ilustraci´on tienen la dificultad adicional de que las caras est´an orientadas.

3.7.

Pyraminx.

El pyraminx es un puzzle con forma de tetraedro (s´olido plat´onico de cuatro caras). Cada una de las cuatro caras est´a dividida en nueve facetas triangulares. 13

Hay pues un total de 4 × 9 = 36 facetas en el pyraminx. Las denotaremos como sigue:

Fijemos una orientaci´on del pyraminx en el espacio, de modo que podamos hablar de delante, izquierda, derecha y abajo. El propio tetraedro est´a subdividido en sub-tetraedros como sigue: por cada cara x (que puede ser f, l, r, d) hay un v´ertice opuesto Vx del s´olido. Llamaremos primer corte X1 al contenido entre la cara x y el primer plano paralelo a la cara que contiene a x; segundo corte X2 al comprendido entre este primer plano y el siguiente paralelo al anterior y tercer corte X3 al tetraedro peque˜ no que contiene s´olo al v´ertice Vx. Por cada cara x podemos realizar una rotaci´on en sentido de las agujas del reloj de 120 grados sobre X1, rotaci´on que tambi´en llamaremos X1. Del mismo modo, es posible realizar una rotaci´on de 120 grados en el sentido de las agujas del reloj al segundo corte X2, que tambi´en llamaremos X2. Por u ´ltimo, X3 representar´a tambi´en el giro de 120 grados en el sentido de las agujas del reloj sobre el tercer corte X3. Estos movimientos permutan los nombres de las 36 facetas por lo que pueden verse como una permutaci´on del conjunto 1, 2, . . . , 36. Por ejemplo, la notaci´on c´ıclica disjunta para este movimiento es

14

F 3 = (23, 22, 36). Los movimientos b´asicos son los siguientes:

F 1 = (2, 32, 27)(8, 31, 26)(7, 30, 12)(19, 29, 11)(18, 28, 3)(1, 17, 13)(6, 15, 4)(5, 16, 14) F 2 = (9, 35, 25)(21, 34, 24)(20, 33, 10)F 3 = (23, 22, 36) R1 = (3, 36, 17)(11, 34, 16)(10, 35, 6)(24, 31, 5)(23, 32, 1)(2, 22, 18)(9, 20, 7)(8, 21, 19) R2 = (12, 33, 15)(26, 29, 14)(25, 30, 4) R3 = (27, 28, 13) L1 = (1, 28, 22)(5, 29, 21)(4, 33, 9)(14, 34, 8)(13, 36, 2)(3, 27, 23)(11, 26, 24)(12, 25, 10) L2 = (6, 30, 20)(16, 31, 19)(15, 35, 7) L3 = (17, 32, 18) D1 = (13, 18, 23)(14, 19, 24)(15, 20, 25)(16, 21, 26)(17, 22, 27) (28, 32, 36)(29, 31, 34)(30, 35, 33) D2 = (4, 7, 10)(5, 8, 11)(6, 9, 12) D3 = (1, 2, 3) El resto de movimientos puede hacerse combinando secuencialmente los anteriores.

4.

ELEMENTOS DE TEOR´IA DE GRUPOS. En 1910 el matem´ atico O. Veblen y el f´ısico J. Jeans discut´ıan sobre la reforma de los planes de estudio en la Universidad de Princeton. Jeans propon´ıa sacar de los programas la teor´ıa de grupos razonando que era un tema que nunca ser´ıa u ´ til a la f´ısica. Sabemos que la teor´ıa de grupos continu´ o ense˜ n´ andose. Por iron´ıas del destino la teor´ıa de grupos se convirti´ o en uno de los temas centrales de la f´ısica y todav´ıa domina el pensamiento de todos los que estamos empe˜ nados en entender las part´ıculas fundamentales de la naturaleza. Freeman J. Dyson, 1964.

Sea X un conjunto finito y SX el conjunto de todas las permutaciones de X en s´ı mismo. Este conjunto SX se llama el grupo sim´etrico de X con la operaci´on de composici´on, usualmente denotado por Sn si suponemos que X = {1, 2, . . . , n}. Por ejemplo, si X = {1, 2, 3}, S3 = {I, s1 = (12), s2 = (23), s3 = (132), s4 = (123), s5 = (13)}, cuya tabla de multiplicar es la siguiente: I s1 s2 s3 s4 s5 I I s1 s2 s3 s4 s5 s1 s1 I s3 s2 s5 s4 s2 s2 s4 I s5 s1 s3 s3 s3 s5 s1 s4 I s2 s4 s4 s2 s5 I s3 s1 s5 s5 s3 s4 s1 s2 I Queremos en estas l´ıneas introducir la terminolog´ıa y t´ecnicas que nos permitan analizar matem´aticamente los puzzles de permutaci´ on. Para ello definimos los siguientes conceptos.

15

Sea X un grupo finito y g1 , g2 , . . . , gn elementos de SX . Llamamos G al conjunto de todos los posibles productos de la forma g = x1 x2 . . . xm , m > 0, donde cada xi es un elemento de g1 , g1−1 , g2 , g2−1 , . . . , gn , gn−1 . El grupo que origina el conjunto G es un grupo de permutaciones con generadores g1 , g2 , . . . , gn . Se llama orden de un grupo al n´ umero de elementos que tiene, y para cualquier elemento g de un grupo, se llama orden de g al menor entero positivo m tal que g m = 1, caso de que exista (si no existe, se dice que g es de orden infinito). Si G es un grupo de permutaciones con un solo generador, se dice que G es c´ıclico. Se llama conmutador de dos elementos g y h de un grupo G al elemento [g, h] = g ∗ h ∗ g −1 ∗ h−1 . En particular, si g y h conmutan, su conmutador es la identidad del grupo. Si volvemos al cubo de Rubik e interpretamos los movimientos como elementos del grupo de permutaci´on del cubo, el orden del movimiento [R, U ] es seis, es decir se necesitan seis composiciones del mismo movimiento para obtener la posici´on inicial. En el cubo de Rubik generado por las permutaciones R, L, U, D, F, B en S54 llamaremos conmutador Y al elemento [F, R−1 ] = F ∗ R−1 ∗ F −1 ∗ R. Del mismo modo, el conmutador Z es [F, R] = F ∗ R ∗ F −1 ∗ R−1 . En un grupo cualquiera G llamamos subgrupo conmutador G0 al generado por todos los conmutadores [g, h] de G. En el caso del grupo generado por todos los movimientos b´asicos del cubo de Rubik, el subgrupo conmutador es relativamente grande, es decir, la mayor´ıa de los movimientos del cubo de Rubik puede generarse a partir de conmutadores como Y y Z. Llamamos conjugaci´ on de dos elementos g y h al elemento g ∧ h = g ∗ h ∗ g −1 . En el cubo de Rubik se puede comprobar que el orden del movimiento R ∧ U es cuatro. Decimos que dos elementos g1 , g2 de un grupo G son conjugados si existe un elemento h en G tal que g2 = g1 ∧ h. Fijado un elemento g de un grupo G, el conjunto C(g) = {h ∗ g ∗ h−1 : h ∈ G} se llama clase de conjugaci´ on de g. Del mismo modo, si H es un subgrupo de G y g es un elemento fijo de G, el conjunto H ∧ g = {g ∗ h ∗ g −1 : h ∈ H} es el llamado subgrupo conjugado de H. Estudiaremos ahora el concepto de acci´on de grupos sobre conjuntos. Decimos que un grupo G act´ ua sobre un conjunto X si: a) cada elemento g ∈ G define una funci´on g : X → X; b) la identidad del grupo define la funci´on identidad en X; 16

c) el producto de dos elementos da lugar a la funci´on compuesta. Si G act´ ua sobre X, decimos que la acci´on es transitiva si para cada par x, y ∈ X existe un g ∈ G tal que y = g(x). La acci´on es libre si la u ´nica g ∈ G que deja fijo alg´ un elemento de X es la identidad. Un ejemplo de grupo que act´ ua sobre un conjunto es precisamente el grupo sim´etrico de un conjunto X. Adem´as es libre y transitiva. Si X es el conjunto de las 54 facetas del cubo de Rubik y G el grupo de permutaci´on generado por las permutaciones R, L, U, D, F, B, entonces G act´ ua sobre X. Si G es un grupo que act´ ua sobre un conjunto X, se llama ´ orbita de un elemento x ∈ X al conjunto Gx = {g(x) : g ∈ G}. Como aplicaci´on de esta noci´on, si llamamos G al grupo de movimientos del cubo de Rubik, X al conjunto de v´ertices del cubo y H al subgrupo de G generado por U ∗ R, intentar calcular el orden de U ∗ R as´ı como la ´orbita del v´ertice uf r en X bajo H. Definimos tambi´en el estabilizador de un elemento x ∈ X en G, siendo G un grupo que act´ ua sobre el conjunto X, como el conjunto stabG (x) = Gx = {g ∈ G : g(x) = x}. Por ejemplo, si X = G y G act´ ua sobre X por la conjugaci´on g : X → X definida por g(x) = g ∗ x ∗ g −1 , entonces stabG (x) = {g ∈ G : g ∗ x = x ∗ g} es precisamente el centralizador de x en G. Si X es el conjunto de las 48 facetas del cubo de Rubik (quitando las fijas), Xc el conjunto de facetas que corresponden a alguna esquina del cubo y Xe el conjunto de facetas de cualquiera de los ejes del cubo, entonces el grupo G del cubo act´ ua sobre X, Xc y Xe . La acci´on de G sobre X induce la siguiente relaci´on de equivalencia: f1 ∼ f2 ⇐⇒ ∃m ∈ G : m(f1 ) = f2 . Hay exactamente dos clases de equivalencia u ´orbitas de G en X: Xc y Xe . En particular la acci´on de G, tanto sobre Xc como sobre Xe , es transitiva. Sea ahora F el subgrupo de G que preserva los ejes y las esquinas (no mueve un subcubo de una esquina a otra esquina pero s´ı puede rotarlo y puede intercambiar los colores de un eje pero no moverlo a otro eje). Tambi´en la relaci´on de equivalencia inducida por la acci´on de F sobre X tiene como clases de equivalencia Xc y Xe y sobre ambas la acci´on es transitiva. Un hecho interesante es que F es el producto directo (producto cartesiano con la operaci´on inducida por la composici´on de G) de Fc y Fe , donde Fc es la intersecci´on de F con el grupo sim´etrico de Xc y Fe la intersecci´on de F con el grupo sim´etrico de Xe . Definiremos a continuaci´on la noci´on de coclase. Si G es un grupo y H un subgrupo de G, una coclase a la izquierda de H en G es el conjunto g ∗ H, para cualquier g ∈ G; del mismo modo, una coclase a la derecha de H en G es el conjunto H ∗ g, , para cualquier g ∈ G. El conjunto de todas las coclases a la izquierda se denota por G/H y el de coclases a la derecha por H\G. Un resultado importante lo constituye el teorema de Lagrange. Teorema. Si G es un grupo finito y H un subgrupo de G, entonces card (G/H) = card G/card H. Como consecuencia, el orden de cualquier subgrupo de un grupo finito es divisor del orden del grupo. 17

5.

GRAFOS DE CAYLEY.

Una interpretaci´on gr´afica de los grupos de permutaci´on, en particular los grupos de puzzles de permutaci´on, viene dada por los grafos de Cayley. Recordemos que un grafo es una colecci´on de pares (V, A) formados por v´ertices o nodos V y aristas o lados A que unen pares de v´ertices, es decir A es un subconjunto de {(v1 , v2 ) : v1 , v2 ∈ V }. Si v, w ∈ V , un camino de v a w es una sucesi´on finita de aristas que empiezan en v y terminan en w. Decimos que un grafo es conexo si cualquier par de v´ertices est´a conectado por alg´ un camino. El n´ umero de aristas que confluyen en un v´ertice v se llama valencia de v. Si dos v´ertices est´an conectados, se define la distancia entre ellos como el n´ umero de aristas que contiene el camino de menor tama˜ no uniendo dichos v´ertices (por convenio, la distancia es infinita si los v´ertices no est´an conectados). El di´ametro de un grafo es el m´aximo entre las distancias de dos v´ertices. Dado un grupo de permutaciones G = h{g1 , . . . , gn }i ⊂ SX se define el grafo de Cayley de G aqu´el cuyos v´ertices son los elementos de G y las aristas verifican la condici´on siguiente: ∀x, y ∈ G, (x, y) ∈ A ⇐⇒ ∃i ∈ {, . . . , n} : y = gi ∗ x ´o x = gi ∗ y. Por ejemplo, si G = h{R, L, U, D, F, B}i ⊂ S54 es el grupo del cubo de Rubik, cada posici´on del cubo corresponde a un v´ertice del grafo de Cayley. Cada v´ertice de este grafo tiene valencia 12. Adem´as, una soluci´on del cubo de Rubik es un camino desde el v´ertice asociado a la posici´on actual hasta el v´ertice correspondiente al elemento identidad y la distancia entre estos v´ertices es el n´ umero de m´ınimo de movimientos necesarios para resolver el cubo. El di´ametro del grafo de Cayley es el menor n´ umero de movimientos necesario para resolver el cubo en el peor de los casos. Para la mayor´ıa de los puzzles de permutaci´on, el di´ametro del grafo de Cayley asociado no es conocido.

6.

ESTRUCTURA DEL GRUPO DEL CUBO DE RUBIK.

Resumiremos por u ´ltimo algunos resultados sobre la estructura del grupo del cubo de Rubik (similar discusi´on se puede hacer con los grupos correspondientes a los dem´as puzzles de permutaci´on). Denotaremos como usualmente G, V, E y F al grupo generado por los movimientos b´asicos, al conjunto de v´ertices, ejes y facetas de las piezas m´oviles, respectivamente. 1) G act´ ua sobre cada uno de los conjuntos V, E, F . Por ello, cualquier movimiento de G puede verse como elemento del grupo sim´etrico SV o´ SE ´o SF . Como estos grupos son diferentes, podemos distinguir tres formas de ver un elemento g ∈ G: gV ∈ SV , gE ∈ SE ´o gF ∈ SF . 2) La aplicaci´on fV E : G → SV ×SE dada por fV E (g) = (gV , gE ) es un homomorfismo. Adem´as la imagen de fV E es isomorfa al conjunto {(x, y) ∈ SV ×SE : x, y son ambas permutaciones pares o ambas impares}. Esto significa que no existe ning´ un movimiento del cubo de Rubik que intercambie los dos elementos de un eje pero deje invariantes a todas las dem´as piezas pues, de ser posible, la imagen de fV E contendr´ıa un elemento (x, y) con x = 1 (los ejes quedan invariantes) e y un 2-ciclo. De este modo, x es impar e y par. 18

3) El n´ ucleo de fV E , que llamaremos K, es un subgrupo normal de G. Este conjunto corresponde a los movimientos que pueden reorientar (intercambiar o rotar) cualquier subcubo pero no cambia un subcubo con otro. Por ejemplo, el movimiento ((D2 ) ∧ R ∗ (U 2 ) ∧ B)2 , que gira la esquina uf r en el sentido horario y la esquina bld en sentido antihorario, pertenece a K (recordemos que x ∧ y = y −1 ∗ x ∗ y). 4) G es el producto semidirecto de K con la imagen de fV E . Decimos que G es producto semidirecto de H1 y H2 si G = H1 ∗ H2 , la identidad es el u ´nico elemento en com´ un de H1 y H2 y H1 es subgrupo normal de G. 5) G est´a generado por los movimientos U ∗ B ∗ L ∗ U ∗ L−1 ∗ U −1 ∗ B −1 y R2 ∗ F ∗ L ∗ D−1 ∗ R−1 .

19

REFERENCIAS. “C´omo jugar y divertirse con el Cubo m´agico de Rubik” de Andr´e Warustel, traducido al espa˜ nol por Mario Merlino de Altadena Editores en 1.981. “Groups and Geometry” de Peter M. Neumann, Gabrielle A. Stoy y E.C. Thompson, Vol.II, Cap.19. The Mathematical Institute, Oxford. Abril 1.980. “Groups and Symmetry” de David Farmer, Mathematical World, 5, AMS, 1.996. “Notas sobre el cubo de Rubik” de David Singmaster, Altabena. 1.981.

20