Le torri di Hanoi e il principio di induzione

Il principio di induzione è un potente strumento di dimostrazione, al quale si ricorre ogni volta che si debba dimostrarela validità di una proprietà in un numero infinito di casi.

Potremmo scrivere così il suo enunciato:
Se una proprietà P_n vale per n=1 e se dalla validità di P_n si può dedurre quella di P_n+1, allora P_n vale per ogni intero n.

Un buon modo per introdurre il principio di induzione è il gioco delle Torri di Hanoi.

Ci chiediamo: è sempre possibile effettuare uno spostamento, qualunque sia il numero dei dischi?.
La risposta è sì. Ragioniamo in questo modo:
Supponiamo di saper spostare, in accordo con le regole del gioco, una configurazione di quattro dischi. Se ora dobbiamo spostare cinque dischi ci comporteremo così: (1) cominciamo a spostare i quattro dischi, infilati inizialmente sul piolo di sinistra, senza muovere mai il più grande alla base che non ci dà fastidio perchè essendo il più grande di tutti è come se non ci fosse, (2) A questo punto avremo i quattro dischi infilati in uno degli altri pioli, facciamo in quello di destra. Allora liberiamo il disco più grande e muoviamolo sul piolo centrale; (3) ora possiamo riportare eseguendo i passaggi di prima i quattro dischi sul piolo centrale.
Quello che abbiamo fatto per quattro dischi, l'abbiamo ripetuto per cinque dischi, dunque saremo in grado di ripeterlo anche per sei dischi. Procedendo per induzione possiamo rifarlo per un qualsiasi altro numero di dischi.

In definitiva possiamo dire che se è possibile spostare un certo numero di dischi, è anche possibile spostarne uno di più.

Ora dovremmo chiederci: siamo sicuri di coprire tutti i numeri? Se i dischi da spostare sono 47, sposteremo un disco, poi due, poi tre, ... dopo un po' di tempo si giungerà al disco quarantasette. Ma se dovessimo spostarne un numero un po’ più grande, diciamo 52698752145698523245874? Riusciamo a contare fino a raggiungerlo? E' il principio di induzione che ce lo conferma: contando un numero dopo l’altro raggiungiamo tutti i numeri senza eccezione. Di conseguenza, possiamo spostare quanti dischi vogliamo.

Bisogna avere un po' di tempo libero, perché per spostare n dischi da un piolo ad un altro occorrono 2ⁿ–1 mosse.

Anche questo si può dimostrare per induzione.
Infatti è vero per n=1 (per spostare un disco basta una mossa).
Supponiamo ora che per n dischi ci vogliano 2ⁿ–1 mosse. Quante ce ne vorranno per spostarne n+1?
Bisognerà spostare prima gli n dischi piccoli lasciando stare il più grande, e per questo occorrono 2ⁿ–1 mosse; poi si sposta il disco grande (1 mossa) e quindi ancora gli n piccoli (2ⁿ–1 mosse). In totale 2ⁿ–1+1+2ⁿ–1 mosse, cioè 2×2ⁿ–1=2ⁿ⁺¹–1 mosse.
In conclusione, se per spostare n dischi ci vogliono 2ⁿ–1 mosse, per n+1 dischi ne occorrono 2ⁿ⁺¹–1. Si può dunque applicare il principio di induzione, e concludere la dimostrazione.

Ad esempio, per spostare 64 dischi occorrono 2⁶⁴–1 mosse, cioè 18.446.744.073.709.551.615 mosse.
Eseguendo una mossa al secondo, ci vogliono 584.546.491.649 anni, 58 giorni, 14 ore, 56 minuti e 15 secondi.

... ma quanto è grande il numero 2 alla 64 ?