Computer Science
Paths across a grid
On a 4 by 4 grid of squares, you walk along the lines from the bottom-left corner to the top-right corner, moving only right or up. How many different routes are there?
- Hint 1How many moves does every route take, and how many of them are to the right?
- Hint 2A route is fixed once you choose which moves are the right moves.
- Every route has 8 moves: 4 right and 4 up.
- A route is a choice of which 4 of the 8 moves go right.
- That is 8 choose 4 = 8!/(4! 4!) = 70.
- Check on a 1 by 1 grid: 2 choose 1 = 2 routes, which is right.
Where it lands: 70
The trap: Multiplying choices at each corner (2⁸): near the edges you only have one choice.
What a tutor might ask next: How many routes avoid the centre point of the grid?
Now do one out loud. In the interview you think aloud with a tutor. Try a Computer Science problem with hints, follow-ups and Mia's feedback on how you think.