CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot

CTK Exchange

Subject: "THE TOWERS OF HANOI-A DIFFERENT PER..."     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #57
Reading Topic #57
saumil07
Charter Member
2 posts
Feb-16-01, 09:24 AM (EST)
Click to EMail saumil07 Click to send private message to saumil07 Click to view user profileClick to add this user to your buddy list  
"THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
 
   You guys out there probably know about the towers of hanoi....let me give you a different perspective that has bogged me for the past few days.....
The regular problem has 3 needles, and you have to move n disks from source to destination using the auxiliary pin. You can move from source to auxiliary OR source to destination and vice versa.
This recursive solution takes 2^n moves in the worst case.

MY problem, however has restrictions imposed upon it. You can move from source to auxiliary, from auxiliary to source, from aux. to destination, and from destination back over to aux. and to source. THE move that is NOT ALLOWED is from source to destination straight. So everytime you go from source to destination, you have to move through auxiliary. This adds great complexity to the program.

Please let me know if anybody has a recursive solution to this.

Thanks
PATRICK


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
672 posts
Feb-16-01, 09:29 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #0
 
   >Please let me know if anybody
>has a recursive solution to
>this.

Before we start seeking a recursive solution, I suggest we find any solution for some simple case. Could you please find a solution for the two disks problem that satisfies your constraint. Let me know and we'd work out the rest.


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
saumil07
Charter Member
2 posts
Feb-17-01, 07:54 PM (EST)
Click to EMail saumil07 Click to send private message to saumil07 Click to view user profileClick to add this user to your buddy list  
2. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #1
 
   Hi, let me try to show you what the base case for 2 disks would be, with the specified constraints. There are 2 disks on Source (S), none on Aux. (A) and none on Destination (D) when the problem starts. You move the smallest disk (uppermost) to A and then over to D. Next, you move the biggest (2nd disk) to A, and then proceed by moving the smalles from D on back over to S. Move the biggest from A to D, and then move the smallest from S to A and then over to D, completing the problem for the simple case. It takes 7 moves to move 2 disks over, and 19 to move 3, and 38 to move 4. Does this make sense, or would you require more details?
Thanks
PATRICK


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
672 posts
Feb-17-01, 09:29 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
3. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #2
 
   Now I see. Candidly I missed the point.

Let me think of it. But just in passing. I checked with the
Encyclopedia of Integer Sequences (https://www.research.att.com/~njas/sequences/) for 2, 7, 19, 38 ... The sequence has not been recorded. So that if you are not mistaken as regard 19 and 38, you have a chance to register a new sequences under your name.

I'll be thinking of your problem.

Alexander Bogomolny


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
PATRICK (Guest)
guest
Feb-18-01, 03:45 PM (EST)
 
4. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #3
 
   Add another restriction to it. You cannot move from Aux. to Source either. So that adds another move when there are 3 discs. the sequence becomes 2, 7, 20, etc. Makes the problem even more complex.


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
672 posts
Feb-18-01, 05:09 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
5. "RE: THE TOWERS OF HANOI-A DIFFERENT PERSPECTIVE"
In response to message #4
 
   > Makes the problem even more complex

I am not sure about that. I think that they are about the same. You may get a more straightforward problem if, in addition, you also exclude direct moves from Dst to Aux.

With those three restrictions you may be able to obtain an upper bound for your probems.

The problem with three restrictions may be looked at this way. Place your pegs on a circle so that only clockwise moves are allowed. The pegs Src, Aux, Dst will be traversed clockwise. Let's forget for a moment about the designations source, auxiliary and destination, and think of just having N disks on one of the pegs. Let Tn be the number of moves needed to move the pegs 1 arc clockwise, and Sn be the number of moves needed to move n pegs 1 arc counterclockwise. Then

Tn = Sn-1 + 1 + Sn-1, and
Sn = Tn-1 + 2 + Tn-1.

In matrix notations, let vn = (Tn Sn)T and a = (1 2)T. Then

vn = A·vn-1 + a, where A is the matrix with rows (0 2) and (2 0).

We may take v0 = 0, so that v1 = a. Then, successively,

v2 = Aa + a,
v3 = A2a + Aa + a,
v4 = A3a + A2a + Aa + a, etc.

The solution is almost immediate if you separate the sequences of odd and even n's.


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to visit the old CTK Exchange archive.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
 Advertise

New Books
Second editions of J. Conway's classic On Numbers And Games and the inimitable Winning Ways for Your Mathematical Plays