Marvin the fly starts at $(0,0).$ Each step, Marvin moves one unit right or one unit up. He is trying to get to the point $(5,7)$. However, at $(4,3)$ there is a frog that will eat him if he goes through that point. In how many ways can Marvin reach $(5,7)$?
Could anyone post the answer? I would like to check my work. Thanks in advance!
I need help on this
To find the number of ways Marvin can reach $(5,7)$ without going through the point $(4,3)$, we can use a concept called dynamic programming.
Let's define a two-dimensional array $dp[i][j]$ which represents the number of ways Marvin can reach the point $(i,j)$ while avoiding the frog at $(4,3)$. We will use the convention that $dp[i][j] = 0$ if $(i,j)$ is an invalid point.
The base cases for the dynamic programming algorithm are as follows:
- $dp[0][0] = 1$ (Marvin starts at $(0,0)$, so there is only one way to reach that point)
- $dp[i][0] = 1$ for $1 \leq i \leq 5$ (Marvin can only move right to reach these points)
- $dp[0][j] = 1$ for $1 \leq j \leq 7$ (Marvin can only move up to reach these points)
Now, we can fill in the dynamic programming array $dp$ using the following recurrence relation:
$$
dp[i][j] = \begin{cases}
dp[i-1][j] + dp[i][j-1] & \text{if } (i,j) \neq (4,3) \\
0 & \text{if } (i,j) = (4,3)
\end{cases}
$$
Starting from $(1,1)$, we can iteratively fill in the values for $dp[i][j]$ using the above recurrence relation. Finally, we will have $dp[5][7]$, which represents the number of ways Marvin can reach $(5,7)$ while avoiding $(4,3)$.
In this case, we can calculate $dp[5][7] = 35$.
Therefore, there are 35 ways for Marvin to reach the point $(5,7)$ without going through the point $(4,3)$.
You probably have a formula f(x,y) for getting from (0,0) to (x,y).
Seems like this would be f(5,7) - f(4,3) - f(5-4,7-3)
That is, throw away all the paths that lead to (4,3), and then throw away all the paths that would lead from (4,3) to (5,7)