Tower of Hanoi Variant

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Tower of Hanoi Variant

Postby jestingrabbit » Tue Jul 24, 2018 12:21 am UTC

So, we're probably all pretty aware of the Tower of Hanoi problem.

To recap, you have three stacks, two are empty, and one has n plates on it, each plate has a number on it from 1 to n and the plates are in order, with 1 at the top. A move consists of taking the plate on top of one stack and putting it on the top of another stack, and is only legal if the receiving stack is empty or the plate on the top of the stack has a greater number on it than the moving plate. The question is then: How many moves are required to rearrange the plates, so that they are all resting on a stack different from the stack they start on?

Variant: If there are 4 stacks, how many moves does it take? if there are k stacks?

[I don't have an answer atm]
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Tower of Hanoi Variant

Postby jaap » Tue Jul 24, 2018 6:40 am UTC

There's a very detailed book "The Tower of Hanoi - Myths and Maths" from 2013 which has a whole chapter devoted to this.
The four-peg version is also called Reve's Puzzle, given that name by H.E. Dudeney who was the first to write about this generalization in his 1908 Canterbury Puzzles.
There is a general solution for k pegs which is now known to be optimal for k=4, but this was apparently only proven in 2014, after that Hanoi book was published. (EDIT: The second edition came out this year and has been updated with this result.)

You can think about transferring n discs from peg A to peg D recursively as follows:
1. First transfer m<n discs from A to C (using all 4 pegs).
2. Use the classic 3-peg Hanoi solution to transfer the remaining n-m discs from A to D using peg B (and ignoring peg C completely).
3. Transfer m discs from C to D (using all 4 pegs).

This generalises in an obvious way for larger number numbers of pegs k, defining a solution in terms of solutions with k-1 pegs.

You now only have to figure out which value of m to use for each number of discs n. Of course you choose whichever leads to the fewest moves. The optimal choice of m is not always unique. For the Reve's puzzle, k=4, we have:

n: m
0: 0
1: 0
2: 1, 0
3: 1
4: 2, 1
5: 3, 2
6: 3
7: 4, 3
8: 5, 4
9: 6, 5
10: 6
11: 7, 6

This is the Frame-Stewart algorithm. It turns out that the solution that this produces for k=4 can also be viewed in a different way as two nested levels of standard Hanoi. Take for example a 10-disc tower. Split it into four sections - disc 1, discs 2-3, discs 4-6, discs 7-10 - which can be considered "superdiscs". Apply the classic 3-peg Hanoi solution for n=4 to these four superdiscs, moving them from A to D using peg B. Each time you need to move a superdisc peg C will be empty, so you can move the individual discs that comprise the superdisc by using the standard Hanoi solution with peg C as the spare peg.

Here is the OEIS entry for Reve's puzzle solution lengths with this algorithm. It has several further references.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Tower of Hanoi Variant

Postby jestingrabbit » Fri Jul 27, 2018 10:55 am UTC

I thought it was pretty deep when I was working on it, but I had no idea I was suggesting an open problem. Thanks for the rundown jaap.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 7 guests