I can't believe there is no mention of the Tower of Hanoi on this forum!!

I am pretty sure many of you guys are familiar of this game..

It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another peg, obeying the following rules:

1- Only one disk may be moved at a time.

2- Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.

3- No disk may be placed on top of a smaller disk.

Now the questions on this forum are:

1- Can this be solved for any number of disks? Even a hundred and only 3 pegs? How can you prove it?

2- How many moves are needed for (n) number of disks?

Advanced question for people already familiar with the 2 first questions:

3 - How many moves are needed if there are 4 pegs not 3??

Note: I don't have an answer for #3 yet...

Please don't post your answers without a spoiler, this may be fun for people who've just heard about this for the first time...

## Question

## roolstar

I can't believe there is no mention of the Tower of Hanoi on this forum!!

I am pretty sure many of you guys are familiar of this game..

It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another peg, obeying the following rules:

1- Only one disk may be moved at a time.

2- Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.

3- No disk may be placed on top of a smaller disk.

Now the questions on this forum are:

1- Can this be solved for any number of disks? Even a hundred and only 3 pegs? How can you prove it?

2- How many moves are needed for (n) number of disks?

Advanced question for people already familiar with the 2 first questions:3 - How many moves are needed if there are 4 pegs not 3??Note: I don't have an answer for #3 yet...

Please don't post your answers without a spoiler, this may be fun for people who've just heard about this for the first time...

## Link to comment

## Share on other sites

## 14 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.