This Is Why Muscle Heads Need Math
At Walter's weight lifting gym there is a stack of 8 weight plates on a pole on the floor, along with 3 empty poles. Walter's physical training regimen involves moving the plates, one at a time, from one pole to another, making sure that a larger plate is never placed on top of a smaller plates.
Walter will end his workout once all of the plates have been moved off of the starting pole and are all on the same pole. Today, Walter is feeling lazy, so he wants to do this in as few moves as possible. What is the minimum number of moves that Walter must make in order to finish his workout?
Details and assumptions
If you are interested in stacking problems, you might want to look at This Robotic Arm Can Do Many Things, But Is Unable To Think For Itself
The answer is 33.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
really, the result of the Frame-Stewart algorithm, I should say .. //sigh
The Frame-Stewart algorithm is supposed to be optimal, right?
let f(n) be the minimum number of moves for n plates it is easy to find that f(1)=1 f(2)=3 f(3)=5 f(4)=9 now back to the problem the easiest way to solve it is to dived the problem into 2 parts
1- move n/2 plates using the 4 poles to a pole which is not the final pole
2- move the remaining plates using only 3 poles to the final pole which is the original towers of hanoi which can be found from f(n)=2^n -1
3- move n/2 plates from the 1st step using the 4 poles to the final pole
so f(8)={2 x f(4)using 4 poles + f(4)using 3 poles }= 2 x 9+(2^4 -1)=18+15=33
Certainly this gives a way to move the plates around, so it is an upper bound on the number of moves, but why can't there be anything better?
Log in to reply
Hey you came up with the question, can you give a solution? Can't find any proper solution ><.Thanks!
I made a generalization of this idea in this note
Once again, Jugaad comes for rescue:
MinTry[] is the array Simulate for 1,2,3 discs. (=1,3,5 respectively) Now simulate for 4 discs. (=9)
The idea: for transferring n discs, you should transfer n-k (light) discs using 4 poles, transfer k (heavy) discs using 3 poles, and transfer n-k (light) discs using 4 poles.
This can be done in 2*MinTry[n-k] + 2^k-1 moves =f(n,k)
Do this for all k, from 1 thru n-1.
Let MinTry[n]= minimum f(n,k)
Return MinTry[8]=33
I solved this be visualizing it, but when I had a look back at it, I decided to find a formula, which I have so far been unable to do. I do know that the minimum moves with 4 towers are as follows: (1 - 1) (2 - 3) (3 - 5) (4 - 9) (5 - 13) (6 - 19) (7 - 25) (8 - 33) and because of the pattern of increases, i'd guess that 9 is 41 and 10 is 51
I also know that the formula for 3 towers is f(x)= (2^x)-1. Anyone who finds a formula let me know.
@Thomas Hayton:
Well, for what it's worth, you can say this about the minimum number of moves:
ϕ ( m + n ) ≤ 2 ϕ ( m ) + 2 n − 1
for m , n positive integers.
Log in to reply
Okay, thanks. I doubt I would have got that any time soon
Log in to reply
:)
Unfortunately, I just noticed that one of your numbers is mistaken: ϕ ( 6 ) = 1 7 not 1 9 .
Log in to reply
@Peter Byers – Okay, thanks for pointing out the mistake. Would have been very hard for me to find a correct formula then.
As a matter of fact (if I'm not mistaken) it is possible to prove, with only a modest degree of difficulty, that ϕ ( 8 ) = 3 3 . If it were smaller, then one of two things would have to happen: either we could move a pile of seven weights onto two (other) poles in only 11 moves (which in turn would mean that ϕ ( 7 ) is 23, or smaller, rather than 25) or we could do so in 12 moves in such a way that one of the poles has only two weights and one of those is the smallest weight.
Of course, that still leaves many details to be worked out.
Log in to reply
P.S. On second thought, here's an improvement on that statement:
If ϕ ( n + 1 ) = ϕ ( n ) + 6 then ϕ ( n ) ≥ 2 ϕ ( n − 2 ) + 1 .
Log in to reply
It seems to be an open problem in general, although there is a fairly simple algorithm that is conjectured to give the minimal solution. Spoiler alert: http://oeis.org/A007664
Knowing that this was a variations of the Towers of Hanoi problem with 4 pegs, I read up on it on wikipedia. I decided to use the Frame-Stewart algorithm .
Where n is the number of disks and r is the number of pegs, we try to find k such that we minimize
2 T ( k , r ) + T ( n − k , r − 1 )
The smallest result is our answer.
So, I tried to pick a k that would minimize the total. I found that 4 disks with 4 pegs was 9 moves, 4 disks with 3 pegs was 15 moves. So, I had a good candidate with 9 × 2 + 1 5 = 3 3 .
2 T ( 4 , 4 ) + T ( 4 , 3 ) = 2 × 9 + 1 5 = 3 3
I found 5 disks with 4 pegs to be 13 moves and 3 disks with 3 pegs to be 7 moves. So, 1 3 × 2 + 7 = 3 3 also.
2 T ( 5 , 4 ) + T ( 3 , 3 ) = 2 × 1 3 + 7 = 3 3
I found 6 disks with 4 pegs to be 23 moves, so that would be too much for k to be 6.
2 T ( 6 , 4 ) + T ( 2 , 3 ) = 2 × 2 3 + 3 = 4 9
I tried k = 3 ; but, then moving 5 disks with 3 pegs takes 31 moves.
2 T ( 3 , 4 ) + T ( 5 , 3 ) = 2 × 7 + 3 1 = 4 5
So, k can be either 4 or 5 and the problem can be solved to 33 moves.
I was going to form some code that would check my work; but, I got impatient and decided to just put in 33 and see if I was right. I got lucky. So, I cheated and looked up the formula on wikipedia, brute-forced on paper, hoped that I was right .. not my proudest answer ...