Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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$

share|cite|improve this answer
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.

share|cite|improve this answer

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)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.