+68 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)$?
(it's not 782 btw)
+506 First, ignore the fact that there is a frog, and just calculate the number of ways that Marvin can reach \((5, 7)\) only going up and right.
To do that, Marvin must move 5 units to the right and 7 upwards to the right using exactly 12 moves. This is the same question as all the different distinguishable combinations of the string of letters \(RRRRRUUUUUUU\), where R represents right and U represents up. There are \({12 \choose 5} = {12 \choose 7} = 792 \) ways to do that.
Now, we need to find the number of ways that Marvin will encounter the frog. Specifically, Marvin needs to move 4 units to the right and 3 units upwards in his first 7 moves (while his other 5 moves could be in any order). Using the same logic above, the number of possible different distinguishable ways to order the string of letters \(RRRRRUUUUUUU\) in which the first 7 letters must contain 4 R's and 3 U's, is equal to \({7 \choose 3} \cdot {5 \choose 1} = 175\) ways. That is the number of ways that Marvin will meet the frog and get eaten.
Since we don't want that to happen, just subtract the total number of ways he is going to get to (5, 7) by the number of ways he is going to get eaten, which is equal to \(792-175=\boxed{617}\) ways.
+506 First, ignore the fact that there is a frog, and just calculate the number of ways that Marvin can reach \((5, 7)\) only going up and right.
To do that, Marvin must move 5 units to the right and 7 upwards to the right using exactly 12 moves. This is the same question as all the different distinguishable combinations of the string of letters \(RRRRRUUUUUUU\), where R represents right and U represents up. There are \({12 \choose 5} = {12 \choose 7} = 792 \) ways to do that.
Now, we need to find the number of ways that Marvin will encounter the frog. Specifically, Marvin needs to move 4 units to the right and 3 units upwards in his first 7 moves (while his other 5 moves could be in any order). Using the same logic above, the number of possible different distinguishable ways to order the string of letters \(RRRRRUUUUUUU\) in which the first 7 letters must contain 4 R's and 3 U's, is equal to \({7 \choose 3} \cdot {5 \choose 1} = 175\) ways. That is the number of ways that Marvin will meet the frog and get eaten.
Since we don't want that to happen, just subtract the total number of ways he is going to get to (5, 7) by the number of ways he is going to get eaten, which is equal to \(792-175=\boxed{617}\) ways.
