< change language
In this post we prove what the minimum number of moves to solve the problem of the Tower of Hanoi is!
Claim: let $T(n)$ denote the number of moves it takes to solve the Tower of Hanoi with $n$ disks; then $T(n) = 2^{n}-1$.
Twitter proof: note that to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk. Each time we move the top $n-1$ disks to another pole we must take, at least, $T(n-1)$ moves (by definition of $T$) hence we clearly have $T(n) = 2T(n-1) + 1$. Just notice that $B(n) = 2^n - 1$ satisfies the recurrence relation and that $T(0) = B(0) = 0$.
If you are having trouble understanding what I mean by to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk, check the following sequence of images that contains some of the intermediate steps to solve the Tower of Hanoi with $4$ disks:
First we move the top $3$ disks to the centre pole in $T(3)$ moves...
Then we change the bottom disk to the available pole in $1$ move...
Then we move the top $3$ disks again in $T(3)$ moves!
Claim: let $T(n)$ denote the number of moves it takes to solve the Tower of Hanoi with $n$ disks; then $T(n) = 2^{n}-1$.
Twitter proof: note that to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk. Each time we move the top $n-1$ disks to another pole we must take, at least, $T(n-1)$ moves (by definition of $T$) hence we clearly have $T(n) = 2T(n-1) + 1$. Just notice that $B(n) = 2^n - 1$ satisfies the recurrence relation and that $T(0) = B(0) = 0$.
If you are having trouble understanding what I mean by to solve the problem with $n$ disks, we first have to move the top $n-1$ disks to one of the two poles, move the bottom disk (the bigger one) to the remaining pole, and then move the top $n-1$ disks to the top of the bigger disk, check the following sequence of images that contains some of the intermediate steps to solve the Tower of Hanoi with $4$ disks:
First we move the top $3$ disks to the centre pole in $T(3)$ moves...
Then we change the bottom disk to the available pole in $1$ move...
Then we move the top $3$ disks again in $T(3)$ moves!
Neste post vou provar qual é o número mÃnimo de movimentos necessário para resolver o problema da Torre de Hanoi!
Proposição: se $T(n)$ é o número mÃnimo de movimentos necessários para resolver o problema da Torre de Hanoi com $n$ discos, então $T(n) = 2^{n}-1$.
Prova num tweet: repare-se que para resolver o problema com $n$ discos, primeiro temos de mexer os $n-1$ discos mais pequenos para uma das duas varas livres, depois mexemos o maior disco para a outra vara vazia, depois voltamos a mexer os $n-1$ discos mais pequenos para cima do disco maior. De cada vez que mudamos os $n-1$ discos mais pequenos de vara, temos de fazer pelo menos $T(n-1)$ movimentos (pela definição de $T$) portanto temos claramente $T(n) = 2T(n-1) + 1$. Agora basta reparar que $B(n) = 2^n - 1$ satisfaz a relação de recurrência e que $T(0) = B(0) = 0$.
Se está a custar a entender o que quero dizer com para resolver o problema com $n$ discos, primeiro temos de mexer os $n-1$ discos mais pequenos para uma das duas varas livres, depois mexemos o maior disco para a outra vara vazia, depois voltamos a mexer os $n-1$ discos mais pequenos para cima do disco maior, vejam a sequência de imagens seguinte, que contém alguns passos intermédios para resolver a Torre de Hanoi com $4$ discos:
Primeiro mudamos os $3$ discos mais pequenos para a vara do meio em $T(3)$ movimentos...
Depois mudamos o disco maior para a vara livre em $1$ movimento...
Depois mudamos os $3$ discos mais pequenos da vara central para a vara mais à direita, em apenas $T(3)$ movimentos!
Proposição: se $T(n)$ é o número mÃnimo de movimentos necessários para resolver o problema da Torre de Hanoi com $n$ discos, então $T(n) = 2^{n}-1$.
Prova num tweet: repare-se que para resolver o problema com $n$ discos, primeiro temos de mexer os $n-1$ discos mais pequenos para uma das duas varas livres, depois mexemos o maior disco para a outra vara vazia, depois voltamos a mexer os $n-1$ discos mais pequenos para cima do disco maior. De cada vez que mudamos os $n-1$ discos mais pequenos de vara, temos de fazer pelo menos $T(n-1)$ movimentos (pela definição de $T$) portanto temos claramente $T(n) = 2T(n-1) + 1$. Agora basta reparar que $B(n) = 2^n - 1$ satisfaz a relação de recurrência e que $T(0) = B(0) = 0$.
Se está a custar a entender o que quero dizer com para resolver o problema com $n$ discos, primeiro temos de mexer os $n-1$ discos mais pequenos para uma das duas varas livres, depois mexemos o maior disco para a outra vara vazia, depois voltamos a mexer os $n-1$ discos mais pequenos para cima do disco maior, vejam a sequência de imagens seguinte, que contém alguns passos intermédios para resolver a Torre de Hanoi com $4$ discos:
Primeiro mudamos os $3$ discos mais pequenos para a vara do meio em $T(3)$ movimentos...
Depois mudamos o disco maior para a vara livre em $1$ movimento...
Depois mudamos os $3$ discos mais pequenos da vara central para a vara mais à direita, em apenas $T(3)$ movimentos!
- RGS
Twitter proof: the Tower of Hanoi
Reviewed by Unknown
on
October 02, 2018
Rating:
Reviewed by Unknown
on
October 02, 2018
Rating:
No comments: