Shortest Path Concept
Consider a Grid m×n. then we are to find the number of shortest path from one corner to diagonally opposite corner.
Proof with Example:-
Consider a 5×8 Grid. what is the minimum number of ways a person can travel from one corner to diagonally opposite corner?
Since we are to go from (0,0) to (5,8). & since (5,8) is 8 step right & 5 step up from (0,0).
So we move in anyway but to reach (5,8) we have to ultimately travel 8 steps right & 5 steps up.
we can travel these R & U steps in any order but the total steps will always be (8+5) = 13
→ we are to find the number of ways in which we can complete these 13 steps ⇒
In these 13 steps path for a particular horizontal 8 steps there is only 1 option left for 5 verticle steps & vice-versa.
So we are to only select 8 or 5 steps from total 13 steps which will be our final answer.
Hence total number of shortest path = ¹³C₈ = ¹³C₅ Answer