JMC 2014 Q17
17. The diagram is a ‘map’ of Jo's local rail network, where the dots represent stations and the lines are routes. Jo wants to visit all the stations, travelling only by train, starting at any station and ending at any station, with no restrictions on which routes are taken.
What is the smallest number of stations that Jo must go to more than once?
- A 1
- B 2
- C 3
- D 4
- E 5

Junior Mathematical Challenge 2014, Question 17. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: C 3
Whichever route is chosen, it must include section \(BD\). We will divide the route into two sections. The first will include stations \(A\), \(B\), C and will finish at \(D\). The second will start at \(D\) and include stations \(E\), \(F\), and \(G\). Clearly the first section cannot be traversed without visiting at least one station more than once and the route \(A - B - C - B - D\) visits only B more than once so it is an optimal solution. Also, traversing the second section involves visiting D more than once as two branches lead from it. If \(D - E - D\) is part of the route then two stations are visited more than once. However, if \(D - G - D\) is part of the route then only \(F\) is visited more than once. So to traverse the second section, it is necessary to visit at least two stations (one of which is \(D\)) more than once. Therefore, the complete route must involve visiting at least 3 stations more than once. An example of an optimum route is \(A - B - C - B - D - F - G - F - D - E\). The stations visited twice are \(B\), \(D\), and \(F\).

Solution © UK Mathematics Trust, from the JMC 2014 solutions. Longer versions with investigations: Solutions and investigations (PDF).