6.B.3. the grid path problem
THE GRID PATH PROBLEM - By Carly Rozins
Carly Rozins is a PhD candidate in applied mathematics at Queen's University. She has a BSc in Biology and Math from the University of Guelph and a MSc in Applied Mathematics from Queen's University. Her research is in mathematical biology, specifically mathematical epidemiology. She also has a keen interest in math education and teaches first year math courses at Queen’s University.
The following problem was presented at The Fields Institute as part of the Math Education Forum. It was presented as an example of a math problem that can teach computational thinking. This problem is suited to senior high school students and to first year university students and has been assigned to second year engineering students as part of their MATLAB course at Queen’s University.
Computational thinking is difficult to define. I think of it as the process one goes through while dissecting a problem. The act of breaking apart a complicated problem into smaller, more manageable pieces to gain a better understanding of the overall structure is what I view as computational thinking. Once the smaller pieces are well understood, the whole problem is better understood, an answer can be achieved and more complicated questions are now feasible.The Grid Path Problem is a good computational thinking question because it can be broken into smaller components (visually you will see this) and the smaller components give deeper intuition for how the solution works. Additionally it is a nice problem because the objective is easy to understand. In fact, path problems can be given to students in grade school. Not only does the Grid Path Problem have a low floor, but it also has a high ceiling. Additional constrains can be incorporated into the problem which make it a more complex problem, yet the computational thinking used to solve the original problem, makes the more complicated problems manageable (see Question 2 and practice problems 2).
Rules: You must start in the top left corner and you must end in the bottom right corner. You are only allowed to move down and to the right (no moving up or left).
Question 1: To the right is a 6x6 grid (6 rows and 6 columns). How many paths exist which extend from the top left square, to the bottom right square?
Below we have drawn three unique paths. I wonder how many more we can draw?
Let's take a moment to study these paths. Notice that all paths involve five right moves and five down moves. In fact, every successful path will involve exactly five moves down and five moves to the right. (Take a moment to think about that)
Method 1 (combinations):
With this one observation, and a little knowledge of combinations, we are now able to answer Question 1. The path must consist of 10 moves, five of which should be down and five of which should be right. In fact, the order of the moves does not matter as long as there are a total of 10 moves, five of which are right. By using combinations we can find the total number of ways we can “select” a right move from the collection of 10 moves (five right, five down).
10 Choose 5 = 252
There are 252 unique paths.
Note: we could have also used the down moves in place of the right moves.
Method 2: Let's start back at the beginning and approach this problem in a different way. From the top left corner, there are exactly two moves you can make. You can move either right or down. Therefore, there is only one unique path that will take you from the top left square to the square to its right. Likewise, there is only one path that extends from the square in the top left corner to the square directly below it. We denote this by placing a 1 in those squares (see Figure 3). Consider the square in the second row and second column. There are two unique paths that start in the top left square and end there. We denote this by placing a 2 in this square. (Draw them to see for yourself). Continue calculating the number of unique paths that lead to each square in the grid. Of course this will become more and more difficult the farther along you get. Fortunately, a pattern is emerging.
It appears that the numbers in the grid follow Pascal’s triangle.
This observation will allow us to fill the squares in the grid with ease. Take the 6 in the third row and third column. To get 6, we add 3+3, the number in the square above and the number in the square to the left.
Practice Problems 1:
1. Must the grid be square for us to find the total number of paths? Explain.
2. Explain why Method 2 works.
3. Fill in the missing squares in the grid below according to Method 2
4. Use Method 1 and Method 2 to find the total number of paths in the grids below.
Question 2: Consider the 6x6 grid (Figure 4) with a missing square (the shaded square). How many unique paths can be drawn that extend from the top left square to the bottom right square and avoid the missing square.
Solution: We can no longer use Method 1. Since any path that goes through the missing square is now illegal, there will be fewer than 252 unique paths. If we proceed using Method 2, the numbers in gird should be identical to the numbers in Question 1 until we reach the missing square (Figure 6). Consider the square in the fourth row and third column in Figure 6. What number should we write in this square?
Well, there are no paths that lead to the square directly above it and exactly four paths which lead to the square to the left of it 0+4=4. In other words, the four paths that end in the square to the left (the fourth row, second column) are extended by length one into the square in the fourth row and third column while no new paths are entering that square from above.
Continuing to fill in the squares using Method 2 we find that there are 132 unique paths that extend from the top left square to the bottom right square that avoid the missing square. Method 2 works well, but it becomes tedious if you do not have a computer aiding you. There is a much faster solution that involves both Method 1 and Method 2. First observe that:
Where do the numbers 252, 6 and 20 come from and what do they represent?
252 = 10Choose5: the total number of paths that can be drawn in on a 6x6 grid with no missing square.
6 = 4Choose2: the total number of paths that extend from the top left square to the missing square. All of these paths are “illegal” or lost.
20 = 6Choose3: the total number of paths that extend from the missing square to the square in the bottom right corner.
Therefore (6)(20)=120 is the total number of paths that will go through the missing square. We do not want to count these. Hence there are 252-120=132 unique paths.
Practice Problems 2:
1. Consider the 8x6 grid below. How many paths can you draw that start in the top left square, go through the missing square, and end in the bottom right square?
2. Find the total number of paths that avoid the missing square(s) in the grids below.