+770 These kinds of grid problems are very intriguing :D
a) When we hear "no backtracking", it means Christine can only go down and to the right.
Let's say every time she goes down one step is represented by a D, and every time she goes to the right represented by R.
There will be 7 Ds, as that's the amount Christine will have to go down. There will be 5 Rs with the same reasoning.
Let's take the Ds and Rs into a string with an order to represent Christine's path. For example, if it was DRDRDRDRDRDD, that means Christine went down once, then right once, then down once, and so on until she went down once and down again.
Now it has turned into this: "How many ways are there to arrange 7 Ds and 5 Rs in a string?"
There are \(\dbinom{12}{7}\) ways to choose 7 parts of the string to be a D, and one way to organize the rest of the Rs. You could also do \(\dbinom{12}{5}\) ways to choose 5 parts for the Rs, but they are equivalent. They both are 792 ways :D
b) How many go through point D? Well, let's have 2 mini versions of the problem.
// Note, every time I write the dimensions of the grid, it will be the width x height :D
We can notice that there are 2 grids leading and going out of the point D: A 3x4 grid in the top left, and a 2x3 grid in the bottom right.
We just repeat the same thing over again!
For the first grid, there are 7 total parts of the string, and we choose 3 to be the rights (note you can also choose 4 to be the downs, but 3's a bit easier, don't you think?). That's \(\dbinom{7}{3} = 35\) paths.
For the second grid, there are 5 total parts of the string, and we choose 2 to be the rights (same note) to get \(\dbinom{5}{2} = 10\) paths.
The number of paths passing through D will be the product of the mini-grids' paths, which is \(35 \cdot 10 = \fbox{350}\) :D
c) So, the question is asking for the number of paths that do not go through D. If there are \(792\) total paths, and \(350\) go through D, then I ask you: How many don't go through D? I trust you can solve this on your own! :D
+770 These kinds of grid problems are very intriguing :D
a) When we hear "no backtracking", it means Christine can only go down and to the right.
Let's say every time she goes down one step is represented by a D, and every time she goes to the right represented by R.
There will be 7 Ds, as that's the amount Christine will have to go down. There will be 5 Rs with the same reasoning.
Let's take the Ds and Rs into a string with an order to represent Christine's path. For example, if it was DRDRDRDRDRDD, that means Christine went down once, then right once, then down once, and so on until she went down once and down again.
Now it has turned into this: "How many ways are there to arrange 7 Ds and 5 Rs in a string?"
There are \(\dbinom{12}{7}\) ways to choose 7 parts of the string to be a D, and one way to organize the rest of the Rs. You could also do \(\dbinom{12}{5}\) ways to choose 5 parts for the Rs, but they are equivalent. They both are 792 ways :D
b) How many go through point D? Well, let's have 2 mini versions of the problem.
// Note, every time I write the dimensions of the grid, it will be the width x height :D
We can notice that there are 2 grids leading and going out of the point D: A 3x4 grid in the top left, and a 2x3 grid in the bottom right.
We just repeat the same thing over again!
For the first grid, there are 7 total parts of the string, and we choose 3 to be the rights (note you can also choose 4 to be the downs, but 3's a bit easier, don't you think?). That's \(\dbinom{7}{3} = 35\) paths.
For the second grid, there are 5 total parts of the string, and we choose 2 to be the rights (same note) to get \(\dbinom{5}{2} = 10\) paths.
The number of paths passing through D will be the product of the mini-grids' paths, which is \(35 \cdot 10 = \fbox{350}\) :D
c) So, the question is asking for the number of paths that do not go through D. If there are \(792\) total paths, and \(350\) go through D, then I ask you: How many don't go through D? I trust you can solve this on your own! :D
+636 TYSM btw your answers are much better than mine, I'm just more active than you :D
