<p>The streets of a city are arranged like the lines of a chessboard. There are <em>m</em> streets running from north to south and <em>n</em> streets from east to west. Find the number of ways in which a man can travel from north-west to south-east corner, covering the shortest possible distance.</p>
Step-by-Step Solution
Key Concept: The man must move exactly (m-1) steps south and (n-1) steps east in some order; the shortest path problem reduces to arranging these fixed moves, which is a combinations problem of choosing positions for one type of move.
<p><strong>Step 1:</strong> Visualize the grid. With m north-south streets and n east-west streets, the intersections form a grid. To go from NW corner to SE corner via shortest path, the man must cross exactly <strong>(m-1) blocks south</strong> and <strong>(n-1) blocks east</strong>.</p><p><strong>Step 2:</strong> Total moves required = (m-1) + (n-1) = m+n-2. Each path is a sequence of these moves: some combination of S's (south) and E's (east).</p><p><strong>Step 3:</strong> The number of distinct shortest paths = number of ways to arrange (m-1) south moves and (n-1) east moves = choosing (m-1) positions for south moves from (m+n-2) total positions.</p><p><strong>Step 4:</strong> This equals C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)!(n-1)!}</p><p>∴ Answer: \frac{(m+n-2)!}{(m-1)!(n-1)!}</p>
Correct Answer: \frac{(m+n-2)!}{(m-1)!(n-1)!}