SMC 2006 Q13
13. The diagram shows five discs connected by five line segments.
Three colours are available to colour these discs.
In how many different ways is it possible to colour all five discs if discs which are connected by a line segment are to have different colours?
- A 6
- B 12
- C 30
- D 36
- E 48

Senior Mathematical Challenge 2006, Question 13. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: D 36
Disc \(A\) may have any one of three colours and, for each of these, disc \(B\) may have two colours. So these two discs may be coloured in six different ways.
If discs \(C\) and \(D\) have the same colour, then they may be coloured in two different ways and, for each of these, disc \(E\) may have two colours. So the discs may be coloured in 24 different ways if \(C\) and \(D\) are the same colour. However, if discs C and D are different colours, then \(C\) may have one of two colours, but the colours of discs \(D\) and \(E\) are then determined. So the discs may be coloured in 12 different ways if \(C\) and \(D\) are different colours. In total, therefore, the discs may be coloured in 36 different ways.

Solution © UK Mathematics Trust, from the SMC 2006 solutions.