Algorithms (F2008)

The standard ToH problem has 3 pegs, and the resulting recurrence for the number of steps needed to transfer n blocks from peg 1 to peg 3 solves to .

Suppose we had FOUR pegs ? One strategy (which is conjectured to be optimal, but is not known to be so) is the following: Take the first n-k blocks and move them from 1 to 2 using all four pegs. Take the remaining k blocks and move them from 1 to 4 without using 2 (which is a three-peg problem). Take the n-k blocks on 2 and move them to 4, using all four pegs (we can do this because any of these blocks can sit on top of the blocks currently on 4, so it’s as if 4 was empty.

There are two questions that result from this algorithm.

• For some fixed k, can we write down the resulting recurrence and solve it ?
• What is the right value of k to pick to get the overall best solution ?

It’s probably best to solve the first question and obtain the solution as a function of n and k. You can then try to minimize this expression with respect to k. Enjoy

You can post questions in the comments: use a SPOILER alert if you’re going to post a solution though.