# hotel occupancy counting problem

The multiple-choice question:

A hotel has four vacant rooms. Each room can accommodate a maximum of four people. In how many different ways can six people be accommodated in the four rooms? (A) 4020 (B) 4068 (C) 4080 (D) 4096.

My attempt:

If there were no 'four person' constraint, the six people could be accommodated in $4^6=4096$ ways. however, this number includes combinations with 5 or 6 people in one room, which should be excluded.

If one room has 5 occupants, one other room has 1 occupant. The number of '1,5' combinations is ${{4} \choose {2}}$=12. If one room has 6 occupants, the other three rooms have no occupants, and there are four such combinations.

I believe the answer should be $4096-12-4=4080$, but am not confident. I'd be grateful for any comments on my attempt.

## 3 Answers

The count of $5+1$ needs to be updated. You have $4$ ways to choose the room that $5$ will be in, $3$ ways to choose the room for $1$, and $6$ ways to choose the lone traveler. So the number of ways to accommodate the guests is $4096-4-4\cdot 3 \cdot 6=4096-76=4020$

• Are you sure? Up to this point we have treated the six people as fungible. Why should we now 'choose' the lone traveler? – Guy Corrigall Dec 24 '13 at 3:03
• When you said $4^6$ you assumed both the rooms and people were distinct. You get one factor of $4$ as you put each person in a room. If not, the result will be much smaller. – Ross Millikan Dec 24 '13 at 3:14
• Thank you - I've learned a lot from MSE on this problem. – Guy Corrigall Dec 24 '13 at 6:19

Seems perfectly fine. A slightly-different way: besides the 4 ways of having $6$ people in a room, for the case of $5$-to-a-room, there are 4 ways of choosing the room for the 5 people, and 3 ways to choose where the $6$th person will stay, for a total of $4(3)$=12. So you do get $4096-4-12=4080$ , like you said.

4^6 - 4 - 6C5 x 4C1 x 3C1 (from 6 people choose 5 to stay in 1 room, then choose 1 of the 4 room for the 5 people, then choose 1 of the remaining 3 rooms for the lone person)