Hamilton 2017 Q2
2. A ladybird walks from \(A\) to \(B\) along the edges of the network shown. She never walks along the same edge twice. However, she may pass through the same point more than once, though she stops the first time she reaches \(B\).
How many different routes can she take?
Hamilton Olympiad 2017, Question 2. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: 27
Label the centre point \(X\), as shown in the diagram alongside.
Clearly any route that the ladybird takes from \(A\) to \(B\) passes through \(X\), and she stops the first time she reaches \(B\).
Therefore the number of different routes that the ladybird can take is equal to
The number of routes from \(A\) to \(X\) is equal to
(the number of ‘direct’ routes from \(A\) to \(X\)) + (the number from \(A\) to \(X\) that visit \(X\) twice),
which is \(3 + 3 \times 2\).
However, the number of routes from \(X\) to \(B\) is just 3, since the ladybird stops the first time she reaches \(B\), so that it is not possible for her to visit \(X\) again. Thus the total number of different routes that the ladybird can take is \(9 \times 3\), which equals 27.
Solution © UK Mathematics Trust, from the Hamilton Olympiad 2017 solutions.