We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
112
3
avatar

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)?

 Jun 15, 2019
 #1
avatar+8718 
+1

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

 Jun 15, 2019
 #2
avatar+208 
-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.

 Jun 15, 2019
 #3
avatar+7711 
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 dpi,j, where (i,j) is the coordinates of the bug, and dpi,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, dp2,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 dp0,0 and top right corner is dp5,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).

 Jun 22, 2019

30 Online Users

avatar