OliForum Matematico

Visto che tutti snobbano la combinatoria ..

La torre di Hanoi è un gioco costituito da tre paletti nel primo dei quali è infilata una torre di dischi ordinati secondo dimensione (in alto i più piccoli..)
Scopo del gioco e' di spostare la torre dalla prima colonna a sinistra all'ultima a destra, rispettando le seguenti regole:
a) si puo' spostare un solo disco alla volta, e solo il disco posto piu' in alto in una colonna
b) non si puo' mai appoggiare un disco piu' grande sopra ad un altro piu'
piccolo
Dimostrare che, se $ n $ e' il numero di dischi impilati sulla prima colonna, il numero minimo di mosse necessarie per completare il gioco e' $ 2^n-1 $
Buon divertimento.. Simone

Ho cancellato un paio di invii multipli e ritoccato il sorgente tex
FrancescoVeneziano
-------------------------------------------------------------

Innanzitutto se$ n=2k+1 $ il primo disco si deve inserire nella torre più a sinistra, mentre se $ n\equiv 0 (\mod2) $ lo si deve mettere nella torre centrale.
Si può dimostrare la tesi sottoforma di "passo induttivo", ovvero considerando la strategia come unica per qualsiasi $ n $ con la stessa parità.
Vabbè, per $ n=1 $ e per $ n=2 $ sappiamo come fare, e in effetti la tesi è rispettata.
Supponiamo di avere ottenuto $ n $ sulla terza colonna. Procedimento simile si ha per ottenere la torre sulla seconda colonna, quindi avremo il doppio delle mosse per riportarla dalla seconda alla terza, $ +1 $ per portare l' ultimo disco dalla prima all'ultima colonna, quindi $ 2(2^n-1)+1=\sum^n_{h=0} 2^k=2^{n+1}-1 $
spero di essere stato chiaro

HumanTorch ha scritto: Procedimento simile si ha per ottenere la torre sulla seconda colonna

potevi giustificarlo meglio:
ES: Chiamo 1 la configurazione in cui c’è un disco nella prima colonna e n dischi nella seconda. 2 è la configurazione vincente e 3 la configurazione iniziale.
Con $ n+1 $ dischi si può arrivare alla configurazione 1 in $ 2^n -1 $ mosse visto che il numero di colonna è arbitrario e la configurazione 1 ha lo stesso numero (hp induttiva) di mosse che avrebbe la configurazione 2 di $ n $ dischi (si tratta in tutti e due i casi di spostare una torre di $ n $ dischi)..
ma non sono certo io a potere fare queste sottigliezze (anzi le mie soluzioni generalmente sono molto più "vaghe" delle tue)..mi sembra vada tutto benissimo..anche io l'avevo risolto induttivamente
un'altra nota: mi sembra corretta la tua discussione pari-dispari su $ n $ma penso (non ne sono sicuro..) che, vista la richiesta, si possa liquidare con l'arbritrarietà del numero(o della posizione) di colonna..non ne sono sicuro però..
Buon pomeriggio Simone