Maths Olympiad Prep

Track / Stage 3 / 73 of 260 #73 of 1964

Problem 73

AMC 10/12, early questions
Combinatorics Difficulty 3.1 Multiple choice

A fancy bed and breakfast inn has 55 rooms, each with a distinctive color-coded decor. One day 55 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 22 friends per room. In how many ways can the innkeeper assign the guests to the rooms?

Pick one

Official solution

We can discern three cases.
Case 1: Each room houses one guest. In this case, we have 55 guests to choose for the first room, 44 for the second, ..., for a total of 5!=1205!=120 assignments.
Case 2: Three rooms house one guest; one houses two. We have (53)\binom{5}{3} ways to choose the three rooms with 11 guest, and (21)\binom{2}{1} to choose the remaining one with 22. There are 5435\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 (53)(21)543=1200\binom{5}{3}\binom{2}{1}\cdot5\cdot4\cdot3=1200 ways.
Case 3: Two rooms house two guests; one houses one. We have (52)\binom{5}{2} to choose the two rooms with two people, and (31)\binom{3}{1} to choose one remaining room for one person. Then there are 55 choices for the lonely person, and (42)\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 (52)(31)5(42)=900\binom{5}{2}\binom{3}{1}\cdot5\cdot\binom{4}{2}=900 ways.
In total, there are 120+1200+900=2220120+1200+900=2220 assignments, or (B)\boxed{\textbf{(B)}}.
(Solution by AwesomeToad16)

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.