Recursion is child's play

Every mathematician (and almost everyone, in fact) is familiar with the "Tower of Hanoi" problem. Not only is it a great way to occupy a patient child for a while, it provides a wonderful illustration of the twin concepts of recursion and induction in the description of the solution to the n-disk problem and the expression of the minimum number of steps in the optimal solution, respectively.

But what if the moves were restricted beyond the basic three commandments? (Thou shalt not place a disk atop any disk of smaller size, for it is hateful to do so; and Thou shalt not place thy hand on more than one disk at the one time, lest you succumb to greed and avarice; and Thou shalt not try to weasel thy way around that last commandment by lifting a disk that is not topmost on its peg, what kind of fool do you take me for?) If, in addition, there is a bound on the difference between the sizes of adjacent disks, what is the optimal solution (if there is one) and how many moves does it take? S. Bendetkis and I. Safro have written a paper dealing with precisely this generalization of the classic problem.

It's always a joy to see some good math on such familiar puzzles.