 Solution

ID: 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:

Step	Coin	Source	Destination
1	$c_{1}$	$s_{1}$	$s_{3}$
2	$c_{2}$	$s_{1}$	$s_{4}$
3	$c_{3}$	$s_{1}$	$s_{2}$
4	$c_{2}$	$s_{4}$	$s_{2}$
5	$c_{1}$	$s_{3}$	$s_{2}$

Every moved coin is exposed, and the last two moves put a smaller coin on a larger one. Thus

5 < 2^{3} - 1 = 7 moves .

Five 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.

 New to topics? Read the docs here!