Question

In: Statistics and Probability

Consider a grid with vertices from (0,0) to (20,20), in which edges can only be traversed...

Consider a grid with vertices from (0,0) to (20,20), in which edges can only be traversed up or right. Think of a street grid with intersections labelled by pairs of integers, and all one-way streets. How many paths, going only up and right, are there in the grid which do not pass through either forbidden intersection, if: (1) There are forbidden nodes at grid points (12,7) and (7,12)? (2) There are forbidden nodes at grid points (6,6) and (13,13)?

Solutions

Expert Solution

Total paths from (20,20) is computed here as:

= (20 + 20)! / (20! 20!)

= 40! / (20! 20!)

= 137846528820

a) Total paths from (0,0) to (20,20) through (12,7) is computed here as:

= [ (12 + 7)! / 12! 7! ]*[ (40 - 19)! / (20 - 12)! (20 - 7)! ]

= (19! / 12!7!)*(21! / 8!13!)

= 10253454120

Total paths from (0,0) to (20,20) through (7,12) is computed here as:

= [ (12 + 7)! / 12! 7! ]*[ (40 - 19)! / (20 - 12)! (20 - 7)! ]

= (19! / 12!7!)*(21! / 8!13!)

= 10253454120

Note that the person cannot pass through both the points (12,7) and (7,12)

Therefore, the total number of paths required here is computed as:
= 137846528820 - 2*10253454120

= 117339620580

Therefore there are 117339620580 total paths possible here.

b) Total paths from (0,0) to (20,20) through (6,6)

= (12!) / (6!6!) * (28! / 14! 14!)

= 37067738400

Total paths from (0,0) to (20,20) through (13,13)

= (26!) / (13!13!) * (14! / 7! 7!)

= 35694859200

Total paths from (0,0) to (20,20) through both the points (6,6) and (13,13)

= (12!) / (6!6!)*(14! / 7!7!)*(14! / 7! 7!)

= 10883448576

Therefore total number of paths allowed here is computed as:

= Total paths - total paths from (0,0) to (20,20) through (6,6) - Total paths from (0,0) to (20,20) through (13,13) + Total paths from (0,0) to (20,20) through both the points (6,6) and (13,13)

= 137846528820 - 37067738400 - 35694859200 + 10883448576

= 75967379796

Therefore 75967379796 is the required total number of paths allowed here.


Related Solutions

Consider a network with N vertices and M edges. A. If N=2481 and M=2481. Find the...
Consider a network with N vertices and M edges. A. If N=2481 and M=2481. Find the number of circuits in the network.
Consider the m by n grid graph: n vertices in each of m rows, and m...
Consider the m by n grid graph: n vertices in each of m rows, and m vertices in each of n columns arranged as a grid, and edges between neighboring vertices on rows and columns (excluding the wrap-around edges in the toric mesh). There are m n vertices in total. a)What is the diameter of this graph? b) From the top left vertex to the bottom right vertex, how many shortest paths are there? Please explain.
(a) Given a 4×4 grid, how many different paths from (0,0) to (4,4) satisfy the following...
(a) Given a 4×4 grid, how many different paths from (0,0) to (4,4) satisfy the following condition: • You can only go from (x, y) to either (x+1, y) or (x, y+1) (b) Given a 4×4 grid, how many different paths from (0,0) to (4,4) satisfy the following condition: • You can only go from (x, y) to either (x+1, y) or (x, y+1) • You cannot go to points (x, y) where y > x, in other word, you...
Consider an undirected graph G that has n distinct vertices. Assume n≥3. How many distinct edges...
Consider an undirected graph G that has n distinct vertices. Assume n≥3. How many distinct edges will there be in any circuit for G that contains all the vertices in G? What is the maximum degree that any vertex in G can have? What is the maximum number of distinct edges G can have? What is the maximum number of distinct edges that G can have if G is disconnected?
Consider a regular 10-gon in which alternate vertices are painted red and blue. Show that the...
Consider a regular 10-gon in which alternate vertices are painted red and blue. Show that the symmetry group of the painted 10-gon is isomorphic to D5.
Consider the following figure. A hexagon has six labeled vertices and a dashed line segment which...
Consider the following figure. A hexagon has six labeled vertices and a dashed line segment which divides the hexagon into a trapezoid and rectangle. The first side is horizontal, starts at vertex R, goes to the right, and ends at vertex S. The second side is vertical, starts at vertex S, goes up, and ends at vertex T. The third side starts at vertex T, goes up and to the right, and ends at vertex V. The fourth side is...
Consider the two investments shown below, only one of which can be chosen. They are one-shot...
Consider the two investments shown below, only one of which can be chosen. They are one-shot investments. Calculate AW2-1 assuming 13.2305 interest rate. EOY Alternative 1 Alternative 2 0 - 20,286 - 40,370 1 3,741 1,000 2 3,741 1,800 3 3,741 2,600 4 3,741 3,400 5 3,741 4,200 6 5,000 7 5,800 8 6,600
Consider the two investments shown below, only one of which can be chosen. They are one-shot...
Consider the two investments shown below, only one of which can be chosen. They are one-shot investments. Calculate AW2-1 assuming 15.2628 interest rate. EOY Alternative 1 Alternative 2 0 - 24,423 - 48,780 1 2,729 1,000 2 2,729 1,800 3 2,729 2,600 4 2,729 3,400 5 2,729 4,200 6 5,000 7 5,800 8 6,600
Consider the two investments shown below, only one of which can be chosen. They are one-shot...
Consider the two investments shown below, only one of which can be chosen. They are one-shot investments. Calculate AW2-1 assuming 13.2305 interest rate. EOY Alternative 1 Alternative 2 0 - 20,286 - 40,370 1 3,741 1,000 2 3,741 1,800 3 3,741 2,600 4 3,741 3,400 5 3,741 4,200 6 5,000 7 5,800 8 6,600
Consider the two investments shown below, only one of which can be chosen. They are one-shot...
Consider the two investments shown below, only one of which can be chosen. They are one-shot investments. Calculate AW2-1 assuming 14.7914 interest rate. EOY Alternative 1 Alternative 2 0 - 20,301 - 58,577 1 2,706 1,000 2 2,706 1,800 3 2,706 2,600 4 2,706 3,400 5 2,706 4,200 6 5,000 7 5,800 8 6,600
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT