MOG 2015 Q3
A ladybird is going for a wander around a \(10 \times 10\) board, subject to the following three rules (see the diagram).
She starts in the top left cell, labelled \(S\).
She only moves left, right or down, as indicated.
She never goes back to a cell that she has already visited.
In how many different ways can she reach the bottom row of cells, shaded grey?

Mathematical Olympiad for Girls 2015, Question 3. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: \(10^9\), that is, \(1\,000\,000\,000\)
Commentary
One possible approach would be to try to systematically list all possible paths around the board. From the starting square the ladybird can either move down or right. If she goes down she then again has a choice of down or right; if she goes right she can continue to the right or go down, but cannot go left along the same level (because she is not allowed to return to a cell she has already visited).
While this method is certainly systematic, there are too many options to list. So let’s stop and think what the rules really mean for the ladybird’s route around the board.
At any stage, the ladybird can move down a row. In order to reach the bottom, she will need to move down a row exactly nine times (remember that she can’t move up). Within a row, she can move down from any of the ten cells. Rule (iii) says that she never goes back to a cell that she has already visited. This means that when she arrives at a row, she must move to the left or right or stay still, and then go down. She can’t go left for a bit then right for a bit, for example, or she’d go back on herself.
This is a key observation. Imagine recording an accurate description of the ladybird’s route through the chessboard. In principle, it might be a long sequence of steps to the left, steps to the right, and steps down. But we have seen that the rules mean that it is simpler than this. She takes a total of 9 steps down, and in between each step she navigates directly to the cell from which she’ll make the next step down. So to record her route precisely, it’s enough to write a list of the nine cells from which she takes a step down — there is no ambiguity about her route in between those cells, she must just step down and then move directly to the next cell in the list. This gives us a much more manageable counting problem.
Once the ladybird (here called Ella) has reached the \(d\)th row she can move left or right, or not at all, to one of 10 cells in that row before her descent to the next row (unless she has already reached the last row).
Since Ella can’t go back on herself, there is only one way for her to reach any of the ten cells in \(d\)th row.
For each of rows \(1, 2, \dots, 9\), Ella has 10 options for the point at which she descends. Therefore there are \(10^9\), that is, \(1\,000\,000\,000\), ways for Ella to reach the bottom row of cells.
Note
Wherever Ella starts in the top row, the answer is the same.
Also, if the board is of shape \(m \times n\) (that is, \(m\) rows, \(n\) columns) then Ella can reach the bottom row from anywhere in the top row in \(n^{m-1}\) different ways.
Solution © UK Mathematics Trust, from the MOG 2015 solutions.