Question

consider the xy-coordinate plane and the points with non-negative integer coordinates. at each step you can move one unit to the right or one unit up. find the number of routes that start at point (0,0) and end at (4,7) which do not pass through (3,3)

Answer 1

The total number of routes from (0,0) to (4,7) that do not pass through (3,3) is 35⋅70 = 2450

The solution to the problem:

To avoid passing through (3,3), we can divide the problem into two subproblems: reaching (4,3) and then reaching (4,7). For each subproblem, we can only move one unit to the right or one unit up.

To reach (4,3), we need to move 4 units to the right and 3 units up, for a total of 7 moves. There are 7/3 = 35 ways to arrange these 7 moves, which corresponds to the number of routes from (0,0) to (4,3) that do not pass through (3,3).

To reach (4,7) from (4,3), we need to move 4 units to the right and 4 units up, for a total of 8 moves. There are 8/4 =70 ways to arrange these 8 moves, which corresponds to the number of routes from (4,3) to (4,7) that do not pass through (3,3).

Therefore, the total number of routes from (0,0) to (4,7) that do not pass through (3,3) is 35⋅70 = 2450