Acertijo MIMU
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.
28 comentarios
Deja un comentario
Puedes utilizar código LaTeX para insertar fórmulas en los comentarios.Para ello sólo tienes que escribir $ latex código-latex$ (sin el espacio entre $ y la palabra latex).
Si tienes alguna duda sobre cómo insertar algún símbolo puede ayudarte la siguiente web:
Wikipedia: Usando TeX
Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.
fcasarra - 6 de Agosto de 2007 11:32
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 de multiplicarlo por 2.
-Un número que no es divisible por 3, sigue sin serlo después de restarle un múltiplo de 3.
-1 no es divisible por 3.
koldito - 6 de Agosto de 2007 12:00
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.
Jordi Bodera Sempere - 6 de Agosto de 2007 12:01
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 opción MI =>(1) = UU
y sobre UU tenemos que
UU=>(1) = Error ya que no tenemos MI
UU=>(2) = Error ya que no tenemos UI
UU=>(3) = Error ya que no tenemos IM
Vamos… que me he perdido algo o no se puede hacer.
Tordek - 6 de Agosto de 2007 12:11
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
Tordek - 6 de Agosto de 2007 12:13
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.
Tordek - 6 de Agosto de 2007 12:14
IM ni MU, digo…
Jordi Bodera Sempere - 6 de Agosto de 2007 12:15
Ei… me he dado cuenta de algo:
Las posibles transformaciones son en los DOS sentidos.
Koki - 6 de Agosto de 2007 12:55
Yo también lo he hecho en 25 pasos, a ver si lo mejoro
Koki - 6 de Agosto de 2007 13:15
Je, je, 23 pasos.
Laurah - 6 de Agosto de 2007 13:31
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
Kent Mentolado - 6 de Agosto de 2007 16:04
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 => MIIIU (Regla 2)
3) M(III)U => MUU (Regla 3)
4) (MU)U => MUUU (Regla 2)
5) M(UU)U => MU (Regla 4)
Si se supone que no se puede resolver… en que me he equivocado (bueno, nos, porque los tres primeros pasos los publicó antes Tordek
?
^DiAmOnD^ - 6 de Agosto de 2007 16:10
2) (MI)U => MIIU (Regla 2)
Eso no se puede hacer. En este caso si quieres utilizar la regla 2 te quedaría MIUIU.
Kent Mentolado - 6 de Agosto de 2007 16:18
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 ya indicó fcasarra.
^DiAmOnD^ - 6 de Agosto de 2007 16:27
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.
Fran - 6 de Agosto de 2007 17:38
¿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.
^DiAmOnD^ - 6 de Agosto de 2007 17:42
Fran, si te refieres al primero de los acertijos te aseguro que sí. Si te refieres al segundo…nadie ha dicho que la tenga.
Fran - 6 de Agosto de 2007 17:49
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 ;).
marceluda - 6 de Agosto de 2007 17:58
21 pasos
Si se puede.
marcos - 6 de Agosto de 2007 18:08
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
Julio - 6 de Agosto de 2007 18:13
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 las UU ya estaria resuelto no?? pero no se puede por que UU=MI
Fran - 6 de Agosto de 2007 18:27
Pues sí, la solución optima tiene 21 pasos.
^DiAmOnD^ - 6 de Agosto de 2007 19:30
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.
Javier - 7 de Agosto de 2007 0:08
Si mañana me acuerdo le aplico el algoritmo A*. Debería dar la solución más óptima.
Leander - 7 de Agosto de 2007 10:40
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
Leander - 7 de Agosto de 2007 10:51
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 (UI -> I)
21: MU (IM -> MU)
^DiAmOnD^ - 7 de Agosto de 2007 15:00
Muy bueno Leander. Ya no lo intento
andrea - 1 de Marzo de 2008 19:56
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)
probando - 15 de Abril de 2008 17:05
Mi>Mu
Mi= Mx x=i
Mii= Mx x=ii
Miii= Mx x=iii
Mu= iii=u