# Riddle of the day

Towers of Hanoi

Towers of Hanoi

Let us start with some geography. Hanoi is the capital of Vietnam. From the temperature table in the Wikipedia article, it appears that the weather is really nice throughout the year. Not for ski lovers definitely. The Towers of Hanoi is a cool puzzle. Despite the fact that it is usually being taught as the first non-trivial example of recursion, its elegance is not to be discarded or underestimated. In this post, let’s explore the Hanoi Towers.

Problem Statement: Consider the three pegs of the figure above. One of the three pegs has $n$ disks in the shape of a proper tower. The goal is to move the tower to one of the other pegs but with one constraint in our moves. We cannot move a larger tower onto a smaller one.

The first question to ask is whether there exists a solution! The answer as you already probably know is yes. Here is a short piece of code that answers this question in the affirmative way.
/**
* Lasting gems
* @author randomprojection
*/
public class Hanoi {

public static int moves=0;
public static void main(String args[])
{
HanoiRec(5,”A”,”B”,”C”);
System.out.println(“Total number of moves=”+moves);
}

public static void HanoiRec(int n, String from, String aux, String to)
{
if (n==1){
System.out.println(“Move disk from “+from+” to “+to);
moves = moves+1;
}
else
{
HanoiRec(n-1,from,aux,to);
System.out.println(“Move disk from “+from+” to “+to);
moves = moves+1;
HanoiRec(n-1,aux,from,to);
}

}

}

Now by running the code for different numbers of disks, we see that the number of moves is $2^n-1$. Clearly, this is not a coincidence. Let’s prove it.

Proposition: The optimal number of moves $T_n$ necessary to solve the Hanoi towers is $2^n-1$.

The riddle of the day for you is to prove the proposition above. Very simple admittedly but make sure you can prove it 😉