It had better. If you're allowed to put larger disks on smaller disks, you can solve towers of Hanoi in linear time. Call the rods A, B, and C: the goal is to move the stack from A to C. First flip the stack upside down, one disk at a time, from A to B. Then do that again, from B to C. The stack is now upright on C, after 2n moves.

(In contrast, the real problem requires O(2^n) moves.)

[1] https://www.youtube.com/watch?list=PLZHQObOWTQDMRtm8h9bG9P06...

It seems like without that rule, the game's solution is 2n-1 steps (dump n-1 disks from the left to the right, move disk n to the center, then un-invert those n-1 disks on top of disk n), rather than 2^n-1 moves.

In the case where you can place larger disks on top of smaller disks, the sub-problems don't have the same solutions, i.e. In order to move N disks from A to B you first move N-1 disks from A to C, then one disk from A to B, then the N-1 disks back from C to B. But in order to solve the N-1 disks, you don't need to ensure that the largest disk ends up on the bottom -- you just move them all straight to the target.

I guess the rule is implicitly tied up in the fact that the sub-problems are solved in the same way as the larger problem.