Newsgroup: it.hobby.enigmi
Titolo: La Torre di Hanoi

Penso che tutti conoscano il rompicapo detto 'La Torre di Hanoi', in cui si hanno una base con tre pioli ed n dischi di raggio decrescente infilati su un piolo, a formare una piramide. Scopo del 
gioco e' di spostare la torre da un piolo ad un altro, secondo queste regole: 1) si puo' spostare un disco per volta; 2) un disco puo' poggiare o sulla base o su un disco di diametro superiore; 3) 
possiamo usare il terzo piolo come 'area di parcheggio'. 
Le domande sono:
a) con che logica si puo' risolvere il rompicapo per una piramide di n anelli, e come calcolare il numero minimo di mosse per risolverlo;
2) giocherellando con i pioli (senza infrangere le regole, ovviamente), avro' ad un certo punto una data configurazione (intesa come descrizione dei dischi su ogni piolo); e' possibile in questo 
modo riprodurre tutte le possibili disposizioni degli n dischi sui tre pioli, o ci sara' qualche posizione 'irraggiungibile?
Massimo 8-)
P.S. Se qualcuno sa anche dirmi da dove ho preso spunto per la seconda domanda, molti complimenti...

 modo riprodurre tutte le possibili disposizioni degli n dischi sui tre pioli, o ci sara' qualche posizione 'irraggiungibile?
10
9
8
7
6
5
4
3
2
1
Fu inventato da E. Lucas nel 1883.
Supponamo di voler spostare una pila di 6 dischi collocati sul piolo A,
per poter muovere il disco piu' grande dovro' prima trasferire il
pacchetto superiore di 5 dischi sul piolo B, muovere il disco di maggio
diametro sul piolo C, infine riversare il pacchetto su C. Si nota cosi'
che per spostare una pila di n dischi occorrono 2m+1 mosse dove m indica
il numero di movimenti necessari per spostare una pila di n-1 dischi.
procedendo per induzione:
dischi	mosse
1	1
2       2*1+1 = 3
3       2*3+1 = 7
4       2*7+1 = 15
.....
n       2^n-1.
Difatti c'e' una semplice strategia di soluzione. Supponiamo i tre pioli
A,B,C ai vertici di un triangolo, allora ad ogni mossa dispari spostiamo
il disco piu' piccolo in senso orario ABCABCABC... alternando ad ogni
mossa pari l'unica legalmente possibile, dopo 2^n-1 trasferimenti il
gioco sara' risolto.
Per la tua domanda b), mi sembra che ogni posizione legale sia
raggiungibile dal primo momento che posso "estrarre" dalla pila un
qualunque disco.
Quale fu l'ispirazione per questa ultima domanda?
non lo so, ma molti giochi combinatori dove ci sono pezzi mobili,
contengono piu' "universi".
Il gioco del 15 ne ha 2 (Sam Loyd inverti' il 14 col 15 infilandosi nel
2° universo facendo impazzire non poche persone). Il cubo di Rubik ne ha
12..ecc.
:)dario

Non male, non male (anzi, bene, bene 8-))
Io avevo trovato un metodo di soluzioni piu' 'praticone': una torre di un anello si risolve spostando l'unico anello dal piolo di partenza al piolo di arrivo; una torre di 2 anelli si risolve spostando il 
primo anello sul piolo di transito, il secondo sul piolo di arrivo ed infine spostando l'anello piu' piccolo dal piolo di transito al piolo di arrivo. In pratica, la conclusione e': ' Spostare una torre di n 
anelli significa spostare una torre di n-1 anelli dal piolo di partenza al piolo di transito, spostare l'ultimo anello sul piolo di arrivo e rispostare la torre di n-1 anelli dal piolo di transito al piolo di arrivo'.  
La funzione (ovviamente ricorsiva) che definiva il numero di mosse e': m(n)=2 m(n-1)+1, ponendo m(1)=1. E' una soluzione meno elegante della tua, ma che si adatta ad essere implementata in 
un programma ricorsivo (avevo studiato la Torre di Hanoi in un corso sul LISP)
Per quanto riguarda l'ispirazione della seconda domanda, e' il 'Teorema di Godel'. Pensavo che esistessero delle 'configurazioni' valide (rispondenti ai criteri iniziali) che pero' il sistema (colui che 
sposta gli anelli) non e' in grado di riprodurre. Un po' cpme il gioco del 15 di Lloyd (p.s. lo hai visto nel libro 'L'ultimo teorema di Fermat' di Singht?).
Comunque, ottima soluzione (non avevo pensato alla faccenda dei triangoli)
Massimo
P.P.S.
La formula generale 2^n-1 me l'ero fatta ricavare da un amico che studia matematica, dandogli in pasto la serie descritta sopra 8-)

 essere implementata in un programma ricorsivo [...]
Ti faccio notare che la tua soluzione e quella descritta da
Dario Uri _e`_la_stessa_ (solo descritta in modo diverso).
Ovevro, la scritura "per esteso" del tuo algoritmo ricorsivo
genera la stessa identica sequenza descritta da Dario in modo
non ricorsivo (infatti il numero di mosse e` eguale).
Ciao.
Mauro