La mucca fa "MU"

[3m0o]

Iniziando con la parola "MI" trasformarla in "MU" in un numero finito di mosse, effettuando solo le seguenti quattro mosse.
1) Se hai una parola della forma "XI" allora puoi trasformala in "XIU" (ad esempio MI -> MIU)
2) Se hai una parola della forma "MX" allora puoi trasformarla in "MXX" (ad esempio MIU -> MIUIU)
3) Se hai una parola della forma "XIIIY" allora puoi trasformala in "XUY" (ad esempio MIUIII -> MIUU)
4) Se hai una parola della forma "XUUY" allora puoi trasformala in "XY" (ad esempio MIUUI -> MII)

Un consiglio: non pensateci per troppo tempo

[axpgn]

Riformula le mosse mettendo i "paletti" tra un pezzo e l'altro (almeno per me che non ho capito bene tutte le mosse )


Cordialmente, Alex

[Folpo13]

Qualcun altro qui sta leggendo Gödel, Escher, Bach di Hofstadter nevvero?

Ci provo...

Perché venga fuori MU deve verificarsi:
M seguito da un numero dispari di U (che si eliminano 2 a 2 lasciandone una alla fine)
M seguito da un multiplo dispari di 3 (quindi 3 e 9 vanno bene, 6 e 12 no) di I.

Si può facilmente constatare che le due possibilità sono equivalenti per la regola 3 (noto che non posso ottenere un numero dispari di U semplicemente raddoppiando e la U può essere aggiunta soltanto se il carattere finale della stringa è I).

Si può dimostrare che il numero di I non sarà mai un multiplo di 3.

Ora parto con 1 I. Ad ogni turno: il numero di I raddoppia oppure il numero di I diminuisce di 3. Noto che $a-3=3n$, $a,n\inNN$ se e solo se $a$ è multiplo di $3$. Ma il nostro numero di I non avrà mai $3$ tra i divisori, perché partendo da 1 posso solo raddoppiare (e non sarà mai divisibile per 3 in questo modo) e toglierne 3 (non sarà mai divisibile per 3, come appena dimostrato).

Quindi non ci sarà mai un multiplo di 3 I e quindi la formazione di MU è impossibile.

Non ho ancora finito il libro e non so la dimostrazione data da Hofstadter, quindi potrei aver fatto qualche errore

[3m0o]

"axpgn":Riformula le mosse mettendo i "paletti" tra un pezzo e l'altro (almeno per me che non ho capito bene tutte le mosse )


Cordialmente, Alex

Non ho capito cosa intendi per "paletti". Questo?

1) Se hai una parola della forma "X-I" allora puoi trasformala in "X-I-U" (ad esempio M-I -> M-I-U)
2) Se hai una parola della forma "M-X" allora puoi trasformarla in "M-X-X" (ad esempio M-I-U -> M-I-U-I-U)
3) Se hai una parola della forma "X-I-I-I-Y" allora puoi trasformala in "X-U-Y" (ad esempio M-I-U-I-I-I -> M-I-U-U)
4) Se hai una parola della forma "X-U-U-Y" allora puoi trasformala in "X-Y" (ad esempio M-I-U-U-I -> M-I-I)

Dove X e Y sono non importa quale combinazione di lettere.

[3m0o]

"Folpo13":

Qualcun altro qui sta leggendo Gödel, Escher, Bach di Hofstadter nevvero?

Mah... a dire il vero è un mio amico che me l'ha proposto, se lui lo stia leggendo o l'abbia letto non ne sono a conoscenza.

Per il resto invece

"Folpo13":
Perché venga fuori MU deve verificarsi:
M seguito da un numero dispari di U (che si eliminano 2 a 2 lasciandone una alla fine)
M seguito da un multiplo dispari di 3 (quindi 3 e 9 vanno bene, 6 e 12 no) di I.

Si può facilmente constatare che le due possibilità sono equivalenti per la regola 3

La seconda condizione non mi convince, io lascerei via multiplo dispari. Scrivere semplicemente multiplo di 3.

"Folpo13":
Si può dimostrare che il numero di I non sarà mai un multiplo di 3.

Ora parto con 1 I. Ad ogni turno: il numero di I raddoppia oppure il numero di I diminuisce di 3. Noto che $ a-3=3n $, $ a,n\inNN $ se e solo se $ a $ è multiplo di $ 3 $. Ma il nostro numero di I non avrà mai $ 3 $ tra i divisori, perché partendo da 1 posso solo raddoppiare (e non sarà mai divisibile per 3 in questo modo) e toglierne 3 (non sarà mai divisibile per 3, come appena dimostrato).

Quindi non ci sarà mai un multiplo di 3 I e quindi la formazione di MU è impossibile.

Questo invece è giusto, anche se specificherei che raddoppiare un numero che non è divisibile per 3 non lo rende divisbile per 3. Tu lo dici solo per 1, ma puoi ottenere qualunque numero di I che non sia divisibile per 3 quindi lo specificherei.

Non ho capito comunque perché mettere la condizione sulle U, siccome non la usi poi.

[axpgn]

Più o meno ma non ho capito lo stesso

Cioè qual è la convenzione usata?

Per esempio, nella prima mossa X rappresenta una lettera sola o può rappresentare più lettere? E in tal caso devono essere tutte uguali oppure no? Oppure rappresenta esattamente sè stessa?
Idem per le altre ...

Cordialmente, Alex

[3m0o]

"3m0o":Dove X e Y sono non importa quale combinazione di lettere.

Dove X e Y sono una qualunque combinazione di lettere in tutte e quattro le regole, possono essere anche la combinazione "vuota" cioè nessuna lettera. Queste lettere possono essere quindi in quantità: 0, 1, o di più, possono essere in qualunque ordine, tutte diverse, oppure tutte uguali.
1) Se la parola termina con una I puoi aggiungerci una U alla fine
2) Se una parola inizia con M puoi raddoppiare le altre sue lettere e aggiungerle alla fine
3) Se nella tua parola ci sono presenti di seguito tre I puoi toglierle e mettervici al loro posto una U
4) Se nella tua parola ci sono presenti due U di seguito puoi cancellarle.

[Bokonon]

Che bei ricordi...il gioco del MU è inserito da Douglas Hofstadter in "Goedel, Escher e Bach: un eterna ghirlanda brillante". Quanto ci ho giocato 30 anni fa...

[Folpo13]

"3m0o":
(Cose)

Io purtroppo o per fortuna ho questa tendenza ad esagerare con ipotesi anche superflue...

Comunque

Le I devono essere un multiplo di 3 dispari perché se fossero in numero pari si formerebbero un numero pari di U, che non va bene perché si cancellerebbero tutte.

Alla fine non cambia la dimostrazione... Ma come ho detto tendo a sovrabbondare con le ipotesi.

Per l'altra cosa effettivamente l'ho lasciato sottointeso ma ovviamente un $a=2b$, $a,b\inNN$ è divisibile per $3$ se e solo se $b$ è divisibile per $3$.

[3m0o]

Non è vero. Da M-III-III (che sono esattamente 6 I) puoi aggiungere alla fine una U usando la regola 1) e poi cancellare i due gruppetti di 3 I ottenendo M-U-U-U e poi cancelli due U rimanendo con M-U.

Edit:

Tecnicamente è vero che devi sempre passare da un multiplo dispari di I, ma solo perché tra 6 e 0 I devi arrivare a 3 I, però puoi benissimo fare il tuo ragionamento passando anche da un multiplo pari di I

Edit 2:

Per dimostrare la non esistenza della soluzione NON è necessario specificare la parità/disparità dei multipli di 3. Non puoi mai ottenere un multiplo di 3 punto indipendentemente dalla sua parità e questo è sufficiente poiché 0 è un multiplo di 3