El cubo de Rubik y otros pasatiempos matematicos

1

EL CUBO DE RUBIK Y OTROS PASATIEMPOS MATEMA´ TICOS Pedro Alegr´ıa ([email protected])´INDICE1. 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. INTRODUCCIO´ N.El cubo ma´gico, con su desconcertante habilidad para sembrar la confusi´on de forma instant´aneanos proporciona un ejemplo excelente de accio´n de un grupo sobre un conjunto. Probablementeya habr´a visto ud. el rompecabezas incluso es posible que tenga uno propio. Pero, en casonegativo, ha aqu´ı una breve descripci´on. Se trata de un cubo dividido en 27 cubos pequenˆosdispuestos de 3 por cada arista. Dentro hay un mecanismo ingenioso que mantiene unidos a loscubitos de tal manera que se pueda girar cada una de las caras del cubo ma´gico alrededor de sucentro.Las caras visibles de los cubitos esta´n coloreadas; en su disposicio´n primitiva cada cara del cuboma´gico, 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 coloresaparecen completamente revueltos. Invariablemente surgen dos preguntas. La primera es ¿co´mofunciona?Dejamos al lector el trabajo de descubrirlo por su cuenta. Necesitar´a la imaginaci´on desbordantedel inventor del cubo, el Profesor Ern¨o Rubik de Budapest, si quiere encontrar una respuestapor la v´ıa del pensamiento. La segunda es ¿co´mo se puede resolver?, o sea, ¿qu´e reglas sencillasy f´acilmente memorizables, sirven para devolver al cubo a su disposici´on original partiendo decualquier configuracio´n?. Aunque en la actualidad existen muchos algoritmos v´alidos distintosno deseamos desilusionarle d´andole detalles. Estas pa´ginas intentan indicar el papel que juega lateor´ıa de grupos en el estudio del cubo ma´gico. En ellas se maneja el cubo como una ilustraci´onexcelente de la teor´ıa de acciones de grupos sobre conjuntos.Segu´n escribio´ el propio Erno¨ 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, hara´n descubrimientos y sera´n de mi opini´on. Mi conviccio´n ´ıntima es que jugando con ´el, reflexionando sobre ´el, podemos alcanzar algo de la lo´gica pura del Universo, de su esencia sin l´ımites, de su movimiento perpetuo en el espacio y en el tiempo.”Ah´ı esta´n las palabras de ese hombre que nacio´ en Budapest (Hungr´ıa) en 1.944, hijo de ingenieromeca´nico y mujer de letras (poetisa y artista), que estudi´o Bellas Artes, obtuvo el diploma deIngeniero, diploma de “designer” (Artes Decorativas) y se dedic´o a la ensen˜anza en la EscuelaSuperior... De c´omo surgio´ su idea de crear el juego, y co´mo se ha desarrollado en nuestros d´ıasdan fe las numerosas pa´ginas de Internet dedicadas al Cubo. So´lo mencionar´e como dato curiosoque 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´ıasde figuras geom´etricas ilustran esta afirmacio´n. El cubo de Rubik y otros puzzles similares ponende manifiesto esta simetr´ıa a trav´es de manipulaciones meca´nicas.Una buena excusa para estudiar los grupos de permutaciones y, por extensi´on, los grupos finitos,puede ser el construir un modelo teo´rico para resolver puzzles del tipo del cubo de Rubik. Comodijo Hilbert, el arte de hacer matem´aticas es escoger un buen ejemplo del cual aprender. As´ı queen 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 lateor´ıa de grupos subyace en una sorprendente variedad de situaciones aparentemente alejadasentre s´ı. Ba´sicamente, siempre que observemos algu´n tipo de simetr´ıa, no debemos sorprendernosque en esencia tengamos un grupo que sirva de modelo. No s´olo el cubo de Rubik tiene muchassimetr´ıas, la cristalograf´ıa, la f´ısica de las part´ıculas, incluso la distribucio´n de las plantas en unasiembra, son algunos ejemplos donde se presentan simetr´ıas. Ya Einstein se preguntaba co´molas matem´aticas, siendo al fin y al cabo un producto del pensamiento humano independiente dela experiencia, est´an tan admirablemente adaptadas a los objetos reales.Observemos algunos detalles ba´sicos sobre el cubo de Rubik y otros puzzles que hacen adecuadoel estudio de los grupos de permutaciones para obtener un contexto unificado de planteamientoy resoluci´on de los mismos.Los pasatiempos que citaremos tienen en comu´n lo siguiente: se trata de puzzles que consistenen varias piezas m´oviles conectadas a un mecanismo que controla sus posibles movimientos, yque tienen las cinco caracter´ısticas siguientes: 1. Las piezas mo´viles pueden enumerarse de forma que cada movimiento del puzzle corres- ponde a una u´nica permutacio´n de los nu´meros {1, 2, . . . , n} que utilizamos para distinguir cada pieza. 2. Si una permutacio´n 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 posicio´n final (o solucio´n) que quien lo realiza puede, en principio, alcanzar. 4

3. PUZZLES DE PERMUTACIONES.3.1. Puzzle del quince de Sam Loyd.Se trata de un cuadrado 4 × 4 con los quince primeros nu´meros naturales (se elimina el nu´mero16).Cada cuadrado numerado representa un bloque deslizante que so´lo puede moverse al cuadradoen blanco. Cada movimiento consiste en deslizar un cuadrado numerado sobre el cuadrado enblanco. Si representamos el cuadrado en blanco con el nu´mero 16, un movimiento ser´a unadeterminada permutacio´n del conjunto {1, 2, . . . , 16}.Debemos observar que no toda posicio´n inicial tiene solucio´n (entendiendo por soluci´on conseguirque cada cuadrado alcance una posicio´n determinada). Por ejemplo, las posiciones de las figurassiguientes 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 exten-dio´ ra´pidamente, como una plaga. Tambi´en en Europa hubo muchos aficionados a este juego, y encualquier lugar se ve´ıa a gente completamente absorta en el juego. R´apidamente se organizaronconcursos y desaf´ıos en relacio´n a este puzzle. 5

En 1880 la fiebre alcanzo´ su punto culminante, pero pronto se enfrio´ al entrar en escena lasarmas de la Matema´tica. La teor´ıa matema´tica que subyace en el puzzle prob´o que so´lo la mitadde los problemas que pod´ıan plantearse ten´ıa soluci´on, independientemente de la estrategiautilizada. Se vio´ claro entonces por qu´e los organizadores de los concursos ofrec´ıan esas enormesrecompensas a quienes resolvieran ciertos problemas.El inventor del puzzle fue Sam Loyd, un conocido autor de numerosos problemas de ingenio ymultitud de puzzles. Curiosamente, no pudo patentar su invento pues la regulacio´n existenteped´ıa que se enviara un modelo sobre el que se pudiera fabricar a partir de ´el un prototi-po. Cuando se le pregunt´o en la Oficina de Patentes si se pod´ıa resolver, ´el contesto´ que eramatema´ticamente imposible. Se le contes´o que, al no ser un modelo que funcionara, no pod´ıapatentarse, lo que satisfizo a Loyd.La explicaci´on a esto es que Loyd construy´o su modelo con las quince piezas en orden salvolas dos u´ltimas, la 14 y la 15, que las coloco´ intercambiadas. El problema que planteaba eraconseguir que todas las piezas estuvieran en orden, s´olo deslizando las piezas en el cuadro.Los 1000 do´lares 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 cua´les son los posibles movimientos en este puzzle. En figura suponemos que u, d, l, r, re-presentan los nu´meros de arriba, abajo, izquierda y derecha del cuadrado libre, respectivamente,y ∗ representa cualquier otro nu´mero.Hay cuatro movimientos ba´sicos: 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 eneste ejemplo.Como todos los movimientos son reversibles y cualquier sucesi´on de ellos puede dar como resul-tado la posicio´n I (todas las piezas en orden creciente) o la posicio´n II (todas las piezas en orden 6

salvo la 14 y la 15 que est´an intercambiadas), toda la variedad de distribuciones de los nu´merosse puede dividir solamente en dos clases disjuntas.Ahora bien, para saber si una posicio´n inicial pertenece a una clase o a la otra, basta contar elnu´mero de inversiones entre las piezas (alteraciones en su orden natural, sumando el nu´mero dela fila del cuadro vac´ıo). Si dicho nu´mero 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 siemprebipartito, es decir tiene dos componentes conexas, una de ellas formada por permutacionespares y otra formada por permutaciones impares.3.2. Anillos hu´ngaros.Este puzzle consiste en dos o ma´s c´ırculos que se entrecruzan, cada uno de los cuales tiene piezasnumeradas (o coloreadas), algunas de las cuales pueden pertenecer a m´as de un c´ırculo. Unmovimiento del puzzle consiste en girar un c´ırculo y, por tanto, todas las piezas contenidas en´el. Las piezas esta´n igualmente espaciadas y las que est´an en m´as de un c´ırculo pueden moversea lo largo de cualquiera de dichos c´ırculos. El objetivo del juego es, como usualmente, colocarlas piezas en su posici´on original.Por simplicidad, consideraremos el puzzle que consiste en s´olo dos c´ırculos, con seis piezascontenidas en cada uno de ellos, como se indica en la figura.Las piezas con los nu´meros 5 y 10 pueden moverse a lo largo de cualquier c´ırculo. Observemosque cada movimiento corresponde a una u´nica permutaci´on de los nu´meros {1, 2, . . . , 10}. Porejemplo, girar el c´ırculo de la izquierda en sentido antihorario corresponde a la permutaci´on i = (1, 2, 3, 4, 5, 10)y gra´ficamente 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, segu´nla teor´ıa de estos grupos, permite deducir que el puzzle tiene solucio´n para cualquier posici´oninicial.3.3. Equator. 1 2Este puzzle consiste en tres bandas circulares situadas en una misma esfera, cada una de las 3cuales tiene 12 piezas cuadradas y cada banda intersecta a las dema´s segu´n un a´ngulo de 90 4 23 24grados. Cada par de c´ırculos se intersecta en dos puntos o nodos y en cada tal nodo existe una 5pieza del puzzle compartida por las dos bandas circulares. Hay pues un total de 6 nodos y el 6nu´mero total de piezas mo´viles es pues 3 × 12 − 6 = 30. 7Sobre la esfera se pinta un mapa de la tierra. La banda longitudinal recorre el ecuador, una bandavertical pasa a trav´es de Norteam´erica y la otra a trav´es de Europa y Africa. Un movimientodel puzzle consiste en girar una de las bandas en cualquier direcci´on. Sucesivos movimientospueden cambiar la orientacio´n de una pieza. Cuando las 30 piezas esta´n colocadas de modo queel puzzle es un mapa correcto de la Tierra, decimos que el puzzle est´a resuelto.Para mayor facilidad en el dibujo, utilizaremos la proyeccio´n de Mercator para representar el glo-bo terrestre. El puzzle tiene entonces las siguientes piezas, en la posicio´n resuelta:El nu´mero 1 corresponde as´ı al polo norte y el 7 al polo sur.Veamos c´omo un movimiento afecta a la posicio´n de una pieza. Por ejemplo, un movimientodel ecuador corresponde a una u´nica permutaci´on del conjunto {1, 2, 3, . . . , 30}. Ahora bien, unapieza, aun estando en su lugar, puede tener cualquier orientacio´n. Para asignar una orientacio´n,que es simplemente una indicacio´n sobre el ´angulo en que la pieza est´a girada, daremos unentero 0, 1, 2 ´o 3. En primer lugar, si una pieza no est´a en su posicio´n correcta, le daremos unaorientaci´on de 0. Si esta´ en su posicio´n correcta, la orientaci´on ser´a 0, 1, 2 o´ 3 dependiendo dela´ngulo que forma con la orientacio´n correcta, segu´n el esquema siguiente:Por ejemplo, a una pieza que se encuentra girada 90 grados en sentido contrario a las agujas delreloj de su orientacio´n correcta, le asignaremos como orientacio´n un 3.En general, las piezas del puzzle se pueden representar mediante el producto cartesiano delconjunto 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

Cada movimiento corresponde a una u´nica permutaci´on del conjunto S, lo que equivale tambi´ena una permutaci´on del conjunto T = {1, 2, . . . , 120}.Una u´ltima observacio´n: si una pieza esta´ correctamente orientada, la pieza de sus ant´ıpodastambi´en esta´ 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´oncorrecta. Una interesante propiedad de este puzzle es que un programa de ordenador utilizadoen teor´ıa de grupos, el GAP, es muy eficiente para resolver esta parte de la soluci´on (sobre todoporque no es tan eficiente para resolver el correspondiente problema del cubo de Rubik).A continuacio´n, debemos conseguir la orientaci´on correcta mediante una lista de movimientos delos nodos (puntos donde los c´ırculos se intersectan) disen˜ados para este propo´sito. No incluiremosaqu´ı 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 unaposicio´n fija en el espacio, centrado en el origen. Un camino geod´esico del polo norte al polo surse llamara´ l´ınea longitudinal y un camino geod´esico cerrado paralelo al ecuador se llamar´a l´ınealatitudinal. Hay 8 l´ıneas longitudinales y 3 latitudinales. En coordenadas esf´ericas, las l´ıneaslongitudinales forman a´ngulos que son mu´ltiplos de π/4, es decir, α = nπ/4, n = 1, . . . , 8, y lasl´ıneas latitudinales esta´n 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, quehacen un total de 24. 10

Fijemos una orientaci´on del cubo de Rubik en el espacio. De este modo, podemos etiquetar cadauna de las seis caras como f (front), b (back), l (left), r (right), u (up), d (down), como en eldibujo. Tiene 8 cubos mo´viles. Cada cara del cubo esta´ asociada a un corte de 4 subcubos quecomparten 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 movimientopor la letra mayu´scula correspondiente a la letra que indica la cara. Por ejemplo, F indica elmovimiento 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 seencuentra, 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 notacio´nba´sica 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 totalde 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 notacio´nc´ı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 taman˜o 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 delas esquinas tendr´an la misma notacio´n y las de los ejes se denotara´n por xy, donde x es la caraen que se encuentra la faceta e y es la cara de la que la faceta es borde. Tomando como orden elsentido 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; Detra´s: 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 permaneceninvariables con cada movimiento del puzzle; por lo tanto estos proporcionan el sistema de ejesfijos de la figura. Adema´s 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 deque las caras est´an orientadas.3.7. Pyraminx.El pyraminx es un puzzle con forma de tetraedro (so´lido plat´onico de cuatro caras). Cada unade las cuatro caras esta´ dividida en nueve facetas triangulares. 13

Hay pues un total de 4 × 9 = 36 facetas en el pyraminx. Las denotaremos como sigue:Fijemos una orientacio´n 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 so´lido. Llamaremosprimer corte X1 al contenido entre la cara x y el primer plano paralelo a la cara que contiene ax; segundo corte X2 al comprendido entre este primer plano y el siguiente paralelo al anterior ytercer corte X3 al tetraedro pequen˜o 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 gradossobre X1, rotacio´n que tambi´en llamaremos X1. Del mismo modo, es posible realizar una rotaci´onde 120 grados en el sentido de las agujas del reloj al segundo corte X2, que tambi´en llamaremosX2. Por u´ltimo, X3 representar´a tambi´en el giro de 120 grados en el sentido de las agujas delreloj sobre el tercer corte X3. Estos movimientos permutan los nombres de las 36 facetas por loque pueden verse como una permutacio´n del conjunto 1, 2, . . . , 36.Por ejemplo, la notacio´n c´ıclica disjunta para este movimiento es 14

F 3 = (23, 22, 36).Los movimientos ba´sicos 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 matema´tico 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 continuo´ ensen˜´andose. Por iron´ıas del destino la teor´ıa de grupos se convirtio´ en uno de los temas centrales de la f´ısica y todav´ıa domina el pensamiento de todos los que estamos empen˜ados 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. Esteconjunto SX se llama el grupo sim´etrico de X con la operacio´n de composicio´n, usualmentedenotado 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 IQueremos en estas l´ıneas introducir la terminolog´ıa y t´ecnicas que nos permitan analizar ma-tem´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 losposibles productos de la forma g = x1x2 . . . 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 Ges un grupo de permutaciones con generadores g1, g2, . . . , gn.Se llama orden de un grupo al nu´mero de elementos que tiene, y para cualquier elemento g deun grupo, se llama orden de g al menor entero positivo m tal que gm = 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 sologenerador, 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 per-mutaci´on del cubo, el orden del movimiento [R, U ] es seis, es decir se necesitan seis composicionesdel 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 llamaremosconmutador 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 G al generado por todos losconmutadores [g, h] de G. En el caso del grupo generado por todos los movimientos ba´sicos delcubo de Rubik, el subgrupo conmutador es relativamente grande, es decir, la mayor´ıa de losmovimientos 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. Decimosque dos elementos g1, g2 de un grupo G son conjugados si existe un elemento h en G tal queg2 = g1 ∧ h. Fijado un elemento g de un grupo G, el conjunto C(g) = {h ∗ g ∗ h−1 : h ∈ G}se llama clase de conjugacio´n de g. Del mismo modo, si H es un subgrupo de G y g es unelemento 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 accio´n de grupos sobre conjuntos. Decimos que un grupo Gactu´a sobre un conjunto X si: a) cada elemento g ∈ G define una funcio´n 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 actu´a sobre X, decimos que la acci´on es transitiva si para cada par x, y ∈ X existe ung ∈ G tal que y = g(x). La accio´n es libre si la u´nica g ∈ G que deja fijo algu´n elemento de Xes la identidad.Un ejemplo de grupo que actu´a sobre un conjunto es precisamente el grupo sim´etrico de unconjunto 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 generadopor las permutaciones R, L, U, D, F, B, entonces G actu´a sobre X.Si G es un grupo que actu´a sobre un conjunto X, se llama ´orbita de un elemento x ∈ X alconjunto Gx = {g(x) : g ∈ G}.Como aplicacio´n de esta nocio´n, si llamamos G al grupo de movimientos del cubo de Rubik, Xal conjunto de v´ertices del cubo y H al subgrupo de G generado por U ∗ R, intentar calcular elorden 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 actu´asobre el conjunto X, como el conjunto stabG(x) = Gx = {g ∈ G : g(x) = x}.Por ejemplo, si X = G y G actu´a sobre X por la conjugacio´n 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 xen G.Si X es el conjunto de las 48 facetas del cubo de Rubik (quitando las fijas), Xc el conjunto defacetas que corresponden a alguna esquina del cubo y Xe el conjunto de facetas de cualquiera delos ejes del cubo, entonces el grupo G del cubo actu´a sobre X, Xc y Xe. La accio´n de G sobreX induce la siguiente relacio´n 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 laacci´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 deuna esquina a otra esquina pero s´ı puede rotarlo y puede intercambiar los colores de un eje perono moverlo a otro eje). Tambi´en la relacio´n de equivalencia inducida por la acci´on de F sobreX tiene como clases de equivalencia Xc y Xe y sobre ambas la acci´on es transitiva. Un hechointeresante es que F es el producto directo (producto cartesiano con la operacio´n inducida porla composicio´n de G) de Fc y Fe, donde Fc es la intersecci´on de F con el grupo sim´etrico de Xcy 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, unacoclase a la izquierda de H en G es el conjunto g ∗ H, para cualquier g ∈ G; del mismomodo, una coclase a la derecha de H en G es el conjunto H ∗ g, , para cualquier g ∈ G. Elconjunto de todas las coclases a la izquierda se denota por G/H y el de coclases a la derechapor 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 delgrupo. 17

5. GRAFOS DE CAYLEY.Una interpretacio´n gra´fica de los grupos de permutacio´n, en particular los grupos de puzzles depermutaci´on, viene dada por los grafos de Cayley. Recordemos que un grafo es una colecci´on depares (V, A) formados por v´ertices o nodos V y aristas o lados A que unen pares de v´ertices, esdecir A es un subconjunto de {(v1, v2) : v1, v2 ∈ V }.Si v, w ∈ V , un camino de v a w es una sucesio´n finita de aristas que empiezan en v y terminan enw. Decimos que un grafo es conexo si cualquier par de v´ertices esta´ conectado por algu´n camino.El nu´mero de aristas que confluyen en un v´ertice v se llama valencia de v. Si dos v´erticesesta´n conectados, se define la distancia entre ellos como el nu´mero de aristas que contiene elcamino de menor taman˜o uniendo dichos v´ertices (por convenio, la distancia es infinita si losv´ertices no esta´n conectados). El di´ametro de un grafo es el ma´ximo entre las distancias de dosv´ertices.Dado un grupo de permutaciones G = {g1, . . . , gn} ⊂ SX se define el grafo de Cayley de Gaqu´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 = {R, L, U, D, F, B} ⊂ S54 es el grupo del cubo de Rubik, cada posicio´n delcubo corresponde a un v´ertice del grafo de Cayley. Cada v´ertice de este grafo tiene valencia 12.Adema´s, una solucio´n del cubo de Rubik es un camino desde el v´ertice asociado a la posici´onactual hasta el v´ertice correspondiente al elemento identidad y la distancia entre estos v´erticeses el nu´mero de m´ınimo de movimientos necesarios para resolver el cubo. El di´ametro del grafode Cayley es el menor nu´mero de movimientos necesario para resolver el cubo en el peor de loscasos.Para la mayor´ıa de los puzzles de permutacio´n, el dia´metro del grafo de Cayley asociado no esconocido.6. ESTRUCTURA DEL GRUPO DEL CUBO DE RUBIK.Resumiremos por u´ltimo algunos resultados sobre la estructura del grupo del cubo de Rubik(similar discusio´n se puede hacer con los grupos correspondientes a los dem´as puzzles de per-mutacio´n). Denotaremos como usualmente G, V, E y F al grupo generado por los movimientosb´asicos, al conjunto de v´ertices, ejes y facetas de las piezas mo´viles, respectivamente. 1) G actu´a 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 aplicacio´n 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 ningu´n movimiento del cubo de Rubik que intercambie los dos elementos de un eje pero deje invariantes a todas las dema´s 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 nu´cleo 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 comu´n 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