Question

The streets of a city are arranged like the lines of a chessboard. There are m streets running from north to south and n streets from east to west. Find the number of ways in which the man can travel from north-west to the south-east corner covering the shortest possible distance.

Answer 1

Hint: In this question the concept of permutations and combinations will be used. We need to apply logic and general algebra to proceed through the problem. We will form linear equations and write the given constraints to find all the possible solutions. The number of ways to arrange n things when r things are identical are-
$\dfrac{{n!}}{{r!}}$

Complete step-by-step answer:

Let each line represent a street of the city. The man has to go from Q to R. If we make a graphical representation of this data, the man has to travel (m - 1) units toward the right(east) and (n - 1) units downwards(south).

This means that the man has to make m - 1 movements to the right and n - 1 to the bottom. The total movements to reach the destination will be-
m - 1 + n - 1 = m + n - 2
Out of these, the m - 1 movements to the right are identical, and the n - 1 movements to the bottom are also identical. We know that the number of ways to arrange n things when r things are identical are-
$\dfrac{{n!}}{{r!}}$
So, the total number of ways in which m + n - 2 movements can be made where m - 1 are identical and the rest n - 1 are also identical are-
$\dfrac{{\left( {{\text{m}} + {\text{n}} - 2} \right)!}}{{\left( {{\text{m}} - 1} \right)!\left( {{\text{n}} - 1} \right)!}}$
This is the required number of ways.

Note: There is no direct method to solve this problem. We need to form the equations according to the question, and simplify it using general algebra. One common mistake is that students often forget the formula for combinations and permutations, which should be remembered.