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

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.

 Ancestors (10)

There are no discussions about this article yet.

There are currently no matching articles.