HMMT-Nov 2009 gen, Problem 7

There are 15 stones placed in a line. In how many ways can you mark 5 of these stones so that there are an odd number of stones between any two of the stones you marked?

Solution: Number the stones 1 through 15 in order. We note that the condition is equivalent to stipulating that the stones have either all odd numbers or all even numbers. There are $\left(\begin{array}{l}8 \\ 5\end{array}\right)$ ways to choose 5 odd-numbered stones, and $\left(\begin{array}{l}7 \\ 5\end{array}\right)$ ways to choose all even-numbered stones, so the total number\\ of ways to pick the stones is $\left(\begin{array}{l}8 \\ 5\end{array}\right)+\left(\begin{array}{l}7 \\ 5\end{array}\right)=77$. $\left(\left(\begin{array}{l}n \\ k\end{array}\right)\right.$ is the number of ways to choose $k$ out of $n$ items. It equals $\left.\frac{n !}{k !(n-k) !}\right)$. $\fbox{77}$.

Answer: 77