Torre di Hanoi
Ciao a tutti! Dopo un po' di pausa di assestamento, sono tornato!
Mi stavo cimentando in un problema molto carino: la Torre di Hanoi. Mi dicono che per risolvere una Torre di Hanoi di $n$ dischi e $3$ supporti sono necessarie $2^n-1$ mosse, ma non riesco a dimostrarlo e, da buon matematico, non prendo nulla per buono, che non sia dimostrato. Vorrei poi fare una generalizzazione a $n$ supporti, ma non so proprio dove partire... Questo tipo di problemi non li ho mai affrontati, e più che una soluzione al problema da me proposto, vorrei qualche consiglio generale (soprattutto consigli su testi e campi della Matematica inerenti) su questo tipo di problemi, atti a trovare "la via più breve per...".
Ogni vostro consiglio sarà oro per me!
Ciao!!!
Mi stavo cimentando in un problema molto carino: la Torre di Hanoi. Mi dicono che per risolvere una Torre di Hanoi di $n$ dischi e $3$ supporti sono necessarie $2^n-1$ mosse, ma non riesco a dimostrarlo e, da buon matematico, non prendo nulla per buono, che non sia dimostrato. Vorrei poi fare una generalizzazione a $n$ supporti, ma non so proprio dove partire... Questo tipo di problemi non li ho mai affrontati, e più che una soluzione al problema da me proposto, vorrei qualche consiglio generale (soprattutto consigli su testi e campi della Matematica inerenti) su questo tipo di problemi, atti a trovare "la via più breve per...".
Ogni vostro consiglio sarà oro per me!
Ciao!!!
Risposte
L'articolo su MathWorld della Wolfram Research riporta, oltre alla spiegazione, anche una buona bibliografia.
L'aspetto interessante del problema è nell'eleganza con cui si risolve con una formulazione ricorsiva (braccio operativo dell'induzione), facilmente implementabile (soprattutto con un linguaggio che supporti le liste, ma non è necessario).
Qui trovi un Maple worksheet animato per la risoluzione (ovviamente, se hai Maple).
L'aspetto interessante del problema è nell'eleganza con cui si risolve con una formulazione ricorsiva (braccio operativo dell'induzione), facilmente implementabile (soprattutto con un linguaggio che supporti le liste, ma non è necessario).
Qui trovi un Maple worksheet animato per la risoluzione (ovviamente, se hai Maple).
È abbastanza facile capirlo se ci pensi un po'...
Basta che invece di farlo sulla carta ci giochi seriamente (il mio massimo è con 11 dischi e ho fatto una sola mossa sbagliata). Dopo che capisci il meccanismo che ci sta dietro ti metti a scrivere il numero di mosse. Avevo cominciato a giocarci perché lo avevo sul cellulare (con 6 dischi ci mettevo qualche minuto, con 11 sul pc ci avrò messo un’ora).
Incominci con il caso di 1 disco (1 sola mossa).
Dopo di che per induzione ipotizzi che valga per $n-1$.
Dopo di che basta osservare che per spostare la colonna da 1 a 3 basta spostare la colonna meno l’ultimo anello in 2, spostare l'ultimo anello in 3 e spostare il resto in 3.
Quindi hai che mosse di $n = 2(2^(n-1) - 1) + 1 = 2^n - 2 +1 = 2^n -1$
Basta che invece di farlo sulla carta ci giochi seriamente (il mio massimo è con 11 dischi e ho fatto una sola mossa sbagliata). Dopo che capisci il meccanismo che ci sta dietro ti metti a scrivere il numero di mosse. Avevo cominciato a giocarci perché lo avevo sul cellulare (con 6 dischi ci mettevo qualche minuto, con 11 sul pc ci avrò messo un’ora).
Incominci con il caso di 1 disco (1 sola mossa).
Dopo di che per induzione ipotizzi che valga per $n-1$.
Dopo di che basta osservare che per spostare la colonna da 1 a 3 basta spostare la colonna meno l’ultimo anello in 2, spostare l'ultimo anello in 3 e spostare il resto in 3.
Quindi hai che mosse di $n = 2(2^(n-1) - 1) + 1 = 2^n - 2 +1 = 2^n -1$
Evidenzierei che il fatto che ci siano 3 supporti rende il metodo di risoluzione unico e inoltre è il caso che necessità più mosse. Infatti se il numero di supporti aumenta ci si può comportare come se un supporto non esistesse e usare l'algoritmo normale della torre di hanoi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo