HMMT-Feb 2011 guts, Problem 14

Danny has a set of 15 pool balls, numbered $1,2, \ldots, 15$. In how many ways can he put the balls in 8 indistinguishable bins such that the sum of the numbers of the balls in each bin is 14,15 , or $16 ?$

Solution: Clearly, the balls numbered $15,14, \ldots, 9,8$ must be placed in separate bins, so we number the bins $15,14, \ldots, 9,8$. Note that bins 15 and 14 may contain only one ball while all other bins must contain at least two balls. We have two cases to examine. Case 1: Only one bin contains exactly one ball. Let $a_{i}$ denote the number of ways to place the balls numbered $1,2, \ldots, i-1$ into the bins numbered $15,14, \ldots, 15-i+1$. We can place either $i-1$ or $i-2$ into the bin numbered $15-i+1$. If we place $i-1$ in there, then there are $a_{i-1}$ ways to finish packing the rest. If we place $i-2$ in this bin, then $i-1$ must be placed in the bin numbered $15-i+2$, so there are $a_{i-2}$ ways to place the rest of the balls. Therefore $a_{i}=a_{i-1}+a_{i-2}$. Since $a_{1}=2$ and $a_{2}=3$, the sequence $\left\{a_{i}\right\}$ is the Fibonacci sequence, and $a_{7}=34$. Case 2: Both bins 14 and 15 contain only one ball. A pair of balls from 1-7 must be put together to one of the bins numbered 8 through 13. This pair has sum at most 8 , so we can count for all the cases. \begin{center} \begin{tabular}{c|c} Balls & Number of packings \\ \hline 1,2 & 16 \\ \hline 1,3 & 10 \\ \hline 1,4 & 12 \\ \hline 1,5 & 12 \\ \hline 1,6 & 10 \\ \hline 1,7 & 8 \\ \hline 2,3 & 6 \\ \hline 2,4 & 4 \\ \hline 2,5 & 4 \\ \hline 2,6 & 3 \\ \hline 3,4 & 2 \\ \hline 3,5 & 1 \\ \hline \end{tabular} \end{center} Therefore, there are 88 possibilities in this case, and the total number of possibilities is 122 . $\fbox{122}$.

Answer: 122