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 😉

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: