• Author / Uploaded
• Alejandro Callapiña

• Categories
• Matemáticas
• Ciencia
• Ciencia (general)
• Educación avanzada
• Ciencia y Tecnología

Citation preview

“UNIVERSIDAD ANDINA DEL CUSCO” FACULTAD DE INGENIERIA Y ARQUITECTURA ESCUELA PROFESIONAL DE INGENIERIA DE SISTEMAS

FUNDAMENTOS MATEMATICOS Y ALGORITMICOS EN LA RESOLUCION DEL CUBO RUBIK 2017 - I ASIGNATURA ALGORITMICA Y LABORATORIO DE PROGRAMACION I DOCENTE

: MGT. RAMIRO MORA JIMENEZ

ESTUDIANTES Y CÓDIGO

:



Juan Alejandro Callapiña Condori

CUSCO – PERU 2017

016100266F

:

PRESENTACIÓN

El presente trabajo de Responsabilidad Social, junto al trabajo de investigación realizado, pretende desarrollar el tema de que lleva como título: “Fundamentos Matemáticos y Algorítmicos en la Resolución del Cubo Rubik”; la cual junto a sus respectivos temas y subtemas, será analizada y redactado, rigiéndose a las normas establecidas por la Mgt. Ramiro Mora Jimenez, para una correcta y concisa presentación del trabajo. Pretendemos como estudiantes de la Universidad Andina del Cusco, realizar una correcta investigación del tema y servir de base de conocimientos para nuestros compañeros.

08 de mayo de 2017.

2

INTRODUCCIÓN

El Design Thinking es un concepto cuya metodología se ha venido implementando gradualmente en los últimos años en diferentes empresas como una forma de crear productos y servicios que tiendan a satisfacer en mejor manera las necesidades de los usuarios haciéndolos parte activa del proceso de creación. Parte de la importancia y el protagonismo que ha empezado a tener en los últimos años están directamente relacionados con la innovación y la creatividad; aquello que permite a las empresas crear productos capaces de cambiar las reglas del mercado (como en el caso de Apple), y en la necesidad cada vez más evidente que tienen las organizaciones hoy en día de crear nuevos modelos y formas de entender los problemas a los que se enfrentan, no bajo la lupa de las formas tradicionales, sino de nuevos esquemas en tanto quieran diferenciarse y asumir un papel cada vez más destacado dentro del mercado y su entorno competitivo. Es una herramienta de gran utilidad enfocada a fomentar la innovación en las organizaciones de una forma eficaz y exitosa. Esto se debe a que, gracias a su aplicación, se generan importantes beneficios en el diseño de soluciones, permitiendo a las empresas obtener mejores resultados en su comercialización. En otras palabras, el “design thinking” es un enfoque que se sirve de la sensibilidad del diseñador y su método de resolución de problemas para satisfacer las necesidades de las personas de una forma que sea tecnológicamente factible y comercialmente viable.

3

ÍNDICE

 Presentación  Introducción  El Cubo Rubik o ¿Qué es Cubo Rubik?........................................................……..……..4 o ¿En que Consiste el proceso del Cubo Rubik? o Matematicas del Cubo Rubik  Resolución del Cubo Rubik o Armar el cubo rubik por método sencillo o Armar el cubo rubik por método fridich  Conclusiones  Bibliografía

4

EL CUBO RUBIK

¿Qué es el cubo Rubik? El cubo de Rubik es un rompecabezas mecánico tridimensional inventado por el escultor y profesor de arquitectura húngaro Erno Rubik en 1974. Originalmente llamado "cubo mágico", el rompecabezas fue licenciado por Rubik para ser vendido por Ideal Toy Corp. en 1980. Ganó el premio alemán a mejor juego del año en la categoría "Mejor Rompecabezas" ese mismo año. Hasta enero de 2009 se han vendido 350 millones de cubos en todo el mundo, haciéndolo el juego de rompecabezas más vendido. Es considerado, en general, el juguete más vendido del mundo. Un cubo de Rubik clásico, posee seis colores uniformes (tradicionalmente blanco, rojo, azul, naranja, verde y amarillo). Un mecanismo de ejes permite a cada cara girar independientemente, mezclando así los colores. Para resolver el rompecabezas, cada cara debe volver a quedar en un solo color. El cubo celebró su 25º aniversario en 2005 por lo que salió a la venta una edición especial del mismo en la que la cara blanca fue remplazada por una reflejante en la que se leía "Rubik's Cube 1980-2005". En su 30º aniversario, en 2010, se comercializó otra edición especial que estaba fabricada en madera. Existen variaciones con diversos números de cuadrados por cara. Las principales versiones que hay son las siguientes: el 2×2×2 "Cubo de bolsillo", el 3×3×3 el cubo de Rubik estándar, el 4×4×4 (La venganza de Rubik). El cubo de Rubik consta de: 8 piezas-vértice de 3 colores, 12 piezas-arista de 2 colores, 6 piezas centrales y la estructura. MATEMATICAS DEL CUBO RUBIK Permutaciones El cubo de Rubik original (3×3×3) tiene ocho vértices y doce aristas. Hay (40 320) formas de combinar los vértices del cubo. Siete de estas pueden orientarse independientemente y la orientación de la octava dependerá de las siete anteriores, dando (2187) posibilidades. A su vez hay (239 500 800) formas de disponer las aristas, dado que una paridad de las esquinas implica asimismo una paridad de las aristas. Once aristas pueden ser volteadas independientemente y la rotación de la duodécima dependerá de las anteriores, dando (2048) posibilidades. En total el número de permutaciones posibles en el Cubo de Rubik es de: = 43 252 003 274 489 856 000 Es decir, cuarenta y tres trillones doscientos cincuenta y dos mil tres billones doscientos setenta y cuatro mil cuatrocientos ochenta y nueve millones ochocientos cincuenta y seis mil permutaciones.24 El rompecabezas es a menudo promocionado teniendo solo "millardos" de posiciones, ya que números más grandes no son muy familiares para la mayoría de la gente. Caras centrales El cubo de Rubik original no tenía marcas en las caras centrales (aunque algunos traían las palabras "cubo de Rubik" en el cuadrado central de la cara blanca), y por ende resolverlo no requería prestar atención en orientar correctamente dichas caras centrales. Sin embargo, algunos cubos han sido producidos comercialmente con marcas en todos los centros, como el cuboku. Teóricamente puede resolverse un cubo teniendo los centros rotados; pero se convierte en un desafío adicional resolver también los centros.

5

Marcar los centros del cubo de Rubik aumenta su dificultad debido a que expande el conjunto de posibles configuraciones distinguibles. Hay 46/2 (2048) maneras de orientar los centros, dado que una paridad de los vértices implica un número par de movimientos simples de los centros. En particular, cuando el cubo es resuelto, aparte de las orientaciones de las caras centrales, siempre existirá un número par de caras centrales que requieren un giro de 90º. Las orientaciones de los centros incrementan el número total de permutaciones posibles del cubo de 43 252 003 274 489 856 000 (4.3 × 1019) a 88 580 102 706 155 225 088 000 (8.9 × 1022).25 Girar un cubo alrededor de su propio eje es considerado un cambio de la permutación, ya que involucra contar las posiciones de las caras centrales. En teoría, existen 6! formas de disponer las seis caras centrales del cubo, pero solo 24 de estas son posibles sin tener que desarmar el cubo. Cuando las orientaciones de los centros también son contadas, el total de las permutaciones incrementa de 88 580 102 706 155 225 088 000 (8.9 × 1022) a 2 125 922 464 947 725 402 112 000 (2.1 × 1024). Teoría de grupos Sea P el conjunto de permutaciones del Cubo de Rubik. Podemos definir la operación "seguida por", denotada por →, como →: P × P → P tal que a → b := b ∘ a: es decir, a → b es el resultado de ejecutar primero a y luego b. Llamaremos secuencia o algoritmo a cualquier expresión de la forma a1 → a2 → ... →an, donde a1, a2, ... , an son giros. Afirmación: (P, → ) es un grupo. Demostración: 

Asociativa: (a → b ) → c = c ∘ (b ∘ a) = (c ∘ b) ∘ a = a → (b → c).



Elemento neutro: la permutación trivial, la cual denotaremos por



ningún giro, es decir, P → = → P = P. Inversos: cada permutación tiene inversa. En efecto, si P = a1 → a2 → ... →an es una secuencia y

, que corresponde a no hacer

definimos Q = an-1 → ... → a2-1 →a1-1, se comprueba trivialmente que P → Q = Q → P = Algoritmos

.

En la terminología de los aficionados al cubo de Rubik, una secuencia memorizada de movimientos que tiene un efecto deseado en el cubo es llamado algoritmo. Esta terminología deriva del uso matemático de algoritmo, un conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos. Cada método de resolver el cubo emplea su propio conjunto de algoritmos, junto a descripciones de cuál es el efecto del algoritmo y cuándo puede ser usado para llevar al cubo a un estado más cercano a estar resuelto. Muchos algoritmos son diseñados para transformar solo una pequeña parte del cubo sin desarmar otras partes ya resueltas y así poder ser aplicados repetidamente a diferentes partes del cubo hasta que quede resuelto. Por ejemplo, hay algoritmos para intercambiar tres vértices o cambiar la orientación de dos vértices sin cambiar al resto del rompecabezas. Algunos algoritmos tienen un efecto deseado en el cubo (por ejemplo, intercambiar dos vértices) pero pueden tener efectos colaterales (como permutar dos aristas). Dichos algoritmos son a menudo más simples que otros sin efectos no deseados y son más comúnmente empleados al principio, cuando la mayor parte del rompecabezas no ha sido resuelto y los efectos secundarios no son importantes. Hacia el final de la solución son usados algoritmos más específicos (y por lo general más complejos) para evitar mezclar partes del cubo que ya han sido resueltas. (Wikipedia, 2017)

6

RESOLUCIÓN DEL CUBO RUBIK ARMAR EL CUBO RUBIK POR MÉTODO SENCILLO Este método consiste en resolver el cubo de Rubik por capas, primero la superior, luego la central, y por último la inferior. Además este tutorial está complementado con unas animaciones que podéis mover con el ratón y que mostrarán en todo momento los movimientos que tendréis que realizar. Para conseguir buenos tiempos, hace falta un cubo de Rubik bueno. Debemos saber 3 herramientas que deben hacer: 1.- Experimentar: Jugar con el cubo y familiarizarse con él, Intentar resolver los pasos mas rápido. 2.- Notación: Aprender las letras usadas para indicar las rotaciones de seis caras y describir los algoritmos 3.- Practicar: Practicar los movimientos, memorizar los algoritmos hasta que se pueda resolver el cubo rubik sin ayuda.

Dividimos la solución en 7 pasos: Paso: 1. La Cruz superior: Primero vamos a elegir por qué cara de nuestro cubo vamos a empezar. En la mayoría de casos se recomienda usar la cara blanca, y finalizar con la cara amarilla, En este paso solo tenemos que crear una cruz en la cara superior, de forma que los colores también coincidan en las capas anexas, vamos, como podéis ver en el dibujo. A continuación explicamos cómo colocar cada una de las 4 aristas que forman dicha cruz en su sitio. Primero tendremos que buscar la arista a colocar en las otras dos capas, si la arista ya estuviese en la capa superior pero de forma incorrecta, primero tendremos que girar la capa lateral en la que esté 180º.

2. Completar la capa superior: Ahora nos toca completar la primera capa, como en el dibujo. Para ello solo tenemos que colocar los 4 vértices que faltan, cosa que haremos uno a uno. Ojo, debemos colocar los vértices en su sitio, no solo poniendo el color blanco arriba, sino también haciendo que coincidan los colores de las caras laterales.

7

3. Completar la segunda capa: Nos toca completar ahora la segunda capa, para lo que solo tendremos que colocar en su sitio 4 aristas. Como la parte de arriba ya está hecha y no nos va a aportar mucha información, girad el cubo dejando la primera capa (la que hemos resulto) debajo. Ahora en la capa superior tenemos que buscar una arista que pertenezca a la cara central. Una v ez localizada, giramos la cara superior hasta que la arista coincida en su lateral con el centro de mismo color. Puede ser que en algún momento, la capa intermedia esté sin terminar, pero las aristas que falten no estén en la capa superior, sino en la central pero mal colocadas. Lo que tendremos que hacer entonces es coger una arista cualquiera de la cara superior y meterla en el hueco de la capa intermedia donde haya una arista mal colocada. Esa arista mal colocada pasará entonces a la capa superior y ya podremos colocarla con los movimientos que toquen. 4. Cruz en la Última Cara: La cosa es cada vez menos intuitiva, pero tranquilos, que lo que queda va a resultar muy mecánico. Para empezar tenemos que formar una cruz (en los ejemplos amarilla) en la última capa, pero sin preocuparnos porque coincida con las caras laterales. Si os fijáis, en realidad lo que hay que hacer es que la cara amarilla de las 4 últimas aristas esté en la última cara. A veces con suerte tendremos la cruz hecha 5. Extender la Cruz a la última capa: Ahora tenemos que conseguir que nuestra cruz coincida también con las caras anexas. Para ello lo primero que vamos a hacer es girar la capa de arriba hasta que haya por lo menos 2 colores laterales de dicha cruz en su posición correcta. En algunas ocasiones podremos poner así los 4 colores, pero en la mayoría de los casos, solo lo podremos conseguir con dos colores 6. Colocar los últimos vértices (sin orientar): En este penúltimo paso, debemos de colocar los 4 últimos vértices en su sitio, pero sin importarnos si quedan como girados. Como podéis ver en la imagen, por ejemplo el vértice naranja-amarillo-verde está en su sitio pero a falta de un giro. Ya lo giraremos en el siguiente paso. Se nos pueden dar hasta 4 casos

7. Guiara los vértices y así, acabar el cubo: Por fin llegamos al último paso. Solo nos queda girar los vértices para tener ¡el cubo resuelto! Este paso es algo distinto a los demás, así que por favor, Leer bien antes de empezar. Por si no os aclaráis, más abajo incluyo otra forma de resolverlo, similar a las anteriores, pero con muchos movimientos a aprender. En cualquier caso os recomiendo la primera forma.

(Angosto Hernandez, 2017)

ARMAR EL CUBO RUBIK POR MÉTODO FRIDICH Trataré de explicar el Método Fridrich, un algoritmo para solucionar el cubo a nivel experto, es decir, dirigido a quienes ya saben resolverlo y buscan la manera de mejorar sus tiempos.

8

ACLARACIONES PREVIAS, NOTACIÓN Y DEFINICIONES Este algoritmo toma su nombre de Jessica Fridrich, quien lo ideó, desarrolló y mejoró durante varios años. Es uno de los métodos denominados "capa a capa", y diferentes de los métodos conocidos como de "bordes de esquinas". Lo publicó en internet por primera vez en enero de 1997. Hoy en día es el método más empleado por los speedcubers de todo el mundo, pero no es el único: Lars Petrus desarrolló el suyo propio Para comenzar con el tutorial, es importante conocer la definición de algunos términos con los que nos encontraremos más adelante. Pero, ante cualquier duda de vocabulario relacionada con el universo Rubik aquí hay un diccionario que esta completo: o o o o o o

Cubo: así de nominaremos al cubo en su conjunto. Piezas: son los "cubitos" que forman el cubo. Pueden ser de tres tipos: centros, aristas o esquinas. Cara: cualquiera de los seis lados que forman el cubo, cada uno de un color. Capa: además de las seis caras, las "rodajas" horizontales y verticales intermedias. Girar una cara/capa: girar 90º la cara o la capa a la que se refiere. Girar una pieza: se refiere a cambiar la orientación de una pieza, pero sin cambiar la posición en que se encuentra. o Colocar una pieza: se refiere a cambiar la posición de la pieza y colocarla en su posición correcta, aunque quede mal orientada. o Rotar el cubo: girar el cubo en torno a un eje, pero sin girar ninguna capa. Secuencia: fórmula compuesta de varios giros distintos con la que buscamos girar o colocar correctamente una o varias piezas. o Algoritmo: conjunto de secuencias encaminadas a resolver el cubo. También lo llamamos método o sistema. También es importante la siguiente lista para comprender las secuencias y saber qué capa debemos mover, en qué sentido y cuántos grados: o Los giros serán de 90º (un cuarto de vuelta). o R = giro en el sentido de las agujas del reloj. o R' = giro en el sentido contrario a las agujas del reloj. o R2 = giro de 180º (media vuelta). r = giro de dos capas simultáneamente en el sentido de las agujas del reloj. o r' = giro de dos capas simultáneamente en el sentido contrario a las agujas del reloj. o r2 = giro de 180º (media vuelta) de dos capas simultáneamente o y = rotación del cubo en el sentido de las agujas del reloj, sin girar ninguna capa. o y' = rotación del cubo en el sentido contrario a las agujas del reloj, sin girar ninguna capa. o y2 = rotación de 180º (media vuelta) del cubo, sin girar ninguna capa. o (R)n = repetir la secuencia entre paréntesis el número de veces "n" del superíndice.

9

El método Fridich se divide en 4 pasos: Cruceta inicial (CROSS), Primeras dos capas (F2L), Orientación última capa (OLL) y Permutación última capa (PLL). Por eso también se conoce el método como CFOP (abreviaturas de Cross-F2L-OLLPLL) La Cruceta Inicial es el sencillo, al igual que el método tradicional, formar una cruz en la parte superior Primeras dos capas (F2L) Se corresponde con el segundo paso del método de Jessica Friddich, y nos enseña cómo resolver las dos primeras capas del cubo simultáneamente. Partiendo de la cruceta inicial, daremos la vuelta al cubo de forma que la cruceta quede en la cara inferior, por lo que nosotros veremos en la cara superior el color verde (insisto, en mi caso, porque empiezo resolviendo la cara de color azul). A partir de este momento nos referiremos a la cara verde como cara superior y, por consiguiente, a la cara azul como cara inferior. Con las secuencias propuestas colocaremos, una por una, las cuatro esquinas de la cruceta, acompañadas de sus respectivas aristas, en los cuatro huecos disponibles. La imagen siguiente servirá para aclarar las dudas que os puedan haber surgido. El color gris hace referencia a un color cualquiera

Este paso se compone de 41 secuencias posibles. Según la posición de las piezas objetivo, tendremos dos situaciones diferentes: que la esquina y la arista se encuentren en la capa superior (lo más habitual) o que estén en capas distintas. Las secuencias a aplicar en el primer caso, esquina y arista en capa superior, son estas:

10

Cuando las piezas estén situadas en capas distintas, resolveremos aplicando alguna de las siguientes secuencias:

Es un paso sencillo y muy intuitivo, que se aprende en poco tiempo. La solución de la mayoría de casos que nos encontraremos en F2L, son fáciles de comprender, lo cual nos evitará tener que memorizar las secuencias.

Orientación última capa (OLL) El objetivo de este paso es girar las piezas necesarias de la capa superior, de forma que toda la capa acabe del mismo color, aunque algunas piezas estén mal colocadas. En mi caso (insisto de nuevo: yo empiezo resolviendo la cara azul), una vez aplicada la secuencia correcta, la cara superior acabará de color verde. Bajo estas líneas podéis ver la posición de inicio del cubo, tras haber aplicado las secuencias F2L, y el resultado final tras el paso OLL. El elevado número de casos posibles de inicio hacen de éste el paso más complicado de todo el método, ya que tendremos que memorizar un total de 57 secuencias diferentes, así como la posición de partida del cubo desde la cual aplicaremos cada una de ellas Como ya dijimos antes, estamos viendo la cara superior, en mi caso la verde. Las letras L, B, R y F corresponden a las caras izquierda, posterior, derecha y frontal respectivamente. Las líneas de verdes situadas junto al cubo indican la posición de la pegatina verde en aquellas piezas que no están orientadas correctamente, y que muestran un color diferente en la cara superior. Para aplicar la secuencia, debemos ver el cubo que tenemos en las manos como en las imágenes, con la cara verde arriba y la cruceta inicial abajo.

11

12

Hay dos posiciones que son de sobra conocidas por los speedcubers, hasta el punto de tener nombre propio: SUNE y ANTISUNE. Suelen aparecer con bastante frecuencia, por lo que deberían ser las primeras secuencias que intentéis memorizar. Para el resto de casos, con los que tarde o temprano nos tocará enfrentarnos Permutación última capa (PLL) Por último, una vez orientadas todas las piezas de la capa superior para que muestren el mismo color, tendremos que mover las que estén descolocadas. Este paso se compone de 21 secuencias distintas, la mayoría de ellas bastante largas (13 giros de media y varias secuencias con más de 15 movimientos). Bajo estas líneas, la situación del cubo antes de aplicar el paso PLL y el resultado final, que, en este caso, será el cubo resuelto. En las siguientes imágenes, de nuevo la figura de la izquierda representa la cara superior del cubo tras haber aplicado la secuencia OLL, lo que implica que todas las piezas que vemos en la cara superior deben mostrar el mismo color, en mi caso el verde. Las flechas

13

señalan la situación de las piezas mal colocadas que deberán cambiar de posición, normalmente permutando con otra pieza también mal colocada.

Veréis que las secuencias están agrupadas con paréntesis. No significa nada especial, simplemente que, con fórmulas tan largas, me resulta más sencillo memorizarlas así, en grupos de tres o cuatro movimientos. A propósito, David Calvo, que como campeón de España algo debe saber de esto, tiene una sección de consejos para afrontar el PLL que podéis consultar en busca de continuas mejoras. Los cuatro casos del punto "3.3.- 3 esquinas y 3 aristas" pueden asustar un poco con tanta flecha, así que vamos a detenernos un momento a analizarlo. Reconocer que estamos ante uno de estos casos es sencillo, ya que sólo tendremos dos piezas bien colocadas: una arista y una esquina, contiguas entre sí. Realmente, las cuatro posiciones son el mismo caso, pero invertido y simétrico. Para saber qué secuencia debemos aplicar, miraremos si la esquina contigua a las dos piezas bien colocadas va a la diagonal o a la esquina adyacente. Aristas y esquinas giran en sentido contrario entre sí.

(Santos Leal, 2009)

14

CONCLUSIONES

Las conclusiones que se sacan del presente trabajo de Investigación Formativa, sobre el cubo Rubik, son las siguientes: 

Si una persona trata de resolver el Cubo de Rubik lo más veloz posible, la mente se acostumbra a pensar y ver espacialmente con mayor facilidad.



El Cubo de Rubik tiene múltiples posibilidades: alteración del espacio por objetos, la transformación de objetos en el espacio, el movimiento en el espacio y en el tiempo, y la relación entre el hombre y la recreación.



Pone a prueba nuestra agilidad mental.



Ayuda mucho con la agilidad en las manos, de eso depende el tiempo que tardamos en hacerlo.



Es un reto para sí mismo, para intentar hacerlo cada vez en el menor tiempo posible.



Pone a prueba nuestra memoria.Es capaz de poner a prueba nuestra paciencia, antes de volver a empezar



Nos da gran habilidad Matematica, percibir la realidad, apreciando tamaños, direcciones y relaciones espaciales. Esto es de mucha utilidad en matemáticas.



Nos permite reproducir mentalmente objetos que se han observado y reconocer el mismo objeto en diferentes circunstancias.



Adquirimos una gran retención de información, ayuda a la memoria y la retención.

15

Bibliografía o Angosto Hernandez, C. (7 de Mayo de 2017). Solución sencilla del cubo de Rubik. Obtenido de El cubo rubik de la A a la Z : http://www.rubikaz.com/resolucion.php o

Santos Leal, J. (14 de Noviembre de 2009). Metodo Fridich para el cubo de Rubik 3x3. Obtenido de Coscorron de Razon: http://coscorronderazon.blogspot.pe/2009/11/metodo-fridrich-para-cubo-de-rubik-3x3.html

o

Wikipedia. (8 de Mayo de 2017). Cubo de Rubik. Obtenido de Wikipedia: https://es.wikipedia.org/wiki/Cubo_de_Rubik#Matem.C3.A1tica

16