Non ricordo quando sentii parlare per la prima volta del gioco delle torri di Hanoi, il celeberrimo rompicapo inventato e commercializzato nel 1883 dal matematico Edouard Lucas, noto per le sue generalizzazioni dei numeri di Fibonacci, per il test di primalità oggi noto come Lucas-Lehmer e, appunto, per la sua passione per i rompicapi matematici, che sfociò nella pubblicazione dei quattro volumi delle Récréations mathematiques (due dei quali usciti, ahimè, postumi). Lucas dà una descrizione del gioco delle torri nel terzo volume delle Récréations, attribuendone la scoperta al fantomatico N. Claus de Siam, anagramma di Lucas d'Amiens (sua città d'origine). Ne possiedo alcune versioni, acquistate qua e là, che suscitano immancabilmente la curiosità degli studenti quando li invito a cimentarsi con il gioco. Curiosità che, ahimè, scema non appena cerco di matematizzarne le caratteristiche. Perché di matematica, con le torri di Hanoi, se ne può fare parecchia.
A un livello ancora elementare, può essere interessante ragionare sulla natura ricorsiva del gioco: in effetti la strategia ottimale per la sua risoluzione può essere riassunta dalla frase "per completare la torre a $n+1$ livelli sul terzo piolo, realizzo una torre a $n$ livelli sul secondo, sposto la base sul terzo e ci ricostruisco sopra la torre a $n$ livelli". Da qui si intuisce facilmente la formula $m(n)=2^n-1$ che permette di calcolare il numero minimo di mosse necessarie a completare gli $n$ livelli, facilmente dimostrabile per induzione. L'animazione seguente, un esperimento un po' maldestro di stop motion che risale al periodo pandemico, mostra cosa succede se $n=4$:
Un po' più stimolante è la relazione con i cosiddetti codici Gray, e in particolare con il cosiddetto reflected binary code, brevettato dal fisico dei Bell labs Frank Gray nel 1953. Si tratta di una codifica binaria dei numeri naturali, alternativa a quella "classica", non posizionale ma con un vantaggio tecnico interessante nella trasmissione dei dati: nel passaggio da $n$ a $n+1$ i codici si differenziano solo in una posizione. Eccola per i numeri da 0 a 63 (l'ho ottenuta, come tabella LaTeX, istruendo a dovere chatgpt):
La creazione dei codici si può descrivere in questo modo: partendo da $0...0$, si inverte (cioè si cambia da 0 a 1 oppure da 1 a 0) la prima posizione partendo da destra che non riproduce un codice già usato. Quindi, per quanto riguarda ad esempio i codici a due cifre, $00$ è seguito da $01$, poi da $11$ e $10$.
Il Gray code rappresenta la strategia risolutiva nel senso seguente: ad ogni posizione del codice, da sinistra a destra, è associato un livello della torre, dal più ampio al più stretto; ad ogni transizione, si sposta (ciclicamente: $1\to2\to3\to1$ oppure $1\to3\to2\to1$) sul primo piolo disponibile il disco corrispondente alla cifra che cambia, verso destra se $n$ (l'altezza della torre) è pari, verso sinistra se è dispari.
Illustriamo il caso $n=4$, corrispondente all'animazione (le cifre sono colorate più o meno in modo corrispondente ai livelli):
(spostiamo (verso destra, perché $n=4$ è pari) dapprima il verde (ultima posizione), poi il blu (penultima), poi di nuovo il verde (ultima), poi il rosso (seconda), e così via).
L'uso dei Gray codes permette di scoprire un'altra, affascinante, connessione tra le torri di Hanoi e la matematica (citando l'incipit del sesto capitolo della raccolta Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi, dell'inimitabile Martin Gardner, fonte primaria di ispirazione per questo post, to a mathematician few experiences are more exciting than the discovery that two seemingly unrelated mathematical structures are really closed linked): identificando un codice binario con le coordinate di un punto di $\mathbb R^n$, la successione dei codici descrive un percorso che tocca esattamente una volta ogni vertice di un $n$-cubo (un quadrato per $n=2$, un cubo per $n=3$, un tesseract per $n=4$ ecc.), senza percorrere più di una volta ogni spigolo. In altre parole, un cammino Hamiltoniano sul grafo definito dai vertici e dagli spigoli. I casi $n=2,3$ sono abbastanza immediati e banali, e per quanto riguarda l'ipercubo (che corrisponde al caso con quattro livelli) il disegno seguente (trovato online) permette di seguire il cammino da $0000$ a $1000$:
Ai Grey codes e alle loro applicazioni in campo ludico Gardner dedicò la rubrica Matematical games del numero di agosto 1972 di Scientific American (da qualche parte lo si trova in .pdf, ma non ricordo dove), soffermandosi però soprattutto su un altro popolare rompicapo. Forse un giorno (non appena avrò capito come funziona) ne parlerò anche qui.
