Problem:
A rectangle is drawn on squared paper with its vertices at lattice points and its sides lying along the gridlines. with an integer. Prove that the number of shortest paths from to starting out along is times the number starting out along .
Problem:
A rectangle is drawn on squared paper with its vertices at lattice points and its sides lying along the gridlines. with an integer. Prove that the number of shortest paths from to starting out along is times the number starting out along .
Solution:
Let have lattice points along the side . Then it has lattice points along the side . Let be the first lattice point along after leaving . A shortest path from to must involve a total of moves between lattice points, in the direction and in the direction . Hence the total number of such paths is
Similarly, the number of paths starting out along is
Let . Then the number starting along is and the number starting along is , which is times larger, as required.