SMC 2013 Q25

Challengeborough's underground train network consists of six lines, \(p\), \(q\), \(r\), \(s\), \(t\), \(u\), as shown. Wherever two lines meet there is a station which enables passengers to change lines. On each line, each train stops at every station.
Jessica wants to travel from station \(X\) to station \(Y\). She does not want to use any line more than once, nor return to station \(X\) after leaving it, nor leave station \(Y\) having reached it.
How many different routes, satisfying these conditions, can she choose?
- A 9
- B 36
- C 41
- D 81
- E 720
Senior Mathematical Challenge 2013, Question 25. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: D 81
Jessica must travel alternately on lines which are connected to station \(X\) (i.e. \(s\), \(t\) or \(u\)), and connected to station \(Y\) (i.e. \(p\), \(q\) or \(r\)). In order to depart from \(X\) and end her journey at \(Y\), she must travel along an even number of lines. This can be 2, 4 or 6 lines, making 1, 3 or 5 changes respectively.
Case A, 2 lines: Jessica leaves station \(X\) along one of the lines \(s\), \(t\) or \(u\), makes one change onto one of lines \(p\), \(q\) or \(r\) and reaches station \(Y\). Here there are \(3 \times 3\) possibilities.
Case B, 4 lines: Jessica leaves station \(X\) along one of the lines \(s\), \(t\) or \(u\) and makes her first change onto one of lines \(p\), \(q\) or \(r\). She then makes her second change onto either of the two lines \(s\), \(t\) or \(u\) on which she has not previously travelled and her third change onto either of the two lines \(p\), \(q\) or \(r\) on which she has not previously travelled and reaches station \(Y\). Here there are \(3 \times 3 \times 2 \times 2\) possibilities.
Case C, 6 lines: Her journey is as described in Case B but her fourth change is onto the last of the lines \(s\), \(t\) or \(u\) on which she has not previously travelled and her fifth change is onto the last of the lines \(p\), \(q\) or \(r\) on which she has not previously travelled. Here there are \(3 \times 3 \times 2 \times 2 \times 1 \times 1\) possibilities.
So in total Jessica can choose \(9 + 36 + 36 = 81\) different routes.
Solution © UK Mathematics Trust, from the SMC 2013 solutions. Longer versions with investigations: Solutions and investigations (PDF).