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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

28 Comentarios

  1. 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.

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. 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

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. Ei… me he dado cuenta de algo:

    Las posibles transformaciones son en los DOS sentidos.

    Publica una respuesta
  7. 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

    Publica una respuesta
  8. 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 🙂 ?

    Publica una respuesta
  9. 2) (MI)U => MIIU (Regla 2)

    Eso no se puede hacer. En este caso si quieres utilizar la regla 2 te quedaría MIUIU.

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. 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.

    Publica una respuesta
  12. ¿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.

    Publica una respuesta
  13. Fran, si te refieres al primero de los acertijos te aseguro que sí. Si te refieres al segundo…nadie ha dicho que la tenga.

    Publica una respuesta
  14. 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 ;).

    Publica una respuesta
  15. 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

    Publica una respuesta
  16. 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

    Publica una respuesta
  17. 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.

    Publica una respuesta
  18. Si mañana me acuerdo le aplico el algoritmo A*. Debería dar la solución más óptima.

    Publica una respuesta
  19. 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

    Publica una respuesta
  20. 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)

    Publica una respuesta
  21. 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)

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *