La Stampa - Consultazione Archivio

Le tre torri di Hanoi da Fibonacci a Lucas | MATEMATICA | UN GIOCO DIVERTENTE E ISTRUTTIVO Le tre torri di Hanoi da Fibonacci a Lucas SI DEVE RICOSTRUIRE UNA COLONNA PARTENDO DA UN'ALTRA, SPOSTANDO DEI DISCHETTI UNO PER VOLTA E ORDINANDOLI PER GRANDEZZA, DAL MAGGIORE IN BASSO AL PIÙ' PICCOLO IN ALTO. MA CHE SUCCEDE SE LE COLONNE SONO 4? Federico Peiretti NARRA la leggenda che all'inizio dei tem¬ pi, Brahma portò nel grande tempio di Be- nares, sotto la cupola d'oro che si trova nel cèntro del mondo, tre colonnine dì diamante e sessantaquattro dischi d'oro, collocati su una di queste tre colonnine e ordinati dal più grande in basso al più piccolo in alto, in cima alla colonnina. E' la sacra Torre di Brahma che vede impegnati, giorno e notte, i sacerdoti del tempio nel trasferimento della torre di dischi dalla prima alla terza colonnina. Essi non devono contravvenire alle regole preci¬ se, imposte da Brahma stesso, che richiedono di spostare sol¬ tanto un disco alla volta e che non ci sia mai un disco sopra uno più piccolo. Quando i sacerdoti avranno completato il loro lavoro' e tutti i dischi saranno riordina¬ ti sulla terza colonnina, la torre e il tempio crolleranno e sarà la fine del mondo. Questa suggestiva leggenda indiana in realtà è un'invenzio¬ ne di Edouard Lucas, studioso di teoria dei numeri, che deve la propria fama all'analisi del¬ la «successione di Fibonacci» e alla sua divulgazione (vedi «TuttoScienze» del 29 febbraio 1984). Professore di matematica in un liceo parigino, Lucas è il più celebre esperto in giochi matematici dell'Ottocento, in¬ ventore di tanti rompicapo e giochi ancora oggi popolari. Morì nel 1891, a quarantanove anni, per un banalissimo inci¬ dente. La scheggia di un piat¬ to, rotto accidentalmente du¬ rante un banchetto, lo ferì al volto: se ne andò in pochi giorni per erisipela. La leggen¬ da della Torre di Brahma, che molti ritengono autentica, gli servì nel 1883, per lanciare nel modo più originale, la sua Torre di Hanoi, che si può trovare facilmente in tutti i negozi di giochi. In genere, il gioco in vendita è composto da tre colonnine e otto dischi, di dimensioni de¬ crescenti e infilati in una delle colonnine. Si tratta di spostare la torre dei dischi dalla colon¬ nina su cui si trova, a una delle altre due colonnine libere. Non è permesso prendere tut¬ ta la torre dei dischi e spostar¬ la sulla terza colonnina, si può spostarcelo ripetiamo, soltan¬ to un disco alla volta; inoltre un disco non può mai avere sopra di sé un disco più gran¬ de. Proprio queste regole im¬ pongono un numero ridotto di dischi, altrimenti il gioco di¬ venta lungo e complicato. Per una torre di 64 dischi, la Torre di Brahma, i movimenti neces¬ sari per lo spostamento sono più di 18 miliardi di miliardi. Se calcoliamo un movimen¬ to al secondo e se teniamo presente che in un secolo ci sono 100 x 365,24 x 24 x 60 x 60 secondi, cioè circa 3,2 x 109 secondi, per portare a termine t l'operazione i sacerdoti del' tempio di Benares impieghe¬ rebbero più di cinque mihardi di secoli e quindi, sul nostro futuro, da questo punto di vista, possiamo stare tranquil¬ li. L'analisi del gioco mette in evidenza un importante proce¬ dimento matematico di risolu¬ zione dei problemi, l'iterazio¬ ne, utilizzata ad esempio, per trovare le soluzioni approssi¬ mate di un'equazione. Il gioco è anche largamente diffuso fra gli studenti dei corsi di infor¬ matica, come esercizio di pro¬ grammazione. Indichiamo con A, B e C le tre colonnine. Nel caso banale di un unico disco, occorrerà un solo moviménto per risolvere il gioco, basta infatti spostare il disco dalla colonnina A alla colonnina C Con due dischi sono necessari 3 movimenti, si deve spostare il disco superiore sulla colonni¬ na B, il disco più grande su C ed infine l'altro disco sempre su C. Quali sono gli spostamen¬ ti minimi necessari che dobbia¬ mo fare per trasferire la torre a tre dischi da A a C? Con un po' di pratica si arriva facilmente a capire il procedimento da seguire con un nùmero qualsiasi di dischi, arrivando alla formula risoluti¬ va del gioco.. Se lo sappiamo risolvere con tre dischi, lo sapremo infatti risòlvere an¬ che con quattro dischi. Sarà ; sufficiente trasportare dappri¬ ma i tre dischi superiori sulla seconda: colonnina, con il pro¬ cedimento, già notOi successi¬ vamente il quarto disco sulla terza e infine si collocheranno su questo gli altri tre dischi, sempre con lo stesso procedi¬ mento. Risolto il caso dei quat¬ tro dischi, non ci saranno difficoltà aprocedere, allo stes¬ so modo, con cinque dischi e così vìa, sempre riispettando le regole del gioco. A. questo pun¬ to il lettore frastornato rischia di non capire più nulla. Al solito, è bene saperlo, per capire la matemàtica, anche soltanto di gipco, non si può soltanto "leggere",.ma è neces¬ sario "fare" matemàtica,: con esercizi e riflessioni personali; In questo caso, giocando con dischi e colonnine reali (o virtuali, al computer), tutto sarà sicuramente più chiaro. Si tratta, come dicevamo, di una soluzione iterativa che ci consente di scoprire la formu¬ la generale, per n dischi: 2 elevato a n, meno - 1, movi¬ menti. Per arrivare a questa formula si usa il metodo dell'in¬ duzione matematica, ma per un eventuale approfondimen¬ to dell'argomento, rimandia¬ mo il lettore interessato alle segnalazioni indicate a parte. Per la torre di sessantaquat¬ tro dischi, nota come Torre di Brahma, secondo la formula che abbiamo dato, avremmo quindi - esattamente - due elevato alla 64, meno 1, cioè 18.446.744.073.709.551.615 movimenti. Che cosa succede se introdu¬ ciamo nel gioco una quarta colonnina? Quanti sono, in questo caso, i movimenti ne¬ cessari per spostare un dato numero di dischi? E con più colonnine?