Maths Olympiad Prep

Library / /81 of 196

Combinatorics Difficulty 5.0 AIME Prove it Soviet Union

Problem:

A rectangle ABCDABCD is drawn on squared paper with its vertices at lattice points and its sides lying along the gridlines. AD=k  ABAD = k \; AB with kk an integer. Prove that the number of shortest paths from AA to CC starting out along ADAD is kk times the number starting out along ABAB.

Solution

Solution:

Let ABCDABCD have nn lattice points along the side ABAB. Then it has knkn lattice points along the side ADAD. Let XX be the first lattice point along ABAB after leaving AA. A shortest path from XX to CC must involve a total of kn+n1kn + n - 1 moves between lattice points, n1n - 1 in the direction ABAB and knkn in the direction BCBC. Hence the total number of such paths is
(kn+n1)!(kn)!(n1)! \frac{(kn + n - 1)!}{(kn)!\,(n - 1)!}
Similarly, the number of paths starting out along ADAD is
(kn+n1)!(kn1)!n! \frac{(kn + n - 1)!}{(kn - 1)!\,n!}
Let m=(kn+n1)!(kn1)!(n1)!m = \frac{(kn + n - 1)!}{(kn - 1)!\,(n - 1)!}. Then the number starting along ABAB is mkn\frac{m}{kn} and the number starting along ADAD is mn\frac{m}{n}, which is kk times larger, as required.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.