## Room for choice

Posted by Chris on July 18, 2010 – 5:07 pm

Five girls and one boy have to share four hotel rooms. Each room can hold up to two people, and the boy has to have a room to himself. How many different ways are there to assign the group to the rooms?

(Sorry, a bit boring).

July 18th, 2010 at 5:33 pm

I make 120 different possible combinations

July 18th, 2010 at 5:36 pm

I was hoping that it would last for more than one reply. And I have been lucky

July 18th, 2010 at 5:57 pm

glad to be of service then !

July 19th, 2010 at 12:22 am

18,432

July 19th, 2010 at 12:30 am

Let’s see:

The boy is allocated one room, then 5 girls can be chosen for two beds in the second room, that’s 20 possibilities, then 3 for the two beds in the third room, that’s 3 more, then there can be 3 allocations of the one bed room. So, for the boy in room 1 there are 180 possibilities.

With the boy in rooms 2, 3 and 4 there are a further 180 arrangements in each case.

My guess (very much a guess) is therefore 720.

July 19th, 2010 at 12:42 am

Five girls travel and one boy have to share four hotel rooms.

Each room can hold up to two people,

and the boy has to have a room to himself.

How many different ways are there to assign the group to the rooms?

First select boys room 4 choices of rooms

Select girl who will be alone 5 choices of girls

Choose solo girls room 3 choices of rooms

Choose group of two girls from remaining 4 . 4C2=4!/(2!(4-2)!)=6 choices

Place first group of 2 girls in room. 2 choices of rooms.

Choose remaining group of 2 girls. 1 choice

Choose remaining room to place girls in. 1 room.

#ways=4*5*3*6*2*1*1

#ways=720

Cam

July 19th, 2010 at 12:50 am

It seems I may have overestimated slightly!

The boy is always on his own, so 5 girls go into 3 rooms. I make that 48 combinations (3×2x2×2x2).

4 rooms can be arranged 18 different ways:

1,2,3,4

1,2,4,3

1,3,2,4 etc.

So the total number of possibilities is 48 x 18 = 864.

July 19th, 2010 at 1:16 am

6! it is and, as usual, my solution is covered by Cam

July 19th, 2010 at 2:27 am

OK, since my thunder was stolen once again, I went through the problem one more time in order to find more elegant solution (since we already know the answer and we work with 6 people – there should be something with simple permutations). So I came up with the following idea: Let the girls be numbered from 1 to 5, and the boy be number 6. We consider permutations of 6 elements and we have split the numbers into 3 double cells/ pairs. Since, the only possibility is to have 2 double rooms and 2 single rooms (and 6 is always in a single room!) to each permutation we can assign a room distribution, namely after splitting the pair in which 6 belongs, we already have 4 “groups” and they correspond to the population of the 4 rooms, e.g., if the permutation is 123456, then the initial splitting is (12) (34) (56), then we split the pair with 6 into two: (56) – (5) (6) and in room 1 are (12) in room 2 – (34), in room 3 5 and in room 4 – 6. When we switch the order in the pair in which 6 is, it is significant because it corresponds to changing the room number of 5 and 6, but when we permute only 1 and 2, or 3 and 4, or both (12) and (34) the room allocation is the same as the original one. Hence, we conclude that to each room distribution 4 permutations are assigned. Thus, the number of different possibilities should be #permutations/4=6!/4=2*3*5*6=240.

So which answer is correct – 720 or 240 (or none of them)? And in which solution (and where exactly) is the mistake?

July 19th, 2010 at 3:48 am

Wow, no correct answer. I knew that I hadn’t seen a combinatorial problem quite like this one before, but I hadn’t expected such a success at receiving the wrong answers.

I won’t analyse all the solutions. I’ll pick on Cam’s as it’s the easiest for me to deal with. Cam changed tactic for the fourh line (and only the fourth line) of his reasoning and so ended up overcounting.

July 19th, 2010 at 3:51 am

slavy

If I’m correctly interpreting your method, the err appears to be that it sets the solo girl as always having the room beside the boy. The solo girl, in fact, has 3 choices of rooms. This would explain why the result appears off by a factor of 3.

Cam

July 19th, 2010 at 3:55 am

True – the truth is always in between So I had 720, then I had 180, which of course I miscalculate and made it 240 (which is one quarter of the first answer) and now, if I average the two (geometrically!): sqrt(720*180)=360 So this is my third answer (actually my second one, because even I didn’t believe in post #9)

July 19th, 2010 at 3:58 am

Yes Cam, you are correct! And the problem in your (and mine, too) solution is that when you choose the first girl pair out of all possibilities, you don’t have to choose a room, as well! This choice is already made, since you can choose both two of the girls or the remaining two…

July 19th, 2010 at 4:02 am

I’ll go with – 1 way of dividing up the rooms.

July 19th, 2010 at 4:13 am

Hmm…. Rethinking the problem since Chris says 720 is no good.

Pick one of 4 rooms for the boy

Permutate remaining 3 rooms as oposed to people

AABBC

12345

means girls 1+ 2 in room A,3+ 4 in B, 5 in C

CBCAA

12345

means girls 1 + 3 in room 1, 2 in B, 4+5 in A

Two rooms will be repeated each time

AABBC Permutations=5!/(2!*2!)=720/4=30

AABCC=30

ABBCC=30

Number=5*(30+30+30)=450

Cam

July 19th, 2010 at 4:15 am

My answer is 360.

I numbered the columns as rooms 1-4

and then filled in the rows with possible combinations using the pairings suggested by Slavy (12)(34)(5)(6) so I began:

1 2 3 4

(12) (34) (5) (6)

(12) (34) (6) (5)

and continued this way obtaining 24 possible combinations.

Then I swapped pairings with 3 possible pairings keeping girl (5) on her own [(12)(34)], [(13)(24)], [(14)(23)]. So there are 72 possible outcomes with girl (5) on her own. Of course, each girl could be left on her own so there are 72 times 5 = 360 possible outcomes.

Am I right?

July 19th, 2010 at 4:17 am

Oh my goodness,

The last line should be Number=4*(30+30+30)=360

Answer= 360.

Cam

July 19th, 2010 at 4:33 am

Thank goodnes 360 lines up with slavy’s answer.

I guess I was double dipping. It seems straightforward when thinking of it as a permutation, but as a combination it seems to get murky.

Cam

July 19th, 2010 at 4:39 am

360 it is.

First put boy in his own room: 4 ways to do that (4)

Now there are three rooms and five girls. Since each room can hold only two of them, all the rooms will be used. There will be two doubles and a single (2 + 2 + 1).

There are 5 ways to choose the girl who will go solo, and 3 choices of room for her (15).

Then there are 3 ways to pair up the other 4 girls (3) and two ways to assign them to the other two rooms (2).

Multiplying all those together we get

4 * 15 * 3 * 2 = 60 * 6 = 360 ways.

July 19th, 2010 at 5:19 am

In order to make post #9 correct: as Cam pointed out, there we compute only the distributions where the two single room are neighbors and the answer there was 6!/4=180 (again, I appologize for the computational mistake in the post and the appearance of the irrelevant 240). But this is exactly half of all the cases, since out of 4 rooms, two are neighbors in 3 out of 6 cases ((1,2), (2,3), (3,4) are, and (1,3), (1,4), and (2,3) are not). Hence, the answer should be 2*180=360

July 19th, 2010 at 5:31 am

What about bunging into the mix a choice of, say, 2 suites, 1 executive and a standard room…..

I still think there is only one way to do it….

Boy on own, 1 girl on own and 2 rooms with 2 girls. I don’t care which girl is with which girl, or which room number they are in.

Also, as they are referred to as boys and girls, have they reached their majority yet, or will there be parental supervision? I hate to bring up “Hotel Proprietors Act 1956, Registration of Guests (Aliens)” allowing unsupervised juniors to stay at your hotel…;-)

July 19th, 2010 at 6:00 am

I had copied/pasted “my” solution. I notice that it changes tactic at the last step. For improved consistency, I would have said for the next girl there are 2 choices of room, and then 3 choices of who she shares with. So 4*(5*3)*(2*3) = 360

July 19th, 2010 at 2:00 pm

ah yes, I think I had discounted some combinations of pairings as I’d already had them paired together already, but must not have allowed for being paired but in a different room – don’t think I’ll go back and check though – too much else to do

March 20th, 2012 at 6:49 am

Let’s adjust the problem.

Five girls and one boy have to share four hotel rooms. Each room can hold up to THREE people, and the boy has to have a room to himself. Each room must have at least one person. How many different ways are there to assign the group to the rooms?