Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems / 2 / d / Solution

In terms of minimum plan length, allowing more stacks can only help:Every legal plan using at most $k$ stacks remains legal with $k+1$ available: simply ignore the new stack. The inequality need not be strict. For $n=1$, one move suffices for every $k\ge 2$.

With $k\ge n+1$, put each of the $n-1$ smaller coins on its own spare stack, move the largest coin to the destination, and then place the smaller coins on it in decreasing size order. This uses $2n-1$ moves. Every smaller coin must leave the initial stack before the largest coin's first move. It cannot move just once directly to the final stack and stay there, since that would block the largest coin's eventual arrival. Thus each smaller coin requires at least two moves, while the largest coin requires at least one. HenceCompared with the three-stack value $2^n-1$, the physical task can therefore become substantially easier.

The difficulty of finding an optimal plan is a different issue. Each legal state is determined by assigning every coin to one of the $k$ labelled stacks, whose size order is then forced. There are $k^n$ such assignments, so the state space and possible branching factor grow with $k$. An uninformed search algorithm can therefore face more alternatives even when the optimal plan becomes shorter. Likewise, a simple recursive strategy for three stacks need not immediately supply the best strategy with more stacks. The defensible answer is that the required number of moves never increases, while computational search effort need not decrease.