LatticeMethod BrainTeaser Intermediate

Problem - 4724

$\textbf{Number of Routes}$

The shortest route from point $A$ to $B$ takes $10$ steps. How many such routes are there that do not pass point $C$?


$\textbf{Answer}$

$110$.

$\textbf{Analysis}$

This problem can be solved using several different counting techniques (See the book $Counting$ in the Math All Star series). One of the most intuitive ways is to use the lattice method.

Just mark all the nodes as shown above. The value of each node is the number of ways to reach it from point $A$. There is only one way to reach the node above point $A$. Therefore, its value is $1$. Similarly, there is only one route to the point on the right of $A$. However, there are two routes from $A$ to the point marked with $2$. In short, the value of each node equals the sum of the number on its left and the number below it. This is because these two are the only two possible routes. (Otherwise, if a route comes from the one above or on the right, it will take more than $10$ steps to reach $B$). It follows that the value of the node $B$ is the answer.

report an error