Le Torri di Hanoi (parte 1)

In questi due mesi di attività in LidiMatematici abbiamo messo al sicuro nella nostra borsa del matematico diversi strumenti che, al pari degli arnesi dello scultore che usa lo scalpello per realizzare le proprie opere, possiamo impiegare per risolvere problemi complessi e, nel farlo, comprendere meglio la realtà che ci circonda.

Mettiamo a frutto i mirabolanti strumenti della nostra borsa con un gioco: le Torri di Hanoi. Il gioco è estremamente semplice, abbiamo tre pioli e cinque dischi di diametro crescente. Il gioco inizia con i cinque dischi disposti in ordine crescente di diametro su uno dei tre pioli, obiettivo del gioco è disporre tutti i dischi su un altro piolo muovendo un solo disco per volta, ponendolo o su un piolo vuoto o su un disco di diametro maggiore.

Il gioco delle Torri di Hanoi è un rompicapo matematico inventato da un matematico francese, Edouard Lucas nel 1883. Lucas ha avuto la brillante idea non solo di ideare un affascinante rompicapo matematico, ma anche di inventare una storiella che ne facilitasse la diffusione. Sotto lo pseudonimo di N. Claus de Siam, mandarino del collegio di Li-Sou-Stian, Lucas raccontò al mondo di un fantomatico tempio Indù in cui un gruppo di monaci è interamente dedicato a risolvere il rompicapo delle Torri di Hanoi, spostando 64 dischi d’oro su 3 colonne di diamante.

Dietro all’apparente semplicità, il giochino delle Torri di Hanoi è un rompicapo che riserva sorprese piuttosto interessanti. Cerchiamo di capire il perché osservando l’immagine a cinque dischi e tre pioli:

numeriamo i dischi in ordine di diametro crescente e chiamiamo il disco di diametro più piccolo D1, quello di diametro immediatamente superiore D2 e così via D3, D4 e D5 per gli altri dischi.

Le regole prevedono che si possa spostare un solo disco alla volta, quindi la prima mossa è di muovere il disco più piccolo D1 che sta in cima alla piramide di dischi sul piolo 1. Spostiamolo sul piolo 2. Ora, con il disco D1 sul piolo 2, siamo forzati a porre il disco D2 sul piolo 3, perché le regole prevedono che non si può mettere un disco più grande sopra ad uno più piccolo. Non è quindi possibile mettere il disco D2 sopra al D1. Ma ora, con i pioli 2 e 3 occupati, prima di spostare il disco D3, dobbiamo forzatamente muovere il disco D1 sopra al disco D2 e liberare così un piolo.

Il vincolo di non poter collocare un disco più grande su uno più piccolo comporta quindi una serie di spostamenti addizionali in numero tutto fuorché trascurabile. Il segreto per risolvere l’enigma della Torre di Hanoi è nella ricorsione e per capire come usarla, occorre barare. Ricordate ? Ne abbiamo già parlato.

A proposito del mandarino Claus de Siam: per aggiungere un pizzico di brivido alla cosa, la leggenda vuole che il mondo avrà fine quando i monaci risolveranno il rompicapo. Terrificante ? Non più di tanto, continuate a seguirci, vedremo che c’è di che stare tranquilli …