Mack the bug starts at **(0 , 0)** at noon and each minute moves one unit right or one unit up. He is trying to get to the point **(5 , 7)**. However, at **(2 , 3) **there is a spider that will eat him if he goes through that point. In how many ways can Mack reach **(5 , 7)**?

Guest Jun 15, 2019

#1**+1 **

See the last couple answers here: https://web2.0calc.com/questions/help_26367

hectictar Jun 15, 2019

#2**-5 **

Dude, do you know how to solve these? I think you would cz this is an AoPS HW problem.... And I think you would be better if you read the transcript.

NoobGuest Jun 15, 2019

#3**0 **

We can solve this problem using dynamic programming, a technique taught in computer science, probably in discrete math also.

We can construct a 2-dimensional array called dp. each entry of the array is called dp_{i,j}, where (i,j) is the coordinates of the bug, and dp_{i,j} is the number of ways that the bug can reach (i,j).

First, an important observation is that \(dp_{i,j} = dp_{i-1,j} + dp_{i,j-1}\), for \((i,j) \neq (2,3)\).

This is the **state transition formula** of the dynamic programming.

And, there is only one way to go to (0, n) or (n, 0) for any n, which means \(dp_{0,n} = dp_{n,0} = 1\).

This is the **base case** of the dynamic programming.

Also, dp_{2,3} = 0, as any attempt to go to (2,3) will fail due to the existence of the spider... :(

Now we can construct the array by hand... :)

First, list the base cases.

(Each entry of the matrix aligns with a lattice grid. Numbers are in relative position of the coordinates, which means bottom left corner is dp_{0,0} and top right corner is dp_{5,7}.)

\(dp = \begin{pmatrix} 1&?&?&?&?&?\\ 1&?&?&?&?&?\\ 1&?&?&?&?&?\\ 1&?&?&?&?&?\\ 1&?&0&?&?&?\\ 1&?&?&?&?&?\\ 1&?&?&?&?&?\\ 1&1&1&1&1&1\\ \end{pmatrix}\)

Then use the transition formula to work out the remaining numbers:

\(dp = \begin{pmatrix} 1&8&26&70&180&342\\ 1&7&18&44&110&262\\ 1&6&11&26&66&152\\ 1&5&5&15&40&86\\ 1&4&0&10&25&46\\ 1&3&6&10&15&21\\ 1&2&3&4&5&6\\ 1&1&1&1&1&1\\ \end{pmatrix}\)

Therefore, there are 342 ways to go to (5,7).

MaxWong Jun 22, 2019