0

I'm reading Knuths Concrete Mathematics and trying to solve my own questions as I read through the book. Right now, I want to solve a variant of the tower of Hanoi problem - solving for minimum number of moves T(n) to shift n disks from one tower to another given z towers.

This becomes a recurrence relation on two variables - so simply looking for T(n) with z=3wont help. I need a more powerful methodology with which to approach this problem.

I'm thinking you can represent towers as binary numbers of length n and then think about the situation as a finite state automaton. You move disks with bit shifts and there must be exactly nafter every operation.

Any ideas how to approach this multidimensional recurrence relation?

theideasmith
  • 1,090
  • It seems from the Wikipedia article that the optimal solution is an open problem -- are you talking about the recurrence relation for the "presumed-optimal" Frame-Stewart algorithm? Or if not, which recurrence relation do you mean? – joriki Apr 03 '16 at 20:02
  • If I'm not mistaken, the Wikipedia article reports that Frame-Stewart is proved optimal for four towers. – Oscar Lanzi Apr 03 '16 at 20:46
  • @OscarLanzi: Yes, but I understood $z$ to be arbitrary here. – joriki Apr 03 '16 at 21:02
  • Z is meant to be arbitrary. I didn't anticipate this happening – my asking an as of yet unanswered question in mathematics. I'll give myself a pat on the back for my effort and return to this problem in the future. – theideasmith Apr 03 '16 at 21:11

1 Answers1

0

See this paper for some insight into the question: https://www2.bc.edu/~grigsbyj/Rand_Final.pdf.

It seems from the Wikipedia article that the optimal solution is an open problem -- are you talking about the recurrence relation for the "presumed-optimal" Frame-Stewart algorithm? – joriki

theideasmith
  • 1,090