CEMC Banner

Problem of the Week
Problem B and Solution
Pathways

Problem

  1. Armaan walks to the zoo every day. A map of the streets between Armaan’s house and the zoo is shown, where Armaan’s house is represented by \(A\), the zoo is represented by \(Z\), and the streets are represented by line segments.

    A 3 by 3 grid of squares formed by 4 horizontal gridlines intersecting with 4 vertical gridlines. The point A marks the top left corner of the grid. The point Z marks the bottom right corner of the grid.

    How many different routes can Armaan take from his house to the zoo if he always walks either east or south? Consider the top of the page to be north.

  2. On Tuesday there is some construction, so part of a street is closed, as shown.

    The middle third of the third vertical gridline is blocked by a pylon.

    Armaan cannot walk on the closed part. How many different routes can Armaan take from his house to the zoo on Tuesday?

  3. On Friday, an intersection is closed, as shown.

    The intersection of the third horizontal gridline and the third vertical gridline is blocked by a pylon.

    Armaan cannot walk through this intersection. How many different routes can Armaan take from his house to the zoo on Friday?

Solution

To count the number of routes, we could just draw as many routes as we can think of and see if we can find them all. This might work, but would take a long time, especially if the grid was larger. Here we show a more systematic way of solving the problem. First we will mark each intersection with a letter, as shown.

On the first horizontal gridline, the four intersections are labelled A, B, C, D, from left to right. On the second horizontal gridline, the intersections are labelled E, F, G, H. On the third, they are labelled I, J, K, L. On the fourth, they are labelled M, N, P, Z.

  1. From \(A\), there is only \(1\) route to each of \(B\), \(C\), or \(D\). Similarly there is only \(1\) route to each of \(E\), \(I\), and \(M\). We update our diagram by indicating the number of routes from \(A\) to each of these intersections.

    A number 1 is placed next to intersections B, C, D, E, I and M.

    To reach \(F\), Armaan would need to come from either \(B\) or \(E\). Since there is \(1\) route to \(B\) and \(1\) route to \(E\), it follows that there are \(1+1=2\) routes to \(F\). To reach \(G\), Armaan would need to come from either \(F\) or \(C\). Since there are \(2\) routes to \(F\) and \(1\) route to \(C\), it follows that there are \(2+1=3\) routes to \(G\). Continuing in this way, by adding the number of routes to the preceding intersections, we can determine that there are \(10\) routes to \(P\) and \(10\) routes to \(L\), so there are \(10+10=20\) different routes from Armaan’s house to the zoo.

    The numbers next to the intersections are A: no number, B: 1, C: 1, D: 1; then E: 1, F: 2, G: 3, H: 4; then I: 1, J: 3, K: 6, L: 10; then M: 1, N: 4, P: 10, Z: no number.

  2. The counting of possible routes follows the same pattern as in (a), except for \(K\) and all intersections south and east of it, as shown.

    The numbers next to the intersections are A: no number, B: 1, C: 1, D: 1; then E: 1, F: 2, G: 3, H: 4; then I: 1, J: 3, K and L: no number; then M: 1, N: 4, P and Z: no number.

    To reach \(K\), Armaan would need to come from \(J\), so there are \(3\) routes to \(K\). We can then continue counting as before, by adding the number of routes to the preceding intersections. Then we can determine that since there are \(7\) routes to \(P\) and \(7\) routes to \(L\), there are \(7+7=14\) different routes from Armaan’s house to the zoo on Tuesday.

    In addition to the previous numbers, K has the number 3 and both P and L have the number 7.

  3. The counting of possible routes follows the same pattern as in (a), except for \(K\) and all intersections south and east of it, as shown.

    The numbers next to the intersections are A: no number, B: 1, C: 1, D: 1; then E: 1, F: 2, G: 3, H: 4; then I: 1, J: 3, K and L: no number; then M: 1, N: 4, P and Z: no number.

    Armaan cannot reach \(K\) due to construction. To reach \(L\), Armaan would need to come from \(H\), so there are \(4\) routes to \(L\). Similarly, to reach \(P\), Armaan would need to come from \(N\), so there are \(4\) routes to \(P\).

    In addition to the previous numbers, L and P both have the number 4.

    Since there are \(4\) routes to \(P\) and \(4\) routes to \(L\), there are \(4+4=8\) different routes from Armaan’s house to the zoo on Friday.