HMMT-Nov 2009 guts, Problem 31

There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ziplines can go up, stay flat, or go down, but can't touch each other (this includes touching at their endpoints). Note that you can't string a zipline between two floors of the same building.

Solution: Associate with each configuration of ziplines a path in the plane as follows: Suppose there are $k$ ziplines. Let $a_{0}, \ldots, a_{k}$ be the distances between consecutive ziplines on the left building ( $a_{0}$ is the floor on which the first zipline starts, and $a_{k}$ is the distance from the last zipline to the top of the building). Define $b_{0}, \ldots, b_{k}$ analogously for the right building. The path in the plane consists of starting at $(0,0)$ and going a distance $a_{0}$ to the right, $b_{0}$ up, $a_{1}$ to the right, $b_{1}$ up, etc. We thus go from $(0,0)$ to $(5,5)$ while traveling only up and to the right between integer coordinates. We can check that there is exactly one configuration of ziplines for each such path, so the answer is the number of paths from $(0,0)$ to $(5,5)$ where you only travel up and to the right. This is equal to $\left(\begin{array}{c}10 \\ 5\end{array}\right)=252$, since there are 10 total steps to make, and we must choose which 5 of them go to the right. $\fbox{252}$.

Answer: 252