MOG 2018 Q3
Sheila the snail leaves a trail behind her as she moves along gridlines in Grid 1. She may only move in one direction along a gridline, indicated by arrows. Let \(b\), \(c\), \(d\) be the number of different trails Sheila could make while moving from \(A\) to \(B\), \(C\), \(D\) respectively.
Explain why \(b = c + d\).(2 marks)

Ghastly the ghost lives in a haunted mansion with 27 rooms arranged in a \(3 \times 3 \times 3\) cube. He may pass unhindered between adjacent rooms, moving through the walls or ceilings. He wants to move from the room in the bottom left corner of the building to the room farthest away in the top right corner, passing through as few rooms as possible. Unfortunately, a trap has been placed in the room at the centre of the house and he must avoid it at all costs.
How many distinct paths through the house can he take?(8 marks)
Mathematical Olympiad for Girls 2018, Question 3. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (b) 54
Commentary
The key to both parts of this problem is to realise that, in order to get to \(B\), Sheila must get to either \(C\) or \(D\) first. From there, the only way she can go is to \(B\) (since she can only move in the direction of the arrows).
This means that any trail she can make while moving from \(A\) to \(B\) is either a trail from \(A\) to \(C\) or a trail from \(A\) to \(D\), with the final step to \(B\) added.
The same idea can be used in part (b), but now Ghastly moves between adjacent rooms instead of along grid lines. We can represent the mansion as three \(3 \times 3\) grids stacked on top of each other. Ghastly starts in the bottom front-left corner (marked \(S\) in the diagram) and wants to finish at the top back-right corner, marked \(F\).

The requirement of using the shortest possible route means that he only wants to move to the right, towards the back, or up (so never going back on himself).
Since the rooms are arranged in a cube, some rooms can be accessed from three adjacent rooms (from the left, front and below). For example, the final room can be accessed from the three rooms labelled \(A\), \(B\) and \(C\), so the total number of paths he can take is the sum of the number of paths leading to each of those three rooms.
Using this idea, it is now possible to fill in all 27 cells in the grid above, starting from the one marked \(S\), with numbers representing the number of paths which lead to that cell. The number in the cell labelled \(F\) will be the total number of distinct paths that Ghastly can take.
To get to \(B\), Sheila can either go to \(C\) and then move to the right, or go to \(D\) and then move up. Hence the number of trails she can make while moving from \(A\) to \(B\) equals the number of trails from \(A\) to \(C\) plus the number of trails from \(A\) to \(D\): \(b = c + d\), as required.
We can represent the rooms in the mansion by cells in three \(3 \times 3\) grids. Suppose that Ghastly wants to move from the room marked \(S\) to the room marked \(F\). In order to take the shortest possible path, he should only move to the right, towards the back, or up.
For each room, the number of ways he can get to that room equals the sum of the number of ways he can get to the rooms he could have visited immediately before it; those are the rooms to the left, in front, or below the current room (in some cases, not all three of those rooms exist).
We can therefore find the number of ways to get to each rooms by filling in the cells in the tables, starting from \(S\). There is only one way to get to the three rooms adjacent to \(S\) – that is, to come straight from \(S\). From there, we can fill in the tables as shown below. Note that Ghastly cannot go to the central room, so we place a 0 there.

From the table, the total number of ways to get to room \(F\) is \(18 + 18 + 18 = 54\).
Solution © UK Mathematics Trust, from the MOG 2018 solutions.