Col. Kurtz

Cannibale

User info:

Registered: May 2004
Posts: 849 (0.11 al dì)
Location: Cambogia
Corso: Informatica Magistrale
Anno: Ho finito
Time Online: 7 Days, 4:03:47 [...]
Status: Offline

Post actions:

Ci provo. (selezionare sotto)

La risposta è no.
Per giungere a MU, possiamo

a) Aggiungere una U dopo una I, tramite la regola 1, ottenendo ad esempio MIU. In questo caso, applicando la regola 2 (Mx -> Mxx), otteniamo MIUIU al quale è possibile operare soltanto la regola 2.
b) Raddoppiare I: non porta da nessuna parte. Per ritrovarci con MU, dovremmo avere un numero di I dispari e divisibile per 3, in modo da sostituire tutte le III con U tramite la regola 3, e far sparire le doppie U tramite la regola 4.

Ma, iterando la regola 2, non si avrà mai un numero di I divisibile per 3, in quanto all'ennesima iterazione avremo 2^n I.
Le potenze di due non sono divisibili per 3, si dimostra per induzione:

1) 2^1 non è divisile per 3, cioé 2^1 mod 3 != 0.

Supponiamo quindi che 2^n non sia divisibile per 3 (2^n mod 3 != 0), dimostriamo per 2^(n + 1):

2^(n+1) = 2^n * 2
quindi (2^n * 2) mod 3 != 0, poiché 2^n mod 3 != 0 e il minimo comun divisore fra 2 e 3 è 6, e 0, 1 o 2 (i possibili resti per 3) moltiplicati per 2 sono sempre minori di 6, e pari (quindi != 3).

Scusate la forma alquanto complessa, ma in teoria sarei a lavoro e ho del sonno arretrato. Ho vinto?

__________________
È odio, odio puro, una pietra morta, merda piena di mosche, sorrisi di plastica, vomitarsi dentro... nessuna paura per la paura di aver paura, soldi in tasca e fame in bocca, buonasera e odio negli occhi, non ce la faccio più

Get FreeBSD NOW!
Anch'io voglio estinguermi!

Last edited by Col. Kurtz on 05-03-2006 at 10:09