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

Move the three coins as follows, with $c_1$ smallest:

Every moved coin is exposed, and the last two moves put a smaller coin on a larger one. ThusFive is also optimal here: before the first move of $c_3$, both smaller coins must leave $s_1$. Neither can make its only move directly to the final destination and remain there, because it would obstruct the eventual arrival of $c_3$. Each smaller coin therefore needs at least two moves. Those four small-coin moves and at least one move of $c_3$ give the matching lower bound.