Twitter proof: the Tower of Hanoi


< 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!
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!

  - RGS

Popular posts from this blog

Tutorial on programming a memory card game

Image
Pt En Este post vai ser um tutorial, não muito detalhado, sobre como fazer um jogo de memória com Python e pygame. O jogo que vamos implementar é um jogo comum: viramos uma série de cartas para baixo e temos que as virar duas a duas, tentando encontrar os pares. Claro que quando viramos duas cartas que não são um par, temos de as voltar de novo para baixo. Quando estou a criar um jogo, gosto de o ir desenvolvendo por etapas funcionais: partir o processo em várias fases que representem pontos nos quais eu tenho algo que posso testar. Deste modo, não só o processo se torna muito mais interessante, como posso ir controlando o aspeto do que estou a produzir. Deixo de seguida uma lista das etapas que eu pensei para este projeto; cada ponto da lista descreve a funcionalidade que o jogo já suporta: Criar um ecrã onde mostro todas as cartas dispostas, face para baixo; Clicar em cima de uma carta faz com que ela se vire para cima; Clicar na segunda carta verifica se encontrei
Read more

Markov Decision Processes 01: the basics

Image
Pt En < change language In this post I will introduce Markov Decision Processes, a common tool used in Reinforcement Learning, a branch of Machine Learning. By the end of the post you will be able to make some sense of the figure above! I will couple the formal details, definitions and maths with an intuitive example that will accompany us throughout this post. In later posts we will make our example more complete and use other examples to explain other properties and characteristics of the MDPs. Let me introduce the context of the example: From a simplistic point of view, I only have two moods: " hungry " and " thirsty ". Thankfully, my parents taught me how to eat and how to drink, so that I can fulfill the needs I mentioned earlier. Of course that eating when I am hungry makes me happy, just as drinking when I am thirsty makes me happy! Not only that, but eating when I am hungry usually satisfies me, much like drinking when I am thirsty us
Read more

The hairy ball theorem and why there is no wind (somewhere) on Earth

Image
Pt En < change language What if I told you that right now there is a place on Earth where there is no wind blowing to the sides? None at all! How can I know that? All we need is what is usually called the Hairy Ball Theorem . In less rigorous contexts, one can phrase the Hairy Ball Theorem as such: Theorem (Hairy Ball I): if you have a hairy ball, regardless of the way you comb its hair there will always be a spot where the hair points right up. In this particular image, the hair is pointing up both on the top and on the bottom. More formally, the Hairy Ball Theorem can be formulated like so: Theorem (Hairy Ball II): every continuous vector field over $S^2$ has at least a point where the tangential component is $0$. From this theorem it is actually quite easy to establish our interesting fact! If we think of the wind at the Earth's surface as a continuous vector field, the Hairy Ball Theorem says that there must be a point where the wind isn'
Read more