0
$\begingroup$

I seem to be struggling with the following type of path questions

Consider paths starting at $(0, 0)$ with allowable steps

(i) from $(x,y)$ to $(x+1,y+2)$,

(ii) from $(x,y)$ to $(x+2,y+1)$,

(iii)from $(x,y)$ to $(x+1,y)$

Determine the total number of allowable paths from $(0, 0)$ to $(8, 8)$, and the total number of allowable paths from $(0, 0)$ to $(10, 10)$.

I dont know how to go about this question.

could anyone recommend a trivial method to tackle problems of these types in an exam setting?

$\endgroup$
2
  • 1
    $\begingroup$ General answer for these type of problems would be to use recursion, as answered by Rob Pratt. However, in this "small" case it might be easier to do things "on hand", especially in exam setting. Suppose you do $A$ moves of type (i), $B$ of type (ii) and $C$ of type (iii). After putting constraints on $A, B, C$ you will see that there is only two possibilities in both of your question. Can you work out the rest by yourself? $\endgroup$
    – prosinac
    Apr 2, 2020 at 21:56
  • $\begingroup$ I don't understand @prosinac $\endgroup$
    – mq1998
    Apr 2, 2020 at 22:44

2 Answers 2

4
$\begingroup$

Draw a table and think backwards. Let $p(x,y)$ be the number of such paths from $(0,0)$ to $(x,y)$. By conditioning on the last step into $(x,y)$, we find that $$p(x,y)=p(x-1,y-2)+p(x-2,y-1)+p(x-1,y),$$ where $p(x,y)=0$ if $x<0$ or $y<0$. You know that $p(0,0)=1$, and you want to compute $p(8,8)$ and $p(10,10)$. The resulting table is \begin{matrix} x\backslash y &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 \\ \hline 0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 1 &1 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ 2 &1 &1 &2 &0 &1 &0 &0 &0 &0 &0 &0 \\ 3 &1 &2 &3 &2 &3 &0 &1 &0 &0 &0 &0 \\ 4 &1 &3 &5 &6 &6 &3 &4 &0 &1 &0 &0 \\ 5 &1 & &8 &12 &13 &12 &10 &4 &5 &0 &1 \\ 6 & & &12 & &27 &30 &26 &20 &15 &5 &6 \\ 7 & & & & &51 & &65 &60 &45 &30 &21 \\ 8 & & & & & & &146 & &\color{red}{130} &105 &71 \\ 9 & & & & & & & & &336 & &231 \\ 10 & & & & & & & & & & &\color{red}{672} \\ \end{matrix} In particular, $$p(8,8) = p(7,6)+p(6,7)+p(7,8) = 65+20+45=130.$$

$\endgroup$
2
  • $\begingroup$ How could you apply this with perhaps a path D: $(x,y)->(x,y-1)$ ? $\endgroup$
    – mq1998
    Apr 3, 2020 at 13:13
  • 1
    $\begingroup$ You can use the same approach. The new recurrence has an additional $+p(x,y+1)$ term, and you should explicitly include a boundary condition $p(x,y)=0$ for $y>2x$ to avoid infinite descent. $\endgroup$
    – RobPratt
    Apr 3, 2020 at 14:46
2
$\begingroup$

Suppose you do $A$ moves of type (i), $B$ of type (ii) and $C$ of type (iii). If you want to reach $(8, 8)$, then clearly $A + 2B + C = 8$ and $2A + B = 8$. This yields $B = 8-2A$ and $C = 3A - 8$. Since $A, B, C$ are nonnegative integers, you obtain solutions $(A, B, C) = (3, 2, 1)$ or $(4, 0, 4)$.

Now to calculate paths, for $(4, 0, 4)$ case, a path is described by string of four $A$s and four $C$s. For example, $AAACCACC$ is one such path. There is ${8 \choose 4} = 70$ such paths.

For the $(3, 2, 1)$ case there is ${6 \choose 3} \cdot 3 = 60$ such paths. Altogether there are $130$ such paths.

For reaching $(10, 10)$ same logic gives you $B = 10 - 2A$ and $C = 3A - 10$, so solutions are $(4, 2, 2)$ and $(5, 0, 5)$.

So, the number of paths is ${8 \choose 4} {4 \choose 2} + {10 \choose 5} = 70 \cdot 6 + 252 = 672$.

This is in agreement with Rob Pratts answer. Also, I would like to emphasise as I did in the comment that his answer is "better" in a sense that it illustrates how you can handle any problem of this type, since his answers scales reasonably to larger numbers. This answer can from the practical point of view only be used on such a small examples. But, if I was writing an exam, I'd take this approach (or at least I would try and then estimate would it be faster done this way or in the more general way)

$\endgroup$
4
  • $\begingroup$ +1 I like these kind of "restrict by case" approaches too. It is not that hard to scale for larger numbers as there is a pattern, though the calculation could be tedious. E.g It works nicely for This question. $\endgroup$
    – Calvin Lin
    Apr 3, 2020 at 0:08
  • 1
    $\begingroup$ If you prefer multinomial coefficients to binomial coefficients, the formulas are $\binom{6}{3,2,1}+\binom{8}{4,4}$ and $\binom{8}{4,2,2}+\binom{10}{5,5}$. $\endgroup$
    – RobPratt
    Apr 3, 2020 at 1:24
  • $\begingroup$ I understand everything but where has A+2B+C=8 and 2A+B=8 come from? I don't seen how 8 can be reached using these steps? @prosinac $\endgroup$
    – mq1998
    Apr 3, 2020 at 16:58
  • 1
    $\begingroup$ If you do $A$ moves of type (i) then you moved $A$ steps on the $x$-axis. If you do $B$ moves of type (ii) then you moved $2B$ steps on the $x$-axis. If you do $C$ moves of type (iii) then you moved $C$ steps on the $x$-axis. And you must move $8$ steps in total. So $A+2B+C=8$. Same logic for $y$-axis gives second equation $\endgroup$
    – prosinac
    Apr 3, 2020 at 21:26

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.