6
$\begingroup$

The problem is as follows:

The diagram from below shows a grid of $6\times 6$. How many different ways can you get from $A$ to $B$ without going through any of the highlighted points?

Sketch of the problem

The alternatives given are as follows:

$\begin{array}{ll} 1.&\textrm{265 ways}\\ 2.&\textrm{365 ways}\\ 3.&\textrm{395 ways}\\ 4.&\textrm{405 ways}\\ \end{array}$

Does it exist a way to simplify this problem?. How exactly can I find the method to solve this?. There isn't any indication of which sort of path should be taken. Hence there could be tons of ways and I'm stuck on it. Can someone help me here?.

It would help a lot to me to include some sort of diagram or drawing to justify a resonable method to solve this.

$\endgroup$
13
$\begingroup$

I'm assuming the paths must go right and down only.

You can count the paths by using the inclusion-exclusion principle. Without considering the points that must be avoided, there are $\binom{6+6}{6}$ paths. Now subtract the $\binom{4+1}{1}\binom{2+5}{5}$ paths that visit the first bad point, the $\binom{2+4}{4}\binom{4+2}{2}$ paths that visit the second bad point, and the $\binom{4+5}{5}\binom{2+1}{1}$ paths that visit the third bad point. Then add back in the paths that visit two bad points. No paths visit all three bad points.

\begin{align} &\binom{12}{6} -\left(\binom{5}{1}\binom{7}{5} +\binom{6}{4}\binom{6}{2}+\binom{9}{5}\binom{3}{1}\right) +\left(\binom{5}{1}\binom{4}{4}\binom{3}{1}+\binom{6}{4}\binom{3}{1}\binom{3}{1}\right)\\ &=924-(5\cdot 21+15\cdot 15+ 126\cdot 3)+(5\cdot 1\cdot 3+15\cdot 3\cdot 3)\\ &=924-(105+225+378)+(15+105)\\ &=924-708+120\\ &= {\color{red}{366}} \end{align}


Here's an alternative solution that uses a Pascal-type recursion. Let $p(i,j)$ be the number of good paths that start from $A=(0,0)$ and reach point $(i,j)$. We want to compute $p(6,6)$. By conditioning on the last step into $(i,j)$, we find that $p(i,j)$ satisfies the following recursion: $$ p(i,j)= \begin{cases} 0 &\text{if $(i,j)$ is a bad point}\\ 1 &\text{if $i=0$ or $j=0$}\\ p(i-1,j)+p(i,j-1) &\text{otherwise} \end{cases} $$ The resulting values of $p(i,j)$ are: \begin{matrix} i\backslash j &0 &1 &2 &3 &4 &5 &6 \\ 0 &1 &1 &1 &1 &1 &1 &1 \\ 1 &1 &2 &3 &4 &0 &1 &2 \\ 2 &1 &3 &6 &10 &10 &11 &13 \\ 3 &1 &4 &10 &20 &30 &41 &54 \\ 4 &1 &5 &0 &20 &50 &91 &145 \\ 5 &1 &6 &6 &26 &0 &91 &236 \\ 6 &1 &7 &13 &39 &39 &130 &{\color{red}{366}} \end{matrix} So $p(6,6)=366$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @RobPratt The answer is $365$ but I have no idea how to get there. $\endgroup$ – Chris Steinbeck Bell Mar 21 at 2:07
  • $\begingroup$ Besides the inclusion-exclusion argument, I also listed them explicitly and got 366. $\endgroup$ – RobPratt Mar 21 at 2:17
  • $\begingroup$ Let's suppose what if I don't want to resort to binomials. Does it exist a way to solve this by brute force or counting them using Pascal's logic?. $\endgroup$ – Chris Steinbeck Bell Mar 21 at 2:21
  • $\begingroup$ I have no idea how did the author got to $365$?. Could it be that is a typo or he's not accounting for something. $\endgroup$ – Chris Steinbeck Bell Mar 21 at 2:21
  • 1
    $\begingroup$ @ChrisSteinbeckBell: The Pascal logic for that goes this way: we are calculating the number of paths through the lower two dots. To get to the first dot you have to make $6$ moves, of which are $4$ are down and $2$ are right. You can do that in $6 \choose 4$ ways because you can choose any $4$ of the $6$ moves to be down and the others are right. Then to get to the next dot you have to move $3$ moves of which $1$ is down and to get to $B$ you again make $3$ moves of which $1$ is down. The choices are independent, so you multiply them. $\endgroup$ – Ross Millikan Mar 21 at 3:11
0
$\begingroup$

Denote the points to be avoided by $1$, $2$, $3$, in the order Left, Top, Bottom.

Number of paths through $1 = \binom{6}{2}\cdot \binom{6}{2}$

Number of paths through $2= \binom{5}{1}\cdot\binom{7}{2}$

Number of paths though $3= \binom{9}{4}\cdot \binom{3}{1}$

Number of paths through $1$ and $3= \binom{6}{2}\cdot \binom{3}{1}\cdot \binom{3}{1}$

Number of paths through $2$ and $3 = \binom{5}{1}\cdot \binom{3}{1}$

Number of paths through $1$ and $2 = 0$.

Now we have to substract from the number of paths from $A$ to $B = \binom{12}{6}$ the first three amounts and add the next three amounts, which gets $366$ ( we use the inclusion-exclusion).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Where did you used the inclusion-exclusion principle?. This part I'm not getting it. Is it where the part you mentioned subtracting A to B?. Why is it the number of paths through $1=\binom{6}{2} \cdot \binom{6}{2}$? Why is it that? $\endgroup$ – Chris Steinbeck Bell Mar 21 at 2:57
  • $\begingroup$ @Chris Steinbeck Bell: First, do you understand why the number of paths from $A$ to $B$ is $\binom{12}{6}$ ? There are 6 vertical steps and 6 horizontal steps. Out of $12$ steps, you have to choose which ones will be the horizontal ones, so $12$ choose $6$ ways. $\endgroup$ – orangeskid Mar 21 at 3:01
  • $\begingroup$ Probably this is the reason why I requested the inclusion of a drawing thus I could understand this better. I can see there are seven vertical lines and seven horizontal lines considering A and B. I don't know where do you get the 6 vertical steps and the 6 horizontal steps. why is it 6 ways from those 12?. I'm stuck there. $\endgroup$ – Chris Steinbeck Bell Mar 21 at 3:14
  • 1
    $\begingroup$ @Chris Steinbeck Bell: Check out this source: youtube.com/… also en.wikipedia.org/wiki/Lattice_path $\endgroup$ – orangeskid Mar 21 at 3:24
0
$\begingroup$

I believe you are meant to always move either to the right or down along the grid. Without that restriction there would be infinitely many paths.

To get from $A$, which is $(0,0)$, to $B$, which is $(6,6)$, you need to take six steps down and six steps to the right. (I'm ignoring the restriction to avoid the three marked points for now.) It is true that there are seven horizontal and seven vertical lines in the figure, as you mention in a comment, but the steps are the segments between vertices, not the vertices themselves, which is why only six steps down are needed instead of seven.

One possible path from $A$ to $B$ is $RRDDRDRRDDDR$. Another is $RDRDRDRDRDRD$. A third is $RRRRRRDDDDDD$. In fact, any "word" consisting of six $R$s and six $D$s corresponds to a path. So the problem is reduced to counting words with six $R$s and six $D$s. Such a word is completely specified by stating where the $R$s are (or alternatively stating where the $D$s are). Any set of six elements chosen from $1,2,3,4,5,6,7,8,9,10,11,12$ is a set of possible $R$ positions. For the first possible path mentioned above, the set of $R$ positions is $\{1,2,5,7,8,12\}$. For the second it is $\{1,3,5,7,9,11\}$, and for the third it is $\{1,2,3,4,5,6\}$. There are $\binom{12}{6}$ ways of forming such a set.

Now that we know how many paths there are from $A$ to $B$, we want to subtract paths that are invalid in that they do pass through one of the marked points. There are, for example, $\binom{5}{4}\binom{7}{2}$ paths that pass through the marked point in the second row. The first binomial coefficient is the number of ways to get from $A$ to the marked point; the second is the number of ways to get from the marked point to $B$.

You can compute the number of paths passing through each of the other two marked points by similar reasoning. You will see, however, that some paths have been subtracted twice, so you will need to add these back. That is, you need to use the principle of inclusion-exclusion. One set of paths that needs to be added back is the set of paths that pass through both $(2,4)$ and $(4,5)$. They were subtracted once because they pass through $(2,4)$, and they were subtracted a second time because the pass through $(4,5)$. The number that needs to be added back to compensate for the double subtraction is $\binom{6}{2}\binom{3}{2}\binom{3}{2}$, which is the number of ways of going from $(0,0)$ to $(2,4)$, then from $(2,4)$ to $(4,5)$, and then from $(4,5)$ to $(6,6)$.

Added: Rob Pratt has given a beautiful solution using a Pascal's-triangle-like recurrence. I think it worth pointing out that Pascal's triangle is a table of binomial coefficients, so the binomial coefficients are still there in the background when you use that method. A formula for the result of applying the recurrence can be obtained by combining a sequence of arrays, each of which is a shifted Pascal's triangle multiplied by one or more binomial coefficients.

If no points are required to be avoided, the relevant portion of Pascal's triangle is $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & 15 & 35 & 70 & 126 & 210\\ 1 & 6 & 21 & 56 & \color{red}{126} & 252 & 462\\ 1 & 7 & 28 & 84 & 210 & 462 & 924 \end{array} $$ where, if rows and columns are both labeled $0$ through $6$, the entry in row $i$, column $j$ is $\binom{i+j}{i}$. To eliminate paths that pass through the marked point in the second-to-last row, we need to subtract the array $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 126 & 126 & 126\\ 0 & 0 & 0 & 0 & 126 & 252 & 378 \end{array} $$ whose row $i$, column $j$ entry is $\binom{5+4}{5}\binom{i-5+j-4}{i-5}=126\binom{i-5+j-4}{i-5}$ for $i\ge5$, $j\ge4$. This leaves $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & \color{red}{15} & 35 & 70 & 126 & 210\\ 1 & 6 & 21 & 56 & 0 & 126 & 336\\ 1 & 7 & 28 & 84 & 84 & 210 & 546 \end{array} $$ Similarly, to eliminate paths that pass through the marked point in Row $4$, Column $2$, subtract the array $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 15 & 15 & 15 & 15 & 15\\ 0 & 0 & 15 & 30 & 45 & 60 & 75\\ 0 & 0 & 15 & 45 & 90 & 150 & 225 \end{array} $$ whose row $i$, column $j$ entry is $\binom{4+2}{4}\binom{i-4+j-2}{i-4}=15\binom{i-4+j-2}{i-4}$ for $i\ge4$, $j\ge2$. This leaves $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & 0 & 20 & 55 & 111 & 195\\ 1 & 6 & 6 & 26 & \color{red}{-45} & 66 & 261\\ 1 & 7 & 13 & 39 & -6 & 60 & 321 \end{array} $$ At this point, paths that pass through both the marked point in Row $5$ and the one in Row $4$ have been subtracted twice, which explains the negative entries. To add these back, add the array $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 45 & 45 & 45\\ 0 & 0 & 0 & 0 & 45 & 90 & 135 \end{array} $$ whose row $i$, column $j$ entry is $\binom{4+2}{4}\binom{1+2}{1}\binom{i-5+j-4}{i-5}=45\binom{i-5+j-4}{i-5}$ for $i\ge5$, $j\ge4$. This leaves $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & \color{red}{5} & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & 0 & 20 & 55 & 111 & 195\\ 1 & 6 & 6 & 26 & 0 & 111 & 306\\ 1 & 7 & 13 & 39 & 39 & 150 & 456 \end{array} $$ A similar subtraction followed by addition are needed to eliminate paths that pass through the marked point in Row $1$, Column $4$. Subtracting $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 5 & 5 & 5\\ 0 & 0 & 0 & 0 & 5 & 10 & 15\\ 0 & 0 & 0 & 0 & 5 & 15 & 30\\ 0 & 0 & 0 & 0 & 5 & 20 & 50\\ 0 & 0 & 0 & 0 & 5 & 25 & 75\\ 0 & 0 & 0 & 0 & 5 & 30 & 105 \end{array} $$ whose entries are $\binom{1+4}{1}\binom{i-1+j-4}{i-1}=5\binom{i-1+j-4}{i-1}$ for $i\ge1$, $j\ge4$, gives $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 0 & 1 & 2\\ 1 & 3 & 6 & 10 & 10 & 11 & 13\\ 1 & 4 & 10 & 20 & 30 & 41 & 54\\ 1 & 5 & 0 & 20 & 50 & 91 & 145\\ 1 & 6 & 6 & 26 & \color{red}{-5} & 86 & 231\\ 1 & 7 & 13 & 39 & 34 & 120 & 351 \end{array} $$ To eliminate double subtraction of paths the pass through both $(1,4)$ and $(5,4)$ add $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 5 & 5 & 5\\ 0 & 0 & 0 & 0 & 5 & 10 & 15 \end{array} $$ whose entries are $\binom{1+4}{1}\binom{4+0}{4}\binom{i-5+j-4}{i-5}=5\binom{i-5+j-4}{i-5}$ for $i\ge5$, $j\ge4$. This gives the array in Rob Pratt's answer.

Assembling all these arrays to get a non-recursive formula for the entries in the final array is equivalent to the binomial coefficient method with inclusion-exclusion.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not familiar with the use of combinatorics, but I do understand how to calculate $\binom{12}{6}$ but I don't know how you got it that binomial. Perhaps does it exist another way which doesn't require this?. I would see it better if there is some justification visually of how to account for those ways?. And I'm thinking that the allowed paths are what you say. But there isn't an indication of that. $\endgroup$ – Chris Steinbeck Bell Mar 21 at 1:50
  • $\begingroup$ I have to confess that when I apply the method of my answer I don't manage to match any of the given alternatives, although I do come very close to one of them. I may, of course have made an arithmetic error somewhere. $\endgroup$ – Will Orrick Mar 21 at 1:50
  • $\begingroup$ Gee this doesn't give me much confidence though. $\endgroup$ – Chris Steinbeck Bell Mar 21 at 1:51
  • $\begingroup$ Let $R$ indicate a right move and $D$ a down move. One possible path is $RRDDRDRRDDDR$. In fact, any "word" consisting of six $R$s and six $D$s corresponds to a path. So the problem is reduced to counting words with six $R$s and six $D$s. This is where $\binom{12}{6}$ comes from. (You have to chose the positions of the six $R$s from twelve possible positions.) The number of paths that pass through the marked point in Row 2 is found by splitting the path into two subpaths at that point. $\endgroup$ – Will Orrick Mar 21 at 1:53
  • $\begingroup$ Well, I'm confident of the method, and have checked the arithmetic a few times. Are you 100% sure there's no typo in the answer choices? $\endgroup$ – Will Orrick Mar 21 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.