Teoría de grupos y el Skewb

Universidad de Sevilla Facultad de Matemáticas Teoría de grupos y el Skewb Trabajo de Fin de Grado (Grado en Matemáticas) Autor: Carlos Méndez García-Barroso Tutor: Juan González-Meneses López Índice general 0.1 Resumen ................................ 3 0.2 Abstract ................................ 3 1 Definiciones y resultados previos 4 1.1 La estructura algebraica de grupo .................. 4 1.2 Subgrupos ............................... 6 1.3 Grupo cociente ............................ 7 1.4 Homomorfismos de grupos ...................... 7 1.5 Grupos de permutaciones ...................... 8 1.6 Grupos libres ............................. 9 1.7 Acción de un grupo sobre un conjunto ............... 10 1.8 Producto directo y semidirecto ................... 11 2 El Skewb 15 2.1 Notación ................................ 15 2.1.1 Esquinas ............................ 16 2.1.2 Centros ............................ 19 2.2 La estructura de grupo del skewb .................. 19 3 Métodos de resolución 27 3.1 Método basado en la estructura de grupo ............. 27 3.1.1 Orientación de las esquinas fijas ............... 28 1 3.1.2 Permutación de las esquinas móviles ............ 28 3.1.3 Orientación de las esquinas móviles ............. 29 3.1.4 Permutación de centros ................... 30 3.2 Métodos de velocidad ........................ 31 3.2.1 Método de Sarah ....................... 31 3.2.2 Método NS .......................... 32 2 0.1 Resumen En este trabajo repasaremos algunas definiciones y resultados básicos de la Teoría de Grupos y trataremos de utilizarlos para determinar la estructura de grupo asociada al Skewb, un puzzle del tipo del cubo de Rubik. Además, cubriremos algunos métodos de resolución, incluyendo un método que se basa en la propia estructura del grupo del skewb. 0.2 Abstract In this paper, we aim to review some basic definitions and results from Group Theory and we will attempt to use them in order to determine the group structure associated to the Skewb, a Rubik’s-type twisty puzzle. Furthermore, we will cover some solving methods, including one which takes advantage of the Skewb’s group structure. 3 Capítulo 1 Definiciones y resultados previos En esta sección presentaremos las definiciones y los resultados que serán fundamentales en el desarrollo del resultado final que queremos probar. Para ello, necesitaremos recordar las bases de la teoría de grupos. Nos hemos basado en los libros An Introduction to Abstract Algebra [1], en el que también se basan los apuntes de la asignatura de Álgebra Básica, y en An Introduction to the Theory of Groups [2] y la mayoría de los resultados están enunciados sin demostración para no alargar innecesariamente esta memoria. 1.1 La estructura algebraica de grupo Definición 1.1. Un grupo es un par (G, ?)donde Ges un conjunto y ?es una operación binaria interna sobre Gque cumple las siguientes propiedades: Asociatividad La operación es asociativa. Es decir, (x ? y)? z =x ? (y ? z) para cualesquiera x, y, z ∈G. Elemento neutro Existe un elemento e∈Gque es elemento neutro de la operación. Es decir, se tiene e?x=x?e=xpara cualquier x∈G. Elemento inverso Para cada elemento de G, existe otro que al operar con el primero da el elemento neutro. Es decir, para cualquier x∈G, existe y∈Gcon y ? x =x ? y =e. Dado x∈G, notaremos a su inverso como x−1 Nota. Dado que la operación es asociativa, podemos prescindir del uso de paréntesis cuando vayamos a operar con varios elementos de Gseguidos. Además, en la práctica, suele omitirse también el símbolo que representa la operación en favor de la yuxtaposición. De esta manera, una expresión como x ? (y ? z)se puede escribir sin ninguna ambigüedad como xyz 4 Nota. Si además de cumplir los axiomas de grupo, se tiene la propiedad conmutativa (esto es, xy =yx ∀x, y ∈G), diremos que Ges un grupo abeliano Algunos ejemplos de grupos son: 1. Los números enteros con la suma: (Z,+) 2. Los números racionales no nulos con el producto: (Q×,·) 3. Las matrices del mismo orden con coeficientes sobre un cuerpo y la suma de matrices: (Mn×m(k),+) 4. Dado un conjunto X6=∅, el conjunto SX={f:X→X|fbiyectiva}es un grupo con la operación dada por la composición de aplicaciones. Cuando X={1, . . . , n}, denotamos Sn:=SX. Conocemos a este grupo como el grupo de permutaciones de X. Este ejemplo nos resultará importante más adelante, puesto que “parte” del grupo del Skewb se corresponde con un grupo de permutaciones. Proposición 1.2. Sea Gun grupo. Se tiene: 1. El elemento neutro es único. 2. Cada elemento tiene un único elemento inverso. Además, si xy =e, entonces x=y−1ey=x−1. 3. (x−1)−1=x. 4. (xy)−1=y−1x−1 5. Se tiene la propiedad cancelativa por la izquierda y por la derecha: si xy =xz, entonces y=z. Además, si xy =zy, entonces x=z. Definición 1.3. Sea Gun grupo, k∈Zyg∈G. Entonces definimos la potencia k-ésima de gcomo sigue: gk=           k veces z}|{ g . . . g si k > 0 esi k= 0 g−1. . . g−1 | {z } -k veces si k < 0 Definición 1.4. Sea Gun grupo y g∈G. Llamaremos orden de g(notado ord(g)) al menor entero positivo ktal que gk=e. Si no existe tal entero, diremos que gtiene orden infinito. Definición 1.5. Dado un grupo Gdiremos que su orden es su cardinal como conjunto y lo notaremos |G|. Proposición 1.6. Si Ges un grupo finito, entonces todos los elementos de G tienen orden finito. 5 Ahora definiremos dos conceptos que serán de especial utilidad cuando estudiemos en más profundidad el Skewb. Sin embargo, son conceptos que se pueden definir de manera general para cualquier grupo. Definición 1.7. Sea Gun grupo. Dados dos elementos g, h ∈G, definimos el conmutador de gyhcomo [g, h]:=ghg−1h−1. Definición 1.8. Sea Gun grupo. Dados dos elementos g, h ∈G, definimos el conjugado de hpor gcomo g:h:=ghg−1. Nota. La notación que vamos a usar para la conjugación no es la habitual (gh). Conjugar es algo tan común en los puzzles de tipo Rubik que tiene su propia notación, y es la que utilizaremos a lo largo del desarrollo. 1.2 Subgrupos Definición 1.9. Sea Gun grupo. Diremos que H⊆Ges un subgrupo de G (notado H≤G) si H es un grupo con “la misma” operación de G(es decir, la operación de Grestringida a H×H). Proposición 1.10. Sea Gun grupo. Entonces H≤Gsi y solo si H6=∅y xy−1∈Hpara cualesquiera x, y ∈H. Teorema 1.11. Sea Gun grupo finito y H≤G. Entonces k|H|=|G|para algún k∈Z, al que llamaremos índice de Hen G. En particular, el orden de Hdivide al orden de G. Definición 1.12. Sea Gun grupo y S⊆G. Llamaremos subgrupo generado por Sal menor subgrupo de G(respecto de la inclusión de conjuntos) que contiene aSy lo notaremos hSi. Proposición 1.13. Sea Gun grupo y S⊆G. Se tiene: 1. hSi={g1g2· · · gk|k∈N, gi∈Sog−1 i∈S∀i= 1, . . . , k} 2. hSi=\ S⊆H≤G H Definición 1.14. Sea Gun grupo y H≤G. Diremos que Hes un subgrupo normal de Gsi ghg−1=g:h∈Hpara cualesquiera h∈Hyg∈G. Notaremos esto como HCG. Nota. Con gH nos referiremos al conjunto {gh|h∈H}. Los conjuntos de esta forma se llaman clases por la izquierda de Hen G. De modo similar, los conjuntos Hg ={hg|h∈H}se llaman clases por la derecha. Proposición 1.15. Sea Gun grupo y H≤G. Las siguientes condiciones son equivalentes: 1. Hes un subgrupo normal de G. 2. ∀g, h ∈G gh ∈H⇐⇒ hg ∈H. 3. ∀g∈G gHg−1⊆H. 4. ∀g∈G gH =Hg. 6 1.3 Grupo cociente Dado un grupo Gy un subgrupo H≤G, podemos definir una relación de equivalencia en Gde la siguiente manera: Definición 1.16. Sean g, h ∈G. Diremos que gyhson congruentes por la izquierda (resp. derecha) módulo Hsi g−1h∈H(resp. gh−1∈H). Las clases de equivalencia de esta relación son las clases por la izquierda gH (resp. Hg) con g∈G. Idealmente, querríamos que el conjunto de las clases de equivalencia anteriores (notado G/H) junto con la operación natural heredada de G(esto es, (g1H)(g2H)=(g1g2)H) tuviera estructura de grupo. Sin embargo, hay que imponer una condición adicional al subgrupo H para que esto sea así, como veremos en la siguiente proposición. Proposición 1.17. Sea Gun grupo y H≤G. Son equivalentes: 1. La operación (g1H)(g2H) = (g1g2)Hestá bien definida y dota a G/Hde una estructura de grupo. 2. HCG. 1.4 Homomorfismos de grupos Definición 1.18. Sean GyHgrupos. Decimos que f:G→Hes un homomorfismo de grupos si se cumple que f(g1g2) = f(g1)f(g2)∀g1, g2∈G Nota. Diremos que un homomorfismo de grupos es un isomorfismo de grupos si es biyectivo, y diremos que dos grupos son isomorfos si existe un isomorfismo de uno al otro. Si GyHson isomorfos, lo notaremos como G≃H. Además, llamaremos automorfismo a un isomorfismo de un grupo en sí mismo. Proposición 1.19. Sean f1:G→Hyf2:H→Kisomorfismos de grupos. Se tiene: 1. f−1 1:H→Gtambién es un isomorfismo de grupos. 2. f2◦f1:G→Ktambién es un isomorfismo. 3. Como consecuencia, la relación “ser isomorfos” es una relación de equivalencia entre grupos. Esta última proposición nos dice que a ojos de la teoría de grupos, dos grupos isomorfos son realmente el mismo grupo, salvo el nombre y/o la forma de los elementos. 7 Definición 1.20. Sea Gun grupo. Llamamos grupo de automorfismos de Ga Aut(G):={f:G→G|fes automorfismo}. Proposición 1.21. Sea Gun grupo. Entonces: 1. Aut(G)es un grupo con la composición de aplicaciones como operación. 2. El elemento neutro de Aut(G)es idG:G→G. 3. Dado f∈Aut(G), su inverso es la aplicación inversa f−1∈Aut(G). Definición 1.22. Sea f:G→Hun homomorfismo de grupos. Definimos el núcleo de fcomo ker f:={g∈G|f(g) = eH}. Proposición 1.23. Sean GyHgrupos y f:G→Hun homomorfismo de grupos. Se tiene: 1. f(eG) = eH 2. im(f) = f(G)⊆Hes un subgrupo de H. 3. kerf⊆Ges un subgrupo normal de G. 4. (Primer teorema de isomorfía) G/ker fes isomorfo a im(f). 1.5 Grupos de permutaciones Dado que los grupos de permutaciones juegan un papel fundamental en el desarrollo de la teoría de grupos asociada al Skewb (y en general a cualquier puzzle de tipo Rubik), es recomendable dedicar una parte del trabajo a estos grupos. Definición 1.24. Sea n∈Ny consideremos σ∈Sn. Diremos que σes una permutación de nelementos. Una manera de representarla es mediante la matriz σ=1. . . n σ(1) . . . σ(n) Definición 1.25. Sea σ∈Sn. Llamaremos soporte de σal conjunto sop(σ):= {i∈ {1, . . . , n}| σ(i)6=i} Definición 1.26. Sea n∈Ny sea A={i1, . . . , ik}⊆{1, . . . , n}. Sea σ∈Sn tal que sop(σ) = Ayσ(ij) = ij+1 (entendiendo que k+ 1 = 1). Diremos que σ es un k-ciclo. En las condiciones anteriores, podemos denotar σcomo la matriz (i1· · · ik). Si k= 2, diremos que σes una trasposición. Definición 1.27. Sean σ, τ ∈Snciclos. Diremos que σyτson ciclos disjuntos si sus soportes son disjuntos. Teorema 1.28 (Descomposición en ciclos disjuntos).Sea σ∈Sn. Entonces σ se puede escribir como composición de ciclos disjuntos. Además, esta descomposición es única salvo orden de los ciclos. 8 Capítulo 2 El Skewb El Skewb es un puzzle de la familia del cubo de Rubik. Su nombre proviene de la combinación en inglés de las palabras skew (torcido, oblicuo) y cube (cubo) Al igual que el cubo de Rubik, tiene forma de cubo. Sin embargo, a diferencia del cubo de Rubik original, tiene 4 ejes de giro en lugar de 3, que son las rectas que pasan por pares de vértices diametralmente opuestos. El puzzle consta de 8 esquinas y 6 centros con forma de cuadrado cuyos vértices están en el centro de las aristas del cubo. Al girar alrededor de una esquina, se mueve la mitad del puzzle que rodea a dicha esquina, es decir, la propia esquina, los tres centros adyacentes a ella y las otras 3 esquinas adyacentes a ella. Mecánicamente, el Skewb consta de un núcleo de plástico del que salen cuatro tornillos a los que están unidas permanentemente cuatro de las ocho esquinas. El resto de piezas se pueden separar de este núcleo. Utilizaremos este hecho más adelante cuando tratemos de determinar la estructura de grupo asociada al Skewb. (a) Skewb del autor (b) Skewb desmontado 2.1 Notación Para poder describir bien las las matemáticas asociadas al Skewb, necesitaremos una notación para describir los movimientos que realicemos y tener nombres 15 claros para cada una de las piezas del puzzle. En lo que sigue, consideraremos que nuestro Skewb tiene la disposición de colores estándar. Esto es, las caras son de color blanco, verde, rojo, azul, naranja y amarillo. Los pares de caras opuestas son blanco-amarillo, verde-azul y rojonaranja. Las caras blanca, verde y roja están situadas alrededor de una esquina, y se recorren en ese orden en sentido antihorario. 2.1.1 Esquinas Lo primero de lo que nos damos cuenta es que cada esquina del Skewb define un movimiento, y que cada par de esquinas diametralmente opuesto produce el mismo movimiento, puesto que mueven mitades complementarias del puzzle. Por tanto, para describir los movimientos del Skewb solo necesitamos tener un nombre para 4 de las 8 esquinas. Si además elegimos estas 4 esquinas de manera que sean los vértices de un tetraedro regular, las 4 esquinas elegidas siempre quedarán fijas en su sitio, aunque quizás con una orientación distinta a la correcta. Definiremos la orientación estándar del Skewb como sigue: 1. Con el Skewb resuelto, colocamos la esquina blanco-rojo-verde mirando hacia nosotros. 2. Colocamos la cara blanca del Skewb mirando hacia arriba. Figura 2.2: Esquinas fijas A partir de aquí, llamaremos Fa la esquina de la capa superior que mira hacia nosotros (blanco-rojo-verde), Ua la esquina de la capa superior que mira hacia la parte trasera del Skewb (blanco-naranja-azul), Ra la esquina de la capa inferior que mira hacia la derecha (amarillo-rojo-azul) y La la esquina de la capa inferior que mira hacia la izquierda (amarillo-naranja-verde). De esta manera, podemos describir cualquier secuencia de movimientos como giros alrededor de estas cuatro esquinas, que nunca se moverán de sus correspondientes sitios. En adelante, nos referiremos a este conjunto de esquinas como Ef:={F, L, R, U} Una secuencia de movimientos estará formada por estas 4 letras, seguidas o no de un apóstrofe. La letra sola significa girar en sentido horario alrededor de la esquina indicada, y la letra con apóstrofe significa girar en sentido antihorario alrededor de dicha esquina. Es importante notar que dada una secuencia de movimientos, entenderemos que se realizan de izquierda a derecha. Para facilitar la visualización, incluimos el resultado de girar cada esquina en sentido horario y antihorario. 16 Figura 2.3: Giros horarios F U R L Figura 2.4: Giros antihorarios F0U0R0L0 Aunque no vayamos a utilizarlas como notación para los movimientos, necesitaremos tener un nombre para las otras esquinas del Skewb, puesto que a diferencia de las esquinas fijas, estas sí pueden cambiar de posición entre ellas. Las nombraremos con la letra minúscula correspondiente a la esquina diametralmente opuesta, que siempre será una de las esquinas fijas. Este será el conjunto de esquinas móviles Em:={f, l, r, u}. De este modo, la nomenclatura de las esquinas queda como sigue: Vista frontal Vista trasera Figura 2.5: Esquinas 17 Orientación Dado que cada esquina puede estar en un lugar dado en tres orientaciones diferentes, necesitamos una manera de definir sin ambigüedad cuándo una esquina está orientada correctamente y cuándo no. Para ello, fijada una esquina, el primer paso es determinar a cuál de los dos conjuntos de esquinas pertenece. Una vez hecho esto, observaremos si la esquina está bien orientada respecto del resto de esquinas de su mismo tipo. Para ello, elijamos una esquina x. Observemos que xtiene tres colores, y cada uno de estos colores aparece exactamente en una de las otras tres esquinas del mismo tipo que x. Si cada color de xestá en la misma cara que la otra esquina de su tipo que contiene ese color, diremos que su orientación es 0∈Z3, lo que significará que está bien orientada. Si fuera necesario girar la esquina en cuestión en sentido antihorario para que estuviera bien orientada, diremos que su orientación es 1∈Z3. Finalmente, si fuera necesario girar la esquina en sentido horario, diremos que su orientación es 2∈Z3. Determinar la orientación de las esquinas fijas es relativamente sencillo, puesto que nunca se mueven de su sitio siguiendo la notación explicada anteriormente. Sin embargo, la orientación de las esquinas móviles puede depender de cómo estén permutadas entre ellas. Por ejemplo, en el estado que resulta de aplicar la secuencia L0ULF0, vemos que las esquinas móviles siguen en su lugar, y que lyrno están bien orientadas. Más concretamente, la orientación de les 2 y la orientación de res 1. Sin embargo, si aplicamos RL0R0L, las esquinas móviles sí cambian de lugar. Por ejemplo, lyrestán intercambiadas. En este caso, lestá bien orientada puesto que el lado blanco, que apunta a r, efectivamente lo hace. Sin embargo, r no está bien orientada porque su lado blanco apunta hacia fen lugar de hacia l como debería. Como habría que girarla en sentido horario para que lo estuviera, su orientación es 2. L0ULF 0RL0R0L 18 2.1.2 Centros La notación para los centros es, comparada con la de las esquinas, bastante simple. Puesto que solo tienen una orientación, solo es necesario darles un nombre. Lo haremos asignando a cada centro un número del 1 al 6 de manera que, en el estado resuelto, centros opuestos sumen 7. Asignaremos el 1 al centro blanco, el 2 al verde y el 3 al rojo. De este modo, el resto de centros queda unívocamente determinado. Vista frontal Vista trasera 2.2 La estructura de grupo del skewb Una vez descrita la notación para el Skewb, podemos comenzar a estudiar la estructura de grupo que hay detrás de este puzzle. En primer lugar, tenemos que justificar que, en efecto, existe tal estructura de grupo. Consideremos el conjunto de todas las secuencias de movimientos finitas que podemos aplicar al Skewb. Dichas secuencias de movimientos, como ya hemos visto, son palabras en Ef∪E0 f. Llamemos Wal conjunto de todas esas palabras y consideremos la operación interna que consiste en la concatenación de palabras, que dota a Wde la estructura de monoide. Por otro lado, observemos que un Skewb tiene 30 pegatinas diferentes (3 en cada una de las 8 esquinas y una en cada centro), y que una secuencia de movimientos induce una permutación de esas 30 pegatinas, que podremos considerar como un elemento de S30. Nos referiremos a estas permutaciones como estados del Skewb. Nota. A lo largo del resto del trabajo, para ser consistentes y poder leer los movimientos de izquierda a derecha, también leeremos las permutaciones de izquierda a derecha. Para ello, consideraremos SnyAncon la operación ·definida como σ·τ:= τ◦σ. Es importante notar que no nos interesan todos los estados posibles del Skewb, sino solo aquellos a los que se puede acceder desde el estado resuelto aplicando movimientos. Tal como lo hemos definido, S30 contiene estados que suponen 19 intercambiar una pegatina de una esquina con una de un centro, por ejemplo, algo que obviamente no puede ocurrir en un Skewb solo mediante movimientos. Para determinar exactamente qué estados son válidos, vamos a definir una aplicación α:W→S30 de manera que asociemos a cada secuencia de movimientos el estado en que esta deja al Skewb. Esta aplicación envía la operación de W(la concatenación) en la operación ·de S30, de modo que es un morfismo entre monoides. Veamos que im(α)≤S30. Sean σ1, σ2∈im(α). Entonces, existen w1, w2∈Wcon α(wi) = σi, i = 1,2. De la manera en que hemos definido α, se tiene que α(A0) = α(A)−1∀A∈Ef. Con esto y usando que αpreserva la concatenación, podemos decir que σ1·σ−1 2=α(w1w−1 2)∈im(α), entendiendo por w−1 2la palabra que resulta de invertir el orden de w2y cambiar los movimientos en sentido horario por movimientos antihorarios y viceversa. Tenemos entonces que im(α), que llamaremos Gen adelante, es un grupo formado por los estados válidos de αy lo llamaremos el grupo del Skewb. Observemos ahora atentamente la factorización canónica de α=i◦α◦πS, donde: •πS:W→W/∼Ses la proyección natural de Wen W/∼Sdonde ∼S es la relación de equivalencia que relaciona palabras con la misma imagen por α.πSes sobreyectiva y preserva la concatenación de palabras. •α:W/∼S→Ges una aplicación biyectiva que lleva la concatenación de representantes de las clases en el producto ·en S30. •i:G→S30 es la inclusión, que es inyectiva y preserva la operación ·. Como podemos observar, tenemos a W/∼Sen biyección con G, que es un grupo. Además, esta biyección lleva la concatenación en W/∼Sen el producto ·de S30, lo que hace a W/∼Sun grupo (isomorfo a G) con la operación interna que consiste en concatenar representantes de las clases. Podemos entonces identificar W/∼Scon el grupo del Skewb, y en adelante lo denotaremos por M. Por otro lado, observamos que, si ∼es la relación de equivalencia que da lugar al grupo libre, dos palabras equivalentes por ∼también lo son por ∼S, puesto que las secuencias de la forma AA0dejan al Skewb en el mismo estado en que estuviera. Por tanto, podemos definir las aplicaciones πF:W→FEf yπ:FEf→Mde manera que πS=π◦πFyπes sobreyectiva y preserva la concatenación de palabras, por lo que es un homomorfismo de grupos. Por el primer teorema de isomorfía, tenemos además que FEf/kerπ≃M≃G. En adelante llamaremos Na kerπ. Es interesante observar que Nes, por definición, el conjunto de secuencias de movimientos que dejan al Skewb invariante. Con lo que hemos visto hasta ahora, tenemos el siguiente diagrama: WπF FEf π Mα −→ Gi ,→S30 Y tenemos tres maneras de ver los elementos del grupo del Skewb: 20 • Como secuencias de movimientos en FEf, considerando dos de ellas equivalentes si al aplicar una seguida de la inversa de la otra, no afectamos al Skewb. • Como palabras de W, considerando dos de ellas equivalentes cuando tienen la misma imagen por α. • Como permutaciones de S30 Sin embargo, estas representaciones no aportan detalle acerca de la estructura de grupo del Skewb, por lo que tendremos que encontrar una manera más explícita de expresar cada estado del puzzle. Para ello, vamos a considerar el grupo V:= Z4 3×(Z4 3oϕA4)×A6, con ϕ:A4→Aut(Z4 3)dada por ϕσ(a1, a2, a3, a4) = (aσ(1), aσ(2), aσ(3), aσ(4)). La operación en Vqueda como sigue: (u1,v1, σ1, τ1)(u2,v2, σ2, τ2) = (u1+u2,v1+ϕσ1(v2), σ1·σ2, τ1·τ2) Antes de proseguir, vamos a justificar brevemente la elección de este producto, que a priori podría parecer totalmente arbitrario. Este grupo es un producto directo de otros tres grupos, que se corresponden a los tres tipos de piezas distintas que tiene el Skewb: • El primer Z4 3recoge la información sobre la orientación de las 4 esquinas fijas. • El factor Z4 3oA4se corresponde con las esquinas móviles. Aquí recogemos tanto su orientación como su permutación. Notamos que escogemos A4 puesto que cualquier giro en el Skewb realiza un 3-ciclo en las esquinas móviles, de modo que todas las permutaciones que podremos alcanzar son pares. El producto semidirecto aparece, como veremos, porque si hacemos dos secuencias de movimientos seguidas, después de la primera las esquinas móviles podrían no estar en su sitio, y de esta manera los cambios de orientación provocados por la segunda secuencia se aplican a las esquinas correctas. •A6se corresponde con la permutación de los centros que, de nuevo, es siempre par porque cada giro produce un 3-ciclo de centros. Más adelante veremos que el grupo del Skewb no es isomorfo a Vcompleto, sino que es isomorfo a un subgrupo suyo. En primer lugar, vamos a definir una aplicación g:G→Vde la siguiente manera: dado un estado del Skewb,s∈G, necesitamos aportar la siguiente información: • La orientación de las esquinas fijas (como está definida en la sección anterior), que colocaremos en orden alfabético (esto es, FLRU) en un vector u∈Z4 3. 21 • La orientación de las esquinas móviles, que colocaremos igualmente en orden alfabético (flru) en otro vector v∈Z4 3. • La permutación σde las esquinas móviles, de manera que las esquinas estén numeradas de 1 a 4 en orden alfabético (f=1, l=2, r=3, u=4). • La permutación τde los centros, utilizando la numeración de la sección anterior. Con esto, construimos g(s) = (u,v, σ, τ). Proposición 2.1. ges un homomorfismo de grupos inyectivo. Prueba. En primer lugar, probaremos que ges un homomorfismo: supongamos que tenemos un estado del cubo s1∈G, le aplicamos uno de los generadores (por ejemplo α(F)) y obtenemos s2. Supongamos también que: g(s1) = ((a1, a2, a3, a4),(b1, b2, b3, b4), σ, τ) g(s2) = g(s1·α(F)) = ((a0 1, a0 2, a0 3, a0 4),(b0 1, b0 2, b0 3, b0 4), σ0, τ0) y veamos detalladamente qué ocurre al realizar el movimiento F. • Todas las esquinas fijas permanecen orientadas como estuvieran salvo F, que hemos girado en sentido horario. Por tanto, a0 1=a1+ 1 ya0 i=ai, i = 2,3,4. • Los centros que están en las posiciones 1, 3 y 2 se han movido en un 3-ciclo (en este mismo orden), de modo que τ0=τ·(132). • Las esquinas móviles l,u, y r(que se corresponden con 2, 4 y 3 respectivamente en nuestra representación) se han movido en un 3-ciclo en ese mismo orden, así que σ0=σ·(243). • La esquina móvil que estuviera en la posición de fgira en sentido horario respecto de las demás esquinas móviles. El resto de esquinas móviles permanece con la misma orientación que tenga antes de realizar F, puesto que el movimiento mantiene unidas a las otras tres esquinas. Por tanto, b0 σ−1(1) =bσ−1(1) + 1 yb0 i=bien otro caso. Por otro lado, si calculamos directamente g(s1)g(α(F)) en V(g(α(F)) se determina como explicamos antes) tenemos: g(s1)g(α(F)) = ((a1, a2, a3, a4),(b1, b2, b3, b4), σ, τ)((1,0,0,0),(1,0,0,0),(243),(132)) = ((a1+ 1, a2, a3, a4),(b0 1, b0 2, b0 3, b0 4), σ ·(243), τ ·(132)) = g(s2) = g(s1·α(F)) Esta misma comprobación se puede hacer para el resto de generadores y sus inversos. Por inducción en el número de generadores de una secuencia (teniendo en cuenta que genvía el elemento neutro de Gen el elemento neutro de V), esto demuestra que gpreserva productos, es decir, que es un homomorfismo de grupos. Además, es claro que ges inyectivo porque si un estado del Skewb se envía al elemento neutro de V, ese estado tiene que ser el estado resuelto. 22 A partir de g, podemos definir una aplicación f:FEf→Vsimplemente como f=g◦α◦π. Notemos que gracias a la propiedad universal de los grupos libres, nos basta conocer las imágenes de los elementos de Efpara determinar la imagen por fde cualquier otro elemento de FEf. Esas imágenes son: •F7→ ((1,0,0,0),(1,0,0,0),(243),(132)) •L7→ ((0,1,0,0),(0,1,0,0),(134),(264)) •R7→ ((0,0,1,0),(0,0,1,0),(142),(356)) •U7→ ((0,0,0,1),(0,0,0,1),(123),(145)) Proposición 2.2. kerf=N Prueba. Puesto que f=g◦α◦πy tanto gcomo αson inyectivas, ker f= kerπ=N. Proposición 2.3. Ges isomorfo a im(f). Prueba. Por el primer teorema de isomorfía, FEf/kerf≃im(f). Como ker f= N,im(f)≃FEf/kerf≃FEf/N≃M≃G A continuación veremos exactamente cuál es la imagen de f. Para ello, necesitamos definir antes una aplicación especial. A4tiene un subgrupo normal propio K4={(),(12)(34),(13)(24),(14)(23)}, que suele llamarse grupo de Klein. Al tomar el cociente de A4por K4, obtenemos tres clases por la izquierda, que son: •K4={(),(12)(34),(13)(24),(14)(23)} •(123)K4={(123),(134),(142),(243)} •(132)K4={(132),(143),(124),(234)} El homomorfismo κ:A4/K4→Z3determinado por κ((123)K4)=1es un isomorfismo de grupos, y a partir de él podemos definir λ:A4→Z3como λ(σ) = κ(π(σ)), donde πes la proyección natural de A4en el cociente A4/K4. Con esta definición, podemos determinar im(f). Proposición 2.4. im(f) = H:=((u,v, σ, τ)| 4 X i=1 ui= 4 X i=1 vi=λ(σ))⊆Z4 3×(Z4 3oA4)×A6 Prueba. Por doble inclusión: 23 ⊆Dada una secuencia s∈FEf, tenemos que demostrar que f(s)∈H. Lo haremos por inducción en la longitud de s. k= 1 Se comprueba que para los cuatro generadores y sus inversos se tiene la condición: si denotamos por (u,v, σ, τ)a las imágenes de los generadores, para todos se tiene que P4 i=1 ui=P4 i=1 vi=λ(σ) = 1 y para los inversos, P4 i=1 ui=P4 i=1 vi=λ(σ) = 2 k=⇒k+ 1 Sea s=m1. . . mk+1 ∈FEf. Tenemos que f(m1. . . mk), f(mk+1)∈ Hpor hipótesis de inducción. Veamos que f(s)∈H. Llamemos (u,v, σ, τ) = f(m1. . . mk)y(u0,v0, σ0, τ0) = f(mk+1). Entonces f(s) = (u,v, σ, τ)(u0,v0, σ0, τ0) = (u+u0,v+ϕσ(v0), σ ·σ0, τ ·τ0) Antes de continuar, notamos que las coordenadas de v0y las de ϕσ(v0) tienen la misma suma, puesto que el segundo vector no es más que una reordenación del primero. Finalmente, tenemos: X i=1 (u+u0)i= 4 X i=1 (ui+u0 i) = 4 X i=1 ui+ 4 X i=1 u0 i X i=1 (v+ϕσ(v0))i= 4 X i=1 (vi+v0 σ(i)) = 4 X i=1 vi+ 4 X i=1 v0 σ(i)= 4 X i=1 vi+ 4 X i=1 v0 i λ(σ·σ0) = λ(σ) + λ(σ0) Por la hipótesis de inducción, estos tres números son iguales, de modo que f(s)∈H. ⊇Dado un elemento h∈H, tenemos que encontrar una secuencia de movimientos cuya imagen sea h. Esto es equivalente a encontrar una secuencia de movimientos s∈FEfque lleve ha la posición trivial eV= (0,0,(),()), puesto que si tenemos tal secuencia s=s1. . . sk, se obtiene fácilmente una preimagen de h: hf(s) = eV=⇒h=f(s)−1=f(s−1) = f(s−1 k. . . s−1 1) Por ahora vamos a omitir esto, puesto que en la siguiente sección daremos un método de resolución, con lo cual tendremos esta inclusión. Con estos resultados, ya podemos deducir algunas propiedades interesantes del Skewb, como por ejemplo: • No se pueden intercambiar únicamente dos centros. • Existen secuencias de movimientos que intercambian tres centros. • No se pueden intercambiar únicamente dos esquinas móviles. 24 tres elementos porque se trata de una permutación par. El algoritmo termina porque en cada paso estamos resolviendo al menos un centro, y en el momento en que quedan tres centros por resolver, la única posibilidad es realizar exactamente el 3-ciclo que los resuelve a los tres. 3.2 Métodos de velocidad El método que acabamos de presentar, a pesar de ser simple e intuitivo una vez conocida en detalle la estructura del grupo del Skewb, no es el método más indicado si nuestro objetivo es resolver el Skewb en el menor tiempo posible. Si queremos métodos más apropiados para este fin, lo mejor que podemos hacer es recurrir a la comunidad de los speedcubers, que son personas que se dedican a resolver puzzles de tipo Rubik (incluyendo el Skewb) en el menor tiempo posible. En esta sección vamos a hablar sobre dos de los métodos más populares que usan los speedcubers para resolver el Skewb: el método Sarah, nombrado por su creadora, la canadiense Sarah Strong [4], y el método NS, desarrollado por un conjunto de speedcubers de todo el mundo, entre ellos el navarro Julio Perugorria, del que el autor ha aprendido gran parte de lo que sabe sobre el Skewb. 3.2.1 Método de Sarah El primer paso en ambos métodos es igual, de modo que solo lo explicaremos una vez. Ambos métodos comienzan la solución resolviendo una “cara”, que consiste en elegir un centro y resolver las cuatro esquinas que lo rodean, como se ve en la figura. Vista frontal Vista trasera Ejemplo de un Skewb con una cara resuelta 31 Este paso hace que todas las esquinas estén ya bien permutadas y orienta dos esquinas de cada tipo. Como además hemos resuelto un centro, hemos reducido el conjunto de posiciones posibles a Z3×Z3×A5, lo cual supone que hay 540 posiciones distintas a partir de este punto. Teniendo en cuenta que esto cuenta como distintas posiciones que son iguales salvo una rotación, obtenemos que hay 135 casos esencialmente distintos, que en el método de Sarah se resuelven aplicando repetidamente las secuencias S=L0ULF0y su inversa (S0), posiblemente con rotaciones entre cada aplicación. Dependiendo de la cantidad de pasos que se den para resolver el Skewb una vez resuelta la cara, podemos hablar de tres variantes del método: 1. Sarah principiantes: esta variante resuelve el Skewb en tres pasos, que son: (a) Orientar las esquinas. (3 casos) (b) Resolver el centro opuesto al de la cara resuelta. (2 casos) (c) Resolver los cuatro centros restantes. (4 casos) 2. Sarah intermedio: esta variante resuelve el Skewb en dos pasos: (a) Orientar las esquinas y resolver el centro opuesto al de la cara resuelta. (11 casos) (b) Resolver los cuatro centros restantes. (4 casos) 3. Sarah avanzado: Tras resolver la cara, se aplica la secuencia más corta de S,S0y rotaciones que resuelve el Skewb (135 casos) 3.2.2 Método NS El primer paso del método NS es, de nuevo, resolver una cara del Skewb. El segundo y último paso consiste en reconocer la posición del puzzle y aplicar una de 135 secuencias [5] de movimientos que lo resuelve directamente. La diferencia entre el método NS y la versión avanzada del método de Sarah es que las secuencias de movimientos que se usan en NS no están necesariamente compuestas de SyS0y rotaciones, sino que son secuencias normalmente más cortas. Esto hace que el método sea considerablemente más rápido, pero tiene la desventaja de que requiere una gran cantidad de memorización y práctica por parte de alguien que lo quiera aprender en su totalidad. Es por esto que la mayoría de speedcubers que se centran en el Skewb utilizan una especie de híbrido entre Sarah avanzado y NS. Podríamos preguntarnos cuál sería el método más eficiente para resolver el Skewb. Este sería un método que, dada cualquier posición válida, la resolvería en el mínimo número de movimientos posible. Esto da pie a su vez a preguntarse cuál es el número de movimientos necesario para resolver cualquier posición. Este número cambia dependiendo del puzzle que estemos tratando, y se suele llamar número de Dios de dicho puzzle. Un 32 hipotético método que devolviera soluciones óptimas para todos los estados se llama método de Dios. En el caso del Skewb, el número de posiciones es lo suficientemente pequeño como para que haya programas de ordenador capaces de devolver una solución óptima para cualquier estado válido. Gracias a estos programas, sabemos que el número de Dios del Skewb es 11 [6], lo cual significa que cualquier posición válida se puede resolver en 11 movimientos o menos. 33 Bibliografía [1] Robinson, D.J.S. An Introduction to Abstract Algebra, Walter De Gruyter, 2003 https://p4mriunpat.files.wordpress.com/2011/10/ derek-j-s-robinson-an-introduction-to-abstract-algebra.pdf [2] Rotman, J.J., An Introduction to the Theory of Groups, Springer, 4ª edición, 1999 [3] Jürgen Voigt The Skewb Group. Technische Universität Dresden, 2013 http://www.math.tu-dresden.de/~voigt/vopubl/vopu_n/skewb-04. pdf [4] Método de Sarah: https://sarah.cubing.net/skewb/my-method [5] Método NS: Jhon Taboada, Rohan Krishna, Jayden McNeill https://drive.google.com/file/d/0B040UViKV9ljVTZFakQwMFhlWUU/ view [6] Jaap Scherpuis https://www.jaapsch.net/puzzles/skewb.htm 34