Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers 2

up vote 1 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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.