JK 2016 Q16
16. The diagram shows part of a river which has two islands in it. There are six bridges linking the islands and the two banks as shown. Leonhard goes for a walk every day in which he walks over each bridge exactly once. He always starts at point \(A\), goes first over bridge 1 and always finishes at point \(B\). What is the maximum number of days that he can walk without repeating the order in which he crosses the bridges?
- A 2
- B 4
- C 5
- D 6
- E More than 6

Junior Kangaroo 2016, Question 16. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: D 6
Since Leonhard's walk always goes over bridge 1 first, it must conclude by going over bridge 5 to enable him to reach to B. Note also that bridges 2 and 6 must be crossed consecutively, in some order, as they are the only way to get to and from the opposite bank to the one from which he started and is to finish and so can be considered together.

Hence the number of days he can walk without repeating the order in which he crosses the bridges is the same as the number of ways of choosing ordered crossings of bridges 3, 4 and the pair 2 and 6. These can be chosen in six different ways (three choices for the first bridge, two for the second and then only one choice for the third). Hence Leonhard can walk for six days without repeating the order in which he crosses the bridges.
(The six orders are 126345, 126435, 134265, 136245, 143265 and 146235.)
Solution © UK Mathematics Trust, from the JK 2016 solutions.