Le tre torri

[milizia96]

Borelix deve superare una delle XII fatiche imposte da Giulio Cesare, a tal scopo trasporta una pila di 7 pesanti dischi di pietra da una pedana nel tempio di Giulio Cesare ad una identica in quello di Cleopatra.
I dischi sono di 7 misure diverse, devono essere trasportati uno alla volta e possono essere posati solo sopra un disco più grande o su una pedana libera.
In partenza i dischi sono impilati in ordine dal più grande (posato sulla pedana) al più piccolo (in cima). Borelix ha l’impressione che non ci sia soluzione, ma per fortuna è a disposizione anche una terza pedana nel tempio di Pertouttatis.
Abelix dirige i lavori e assicura l’amico che spostando un disco al giorno, la fatica sarà completata in 127 viaggi.
Dopo un po’ la bella Alfablà passa a salutare i due galli e nota che ci sono 1 disco nel tempio di Giulio Cesare, 2 in quello di Cleopatra e 4 in quello di Pertouttatis. Inoltre Abelix osserva che questo non era mai successo prima.
Quanti viaggi deve ancora compiere Borelix?

(Gara a squadre - semifinale C 2011)

[xXStephXx]

Le famose torri di hanoi
La strategia per fare il minimo numero possibile di mosse è questa. Spostare i primi n-1 blocchi nella torre centrale, spostare il blocco più grande nella torre di destinazione, e spostare gli n-1 blocchi dalla torre centrale a quella di destinazione. In totale si fanno \(\displaystyle 2^n-1 \) mosse. E questo lo si calcola per ricorrenza partendo dal caso in cui si hanno 2 blocchi. (Ma ha anche una sua certa fama ). Se nella prima torre è rimasto un solo blocco, questo significa che tale blocco è il più grande e che in quel momento è in corso la costruzione della torre da 6 blocchi nella colonna centrale. Una volta dunque, lasciato un solo blocco nella prima torre, abbiamo il blocco di grandezza 6 nella torre centrale e nella colonna di Cleopatra abbiamo una torre formata dai blocchi di grandezza da 1 a 5. Per arrivare fin qui abbiamo speso 32 mosse. Infatti abbiamo risolto una torre di hanoi con 5 dischi ed in più abbiamo spostato il disco da 6. Il passo successivo è quello di costruire la torre formata dai blocchi di grandezza 1-4 nella torre di cesare, ma per far ciò si costruisce prima una torre con i blocchi di grandezza 1-3 nella torre di mezzo. (Ed è proprio quello il caso in cui i blocchi sono 1,4,2). Quindi per costruire la torre con 3 blocchi che vanno spostati dalla colonna di cleopatra a quella di mezzo servono 7 mosse, che si sommano alle 32 fatte prima. In tutto sono 39 mosse e ci troviamo in una situazione in cui abbiamo nella prima colonna il blocco di grandezza 7, nella seconda quello di grandezza 6 e quelli di grandezze 1-3, e nella colonna di cleopatra abbiamo i blocchi di grandezze 4 e 5. Mancano per terminare l'opera 127-39=88 mosse.

[milizia96]

Perfetto