IMC 2020 Q11
11. I start at square "1", and have to finish at square "7", moving at each step to a higher numbered adjacent square.
How many possible routes are there?
- A 7
- B 9
- C 10
- D 11
- E 13
Intermediate Mathematical Challenge 2020, Question 11. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: E 13
There is exactly one route from "1" to "2", but two routes from "1" to "3" - one route directly from "1" to "3" and one route which moves from "1" to "2" to "3".
To move from "1" to "4", it is necessary to move from "2" directly to "4" or to move from "3" to "4". So the number of routes from "1" to "4" is 1 + 2 = 3.
By a similar method, the number of routes from "1" to "5" is 2 + 3 = 5 and from "1" to "6" is 3 + 5 = 8. Finally, the number of routes from "1" to "7" is 5 + 8 = 13.
(Note that the numbers of routes to each of the squares is a term in the Fibonacci sequence.)
Solution © UK Mathematics Trust, from the IMC 2020 solutions. Longer versions with investigations: Solutions and investigations (PDF).