# Tower of Hanoi, 4 pegs i'm not sure what they are asking

• mr_coffee
In summary, the book describes an algorithm for transferring a tower of disks from one pole to another, where the tower can have any height. The algorithm is based on moving disks across two poles, and is polynomial in the number of disks transferred.

#### mr_coffee

Hello everyone.

I'm trying to figure this out, The problem says:
Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disk an be transfeered one by one from one pole to any other pole, but at no time may a larger disk be placed on top of a smaller disk. Let $$S_n$$ be the minimum number of moves needed to transfer the entire tower of n disks from the left-most to the right most pole.

c. Show that $$s_k <= 2*s_{k-2} + 3$$for all integers k >= 3.

Okay so i drew it out and I figured out the process:
if i have 4 poles, A, B, C, and D but I found an image on the web that will describe it better:

Then this is the process:
http://img100.imageshack.us/img100/908/untitledwc0.jpg [Broken]

Move n-2 disk from pole A to pole B,
then move top disk to pole C
then move top disk to pole D
Then move disk from C to D

The book says for a and b:

$$s_{1}$$ = 1
$$s_{2}$$= 1 + 1 + 1 = 3
$$s_3 = s_1$$ + (1 + 1 + 1) + $$s_1$$ = 5
$$s_4$$ = $$s_2$$ + (1 + 1 + 1) + $$s_2$$ = 9

and if I keep going with this pattern i'll get:
$$s_5 = s_3 + (1 + 1 + 1) + s_3 = 13$$
...
...
...
So it looks like they are getting the following formula:
$$s_k = s_{k-2}$$ + (1 + 1 + 1) + $$s_{k-2}$$
$$s_k = 2*s_{k-2}$$+ 3

So what I don't understand is, it says SHOW $$s_k <= 2*s_{k-2}$$ but I just showed up there that $$s_k = 2*s_{k-2}$$

So is that all I had to do? Is list out some more terms and generalize a formula?

Thanks!

Last edited by a moderator:
I'm struggling to work out your question owing to your notation.. Please go through it again and make sure when you don't write s_k-2 when you really mean (s_k) -2 or s_{k-2}. And what does == mean? (Third line from bottom.)

sorry matt i fixed it, i hope latex didn't modify my orginal.
== i mean is equal too, i fixed it above as well.

The issue is simply this:

you've shown that it is possible to move across in 2s_{k-2}+3 moves. You have not justified that the plan you set out above is actually the optimal strategy - it is conceiveable that there is a better way of doing it (there isn't as it happens). Thus you have shown that there is an algorithm that takes 2s_{k-2} + 3 moves, hence the best one takes s_k<= 2s_{k-2} +3 moves.

Your solution can actually be improved. rather than building a tower of 8 in the second tower, you could build a tower of size 5 there. then put next 4 biggest rings in tower 3 and finally move the biggest ring to the target tower. This way it will take you only 49 steps. Thus the formula given in the question is correct. There really is shorter solutions. What you have found is the longest of possible solutions hence =<

some more information. when you make the tower with height 5, you use all 4 towers to help build it. but once you make it, you keep it as it is and build your next tower only using the remaining 3 towers (like in the case of standard puzzle).

http://iq-games.blogspot.com/2011/02/bringing-down-towers-of-hanoi-part1.html

I have included the solution for 4 tower case. Please have a look http://iq-games.blogspot.com/2011/04/towers-of-hanoi-part-8.html" [Broken].

Havn't seen this algorithm before anywhere, if any of you have seen it, please let me know.

Also in part 4,5 and 6 you will see the solution (in java) for the general case of 3 tower problem. (having all rings in the first tower at start is just a subset of this, general case is much more interesting and bit more challenging in recursion)

Cheers

Last edited by a moderator:

## 1. What is the Tower of Hanoi puzzle?

The Tower of Hanoi is a mathematical puzzle that consists of three pegs and a number of disks of different sizes, which can slide onto any peg. The objective of the puzzle is to move all the disks from the first peg to the third peg, while following these three rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.

## 2. How many moves are required to solve the Tower of Hanoi puzzle?

The minimum number of moves required to solve the Tower of Hanoi puzzle with n disks is 2^n - 1. So, for a puzzle with 4 disks, the minimum number of moves would be 2^4 - 1 = 15 moves.

## 3. Can the Tower of Hanoi puzzle be solved with more than 3 pegs?

Yes, the Tower of Hanoi puzzle can be solved with any number of pegs, as long as there are at least 3. The minimum number of moves required to solve the puzzle with 4 pegs and n disks is 2^n - 1.

## 4. Who invented the Tower of Hanoi puzzle?

The inventor of the Tower of Hanoi puzzle is unknown, but it is believed to have originated in India in the 19th century. It was later popularized by the French mathematician, Edouard Lucas, in the late 19th century.

## 5. What is the significance of the Tower of Hanoi puzzle?

The Tower of Hanoi puzzle is significant because it is a classic example of a mathematical problem that can be solved recursively. It also has applications in computer science, specifically in the design of efficient algorithms and data structures.

• Calculus and Beyond Homework Help
Replies
7
Views
851
• Mechanical Engineering
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
464
• Calculus and Beyond Homework Help
Replies
4
Views
904
• Topology and Analysis
Replies
2
Views
2K
• MATLAB, Maple, Mathematica, LaTeX
Replies
8
Views
1K
• Introductory Physics Homework Help
Replies
5
Views
1K
Replies
26
Views
3K
• Calculus and Beyond Homework Help
Replies
4
Views
2K
• Topology and Analysis
Replies
8
Views
1K