Solution to Problem 138



Congratulations to this week's winner

Sean Koors

Further solutions were submitted by Steve Prowse, Sudipta Das, Al Zimmermann, Burkart Venzke, John Stamper, Lou Cairoli.


A special commendation to Al Zimmermann for the many insights into this week's problem.

The fewest number of moves is 33.

Let's label the pegs 1 through 4 with the disks initially on disk 1 and denote by Fn the minimal number of moves required to transfer n disks with four pegs and by Tn the minimal number of moves with only three pegs.  It's a straightforward exercise in induction to show that Tn  = 2n - 1.

One possible strategy is the following.  First moving k of the disks to peg 2 using four pegs, then move the remaining n-k of the disks to peg 3 using only three pegs then the original stack of k pegs now on peg 2 onto the stack on peg 4 using all four pegs.   The number of moves is then

Fn = Fk + (2n-k - 1) + Fn-k .
You then find the minimum value of this for k between 1 and n - 1.  Using the following table of Fn allows you to determine the value of F8.
 
n Fn 
1 1
2 3
3 5
4 9
5 13
6 17
7 25
8 33

Al Zimmermann conjectures the following formula for Fn :

Fn = (n - s (s - 1)/2 - 1) 2s + 1, where s = ë (Ö(8n + 1)  - 1)/2 û,
and ë x û means the nearest integer less than or equal to x.

There are other possible strategies to the one suggested above, but an exhaustive computer search (again thanks to Al Zimmermann) shows the above strategy gives the minimum value for the values of n above.

You are visitor number 2291 to this page.