Fog Creek Software
Discussion Board




People in a room

For one person, it's easy.  Likewise for two.  It takes one step for one person, and 3 for two, and I'm certain 7 for three people.  The formula would be (2^N)-1 steps for N people.  You would have to take that many steps exactly; any more would mean you're getting a combination more than once.

You could denote a step by assigning a number to each person, and then using that number to mean either moving that person into the room or out of the room.  So for one person, the step sequence is 1.  For two people, it's 1-2-1.  For three, it's 1-2-1-3-1-2-1.  I suspect you can use this pattern forever.  To get the sequence for N people, first get the sequence for N-1 people, append the number N, then append the N-1 sequence again.

I can see that it works.  It works for the base case with one person.  If it works for N people, it works for N+1 people, because the N sequence runs through all possibilities for N people, the number N+1 moves the (N+1)th person into the room, and then the N sequence would run through all the possibilities for N people with the (N+1)th in the room.

Paul Brinkley
Friday, January 25, 2002

Yes, there is a possible solution regardless of the number of people. Here is the proof:

For this explanation, think of the people in the room as a simple bit pattern. Use a 1 to represent someone who is in the room, while a 0 represents someone not in the room. If there were 8 people, and persons 1, 3, 5, and 7 were in the room, their statuses would be represented as follows:

10101010

Start with a scenario where there is only one person.

In step 1, noone is in the room. In step 2, person 1 is in the room.

Diagram this as follows:

0
1

Now, if you add a second person, you can take both of the steps for 1 person, and add a 0 to the chain. (In other words, for each of the first 2 steps, a second person was not in the room.)

So the first 2 steps for 2 people look like this:
00
10

To complete the equation for 2 people, simply add 2 more steps, reversing the order of the value for the first person, while the second person is consistently in the room. It looks like this:

00
10
11
01

All 4 combinations have been accomplished within the bounds of the problem.

Now add a 3rd person, which means you again double the number of steps (now 8 steps). This time, for the latter stage, again reverse the bits for the first 2 people, while the third person is consistently a 1.

It looks like this:
000
100
110
010
011
111
101
001

Move on to 4 people, again by doubling the number of steps, reversing the order of the bits for the first 3, and consistently having a 1 bit for the 4th person.

0001
1001
1101
0101
0111
1111
1011
0011
0011
1011
1111
0111
0101
1101
1001
0001

Once you understand the pattern, you can see that this can be done infinitely.

Abel Solutions
Friday, January 25, 2002

As the second solution illustrates, this problem can be solved for the n person case using a "gray code" for the number 2^n, and gray codes exist for all n.

Joel Wollman
Friday, January 25, 2002

well, basically all this problem involves is counting in binary.  you hit it on the head to assign each person a 1 or 0 for in or out.  then the "steps" you have to outline is simply to bring them in and out as if you are counting in binary, with each person representing a bit position.

example with three people:

1) bring in A (001 = decimal 1)
2) take out A, 3) bring in B (010 = decimal 2)
4) bring in A (011 = decimal 3)
5) take out A, 6) take out B, 7) bring in C (100 = 4)
8) repeat 1 (101 = 5)
9) repeat 2, 3 (110 = 6)
10) repeat 4 (111 = 7)

so simply following a pattern of counting in binary will guarantee everyone combination gets hit.  if you are asking about the minimal number of steps, i suspect this would be it but i am not sure.

sundog
Monday, January 28, 2002

a slight point in the above solution : a simple linear counting will repeat positions in the room. the trick is to make sure that there is only one 'bit value' change between two cosecutive steps.

shailesh kumar
Monday, February 04, 2002

regarding the comment "the trick is to make sure that there is only one 'bit value' change between two cosecutive steps," that's what gray codes are all about, hence the previous comment.

john mahoney
Wednesday, February 06, 2002

A little bit more diffucult problem is:
there are N1 people in first room and N2 people in second room, how to get all non-repeatable combinations ?

Nbrnr
Tuesday, March 05, 2002

*  Recent Topics

*  Fog Creek Home