In class we counted the number of shortest paths between diagonally opposite cor

Question

In class we counted the number of shortest paths between diagonally opposite corners of a square grid. In this problem we consider shortest paths from one corner (0, 0, 0) of a cube to the diagonally opposite corner at (8, 8, 8). Every step advances by one along exactly one of the three dimensions. What is the length of the shortest path from (0, 0, 0) to (8, 8, 8)? What is the number of shortest paths from (0, 0, 0) to (8, 8, 8)? Prove that the number of shortest paths in an n-dimensional hypercube from (0, ..., 0) to (8, ..., 8) is (8n)!/8!^n when each step advances by one along one of the n dimensions.

Explanation / Answer

(a) Since the number of steps in each of the three directions would be 8 units . Hence , total length of the path travelled would be the sum of the steps taken in each of the directions => 8 + 8 + 8 = 24 units

(b) Let the three direction be A , B and C . Total steps taken in each direction should be 8 and total steps in all should be 24 . Hence , making an arrangement by permuting the case would give the result 24!/( 8! * 8! * 8! )

(c) Similarly , for n-dimensional case , total number of steps taken from ( 0 , 0 , 0 . . . , 0 ) to ( 8 , 8 , 8 . . .. , 8 ) would be equal 8n and 8 steps in each of the dimension . By permuting the arrangement we get total number of ways as => ( 8n )! / ( 8! )n

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.