IMC 2010 Q21
21. A square maze has 9 rooms with gaps in the walls between them. Once a person has travelled through a gap in the wall it then closes behind them. How many different ways can someone travel through the maze from X to Y?
- A 8
- B 10
- C 12
- D 14
- E 16
Intermediate Mathematical Challenge 2010, Question 21. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: E 16
The rooms are labelled A, B, C, D, E, F, G, X, Y as shown.
We look first at routes which visit no room more than once.
We need consider only routes which go from X to A, since each of these routes has a corresponding route which goes from X to C. For example, the route X A D E Y corresponds to the route X C D G Y.
Routes which start X A then go to B or to D. There are three routes which start X A B, namely X A B E Y, X A B E D G Y and X A B E D C F G Y. There are also three routes which start X A D, namely X A D E Y, X A D G Y and X A D C F G Y.
The condition that a gap in a wall closes once a person has travelled through it means that it is not possible to visit a room more than once unless that room has at least four gaps leading into and out of it and the only such room is D. There are two routes which start X A and visit D twice. These are X A D G F C D E Y and X A D C F G D E Y. So there are 8 routes which start X A and there are 8 corresponding routes which start X C so there are 16 routes in all.
Solution © UK Mathematics Trust, from the IMC 2010 solutions.