COSC 326
Heads and Tails
Problem Description
This is a problem about rearranging certain items according to certain rules. In our
problem we will use coins or small disks.
Rules:
• you must always move two touching coins
• you must finish with all the coins touching in a horizontal line
• only horizontal moves are allowed
• you are not allowed to rotate the coins
N.B. any movement of coins is a move!
Task
1. Given three heads followed by three tails in a line, what is the minimum number
of moves to alternate the heads and tails?
2. Try the same task with three heads followed by two tails.
3. In a suitable notation, write down your solutions.
4. Write a program to find the number of moves to alternate n heads and n tails for
2 < n < 20. Print each step on a new line in an easily readable format.
5. Extend your program to handle n heads and n − 1 tails.
How well does your solution scale?
Relates to Objectives
1.2 1.3 2.1 2.2 2.3 2.4 2.5 2.7 2.9 2.10 3.3 3.4 4.1 4.2 4.7 4.8
(2 point, Pair)
