AMC12 2014 12A, Problem 13

A fancy bed and breakfast inn has $5$ rooms, each with a distinctive color-coded decor.  One day $5$ friends arrive to spend the night.  There are no other guests that night.  The friends can room in any combination they wish, but with no more than $2$ friends per room.  In how many ways can the innkeeper assign the guests to the rooms?

Solution: We can discern three cases. Case 1: Each room houses one guest. In this case, we have $5$ guests to choose for the first room, $4$ for the second, ..., for a total of $5!=120$ assignments. Case 2: Three rooms house one guest; one houses two. We have $\binom{5}{3}$ ways to choose the three rooms with $1$ guest, and $\binom{2}{1}$ to choose the remaining one with $2$. There are $5\cdot4\cdot3$ ways to place guests in the first three rooms, with the last two residing in the two-person room, for a total of $\binom{5}{3}\binom{2}{1}\cdot5\cdot4\cdot3=1200$ ways. Case 3: Two rooms house two guests; one houses one. We have $\binom{5}{2}$ to choose the two rooms with two people, and $\binom{3}{1}$ to choose one remaining room for one person. Then there are $5$ choices for the lonely person, and $\binom{4}{2}$ for the two in the first two-person room. The last two will stay in the other two-room, so there are $\binom{5}{2}\binom{3}{1}\cdot5\cdot\binom{4}{2}=900$ ways. In total, there are $120+1200+900=2220$ assignments, or $\fbox{2220}$. (Solution by AwesomeToad16)

Answer: 2220