Un juego para comenzar la semana: el acertijo MIMU. El juego consiste en lo siguientes:
Partiendo de MI llegar a MU utilizando simplemente las siguientes transformaciones:
1.- MI=UU
2.- UI=I
3.- IM=MU
El juego lo he visto en Cositos y es una variación del desquiciante acertijo MIU de Douglas Hofstadter que yo conocía desde hace tiempo y que consiste en lo siguiente:
Partiendo de MI obtener MU utilizando las siguientes reglas:
1.- Si una cadena (conjunto cualquiera de letras) termina en I podemos añadir U al final.
2.- Si tenemos una cadena de la forma Mx (siendo x cualquier conjunto de letras) podemos añadir otra x al final. Por ejemplo, si tenemos MIUI podemos obtener MIUIIUI.
3.- La cadena III puede sustituirse por U.
4.- Si nos aparece UU podemos eliminarlo.
Yo el primero lo he conseguido hacer en 25 pasos. Para jugar entrad en esta página. Lo único que tenéis que hacer es seleccionar la parte de la cadena de letras que queréis reemplazar y el cambio se hará solo. Si alguien resuelve el juego en menos de 25 pasos que lo comente por aquí. A ver si conseguimos entre todos la solución con el menor número de pasos posible.
Sobre el acertijo MIU…si alguien es capaz de conseguirlo que también lo comunique…aunque creo que eso es algo más complicado.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Tengo una posible demostración de que el juego del autor de GEB (Hofstander) no tiene solución. Supongo que me habré equivocado pero ahí va: -La ‘M’ es irrelevante. Nunca se quita ni se pone ni se modifica. -El número de ‘I’ solo lo podemos aumentar multiplicandolas por 2 (regla 2). No importa su distribución con las ‘U’. -El número de ‘I’ solo lo podemos disminuir por múltiplos de 3 (regla 3), por tanto, para eliminar todas las ‘I’ tenemos que conseguir que aparezcan un múltiplo de 3 ‘I’. -Un número que no es divisible por 3, sigue sin serlo después… Lee más »
fcasarra,
Tienes razón, el acertijo MIU no tiene solución. El mismo Hofstadter lo dijo en el libro, con un razonamiento muy parecido al tuyo.
Esto lo hice en LGA!!! Es posible que haya programas que generen el autómata dada la gramática? Una duda: >> Partiendo de MI llegar a MU utilizando simplemente las siguientes transformaciones: 1.- MI=UU 2.- UI=I 3.- IM=MU Si tenemos MI de inicio sólo podemos aplicar la primera regla, con la que obtenemos UU y desde ahí ya no podemos aplicar ninguna más, usease: MI =>(1) = UU (sobre MI aplicamos la primera transformación y obtenemos UU) MI => (2) = Error ya que no tenemos UI MI => (3) = Error ya que no tenemos MU Entonces sólo tenemos la… Lee más »
Depende, entonces, de si es legal, teniendo MIUI, reemplazar (MIU)I por (MIUIU)I, obteniendo MIUIUI, 3 I y 2 U.
En ese caso…
MI
1) MIU
2) (MI)U => MIIU
2) (MI)IU => MIIIU
3) M(III)U => MU
Había pensado lo mismo, Jordi, pero el signo de igualdad se aplica para ambos lados; es decir:
MI => (1) = UU
MI => (2) = MUI
MI => (3) (no se puede, dado que no hay MI ni UI.
IM ni MU, digo…
Ei… me he dado cuenta de algo:
Las posibles transformaciones son en los DOS sentidos.
Yo también lo he hecho en 25 pasos, a ver si lo mejoro
Je, je, 23 pasos.
x favor si arguien a exo er asertijo ese ke ponga la solusion da igual en los pasos ke sea!!!!!!! ¬¬ ke a mi esto me desesperaaa xD asiasss
Tordek, tienes un fallo en tu resolución: MI 1) MIU 2) (MI)U => MIIU 2) (MI)IU => MIIIU 3) M(III)U => MU Creo que las dos primeras transformaciones son legales (al menos, se permiten en los enunciados del problema, dado que define cadena como ‘conjunto cualquiera de letras’, obviando consideraciones como el tamaño o la posición). No es legal la última. No es que se puedan quitar III, sino que se sustituyen por U. Luego al final de tu último paso te quedaría MUU. 0) MI 1) (MI) => MIU (Regla 1) 2) (MI)U => MIIU (Regla 2) 2) (MI)IU… Lee más »
2) (MI)U => MIIU (Regla 2)
Eso no se puede hacer. En este caso si quieres utilizar la regla 2 te quedaría MIUIU.
Porqué no? Define cadena como un conjunto de letras (no especifica que tengan que ser TODAS las letras). Indica además explícitamente que puede ser cualquier conjunto, no la cadena completa. Según la regla dos, si tengo una cadena del tipo Mx puedo transformarla en Mxx, siendo x cualquier número de letras. Si unimos esas dos ideas, y en MIU tomamos como cadena MI, la transformación en MIIU es correcta, no? Obviamente el meollo de la cuestión es si tomar una subcadena como cadena a la que aplicar las normas es legal o no. Sin esa capacidad, no tiene solución como… Lee más »
Vale, es un problema de interpretación. La regla 2 sólo se puede usar con la expresión completa que tengamos en ese momento.
¿Seguro que ‘de MI a MU’ tiene solución? He aplicado un algoritmo de fuerza bruta que inspecciona todas las soluciones de profundidad hasta 26 y, creo, no tiene fallos. Y no encuentro la solución.
Fran, si te refieres al primero de los acertijos te aseguro que sí. Si te refieres al segundo…nadie ha dicho que la tenga.
Me refería al primero así que debe haber un error en mi programa. Puedes darme una pista ¿cuál es la cadena mas larga por la que pasa la solución? Ya sabes para descartar caminos ;).
21 pasos 🙂
Si se puede.
Felicitaciones a los que han logrado la solución óptima. Me han llegado varios mails.
En unos días pondré online más acertijos parecidos, algunos más fáciles, otros más difíciles.
Saludos
Marcos
1: MUI (I -> UI) 2: IMI (MU -> IM) 3: UIMI (I -> UI) 4: UUIMI (I -> UI) 5: MIIMI (UU -> MI) 6: MIMUI (IM -> MU) 7: MIMI (UI -> I) 8: MIUU (MI -> UU) 9: MUIUU (I -> UI) 10: MUUIUU (I -> UI) 11: MUUUIUU (I -> UI) 12: MUMIIUU (UU -> MI) 13: MUMIIMI (UU -> MI) 14: MUMIMUI (IM -> MU) 15: MUUUMUI (MI -> UU) 16: MUUUMI (UI -> I) 17: MUMIMI (UU -> MI) 18: MUUUMI (MI -> UU) 19: MUUUUU (MI -> UU) Bueno si se pudiese eliminar… Lee más »
Pues sí, la solución optima tiene 21 pasos.
Fran en mi solución de 25 pasos la cadena más larga que aparece tiene 6 letras.
A ver si soy capaz yo de hacerlo en 21.
Si mañana me acuerdo le aplico el algoritmo A*. Debería dar la solución más óptima.
Los 21 pasos son:
MI=
1: MUI
2: IMI
3: UIMI
4: UUIMI
5: MIIMI
6: MUIIMI
7: MUUIIMI
8: MMIIIMI
9: MMIIMUI
10: MMIIMI
11: MMIMUI
12: MMIMI
13: MMMUI
14: MMMI
15: MMUU
16: MIMU
17: UUMU
18: UUIM
19: UIM
20: IM
21: MU
Algunos pasos podrían resumirse, por ejemplo en el paso 7
7: M(UU)I(IM)I
Cambiamos a la vez ambos paréntesis de acuerdo a las igualdades correspondientes y nos queda
MMIIMUI
Siendo este el paso 9. Si esto fuese considerado un paso, entonces existe una solución en 17 pasos
Así está mejor 1: MUI (I -> UI) 2: IMI (MU -> IM) 3: UIMI (I -> UI) 4: UUIMI (I -> UI) 5: MIIMI (UU -> MI) 6: MUIIMI (I -> UI) 7: MUUIIMI (I -> UI) 8: MMIIIMI (UU -> MI) 9: MMIIMUI (IM -> MU) 10: MMIIMI (UI -> I) 11: MMIMUI (IM -> MU) 12: MMIMI (UI -> I) 13: MMMUI (IM -> MU) 14: MMMI (UI -> I) 15: MMUU (MI -> UU) 16: MIMU (MU -> IM) 17: UUMU (MI -> UU) 18: UUIM (MU -> IM) 19: UIM (UI -> I) 20: IM… Lee más »
Muy bueno Leander. Ya no lo intento 😛
hola quiero que me ayuden a resolver el acertijo de MU con las siguientes reglas:
despues de una M se puede insertar una U ejemplo mi (mui)
cuando este la palabra IMU se puede elimenar la M ejemplo imu (iu)
se empeiza siempre con mi
se puede triplicar la spalabras ejemplo mi (mimimi)
una U SE REMPLAZA POR 3 ies ejemplo mui (miii)
si hay 4 ies se gudas se eliminan ejemplo miiii(m)
Mi>Mu
Mi= Mx x=i
Mii= Mx x=ii
Miii= Mx x=iii
Mu= iii=u