
Answer to "technical riddles" (people in a room)
I found a solution by induction. Writing it so that people would understand it was a pain, so I'm sorry for the long answer  it really is quite simple. (if you find an error please let me know...)
There are N people outside the room. We'll number them 1..N.
In every solution, after the first step there is 1 person in the room (obviously). My claim is that for every N, there is a solution in which in the last step, there is also one person in the room. (the proof will actually build this solution).
Since it doesn't matter in which order the subgroups are formed, we can assume that the 1st person to enter the room is 1, and the last person staying in the room is N.
Induction base  There's such a solution for N=1:
action: group in the room:
 
1 enters 1
Just to illustrate, here are such solutions for N=2, N=3:
N=2:
action: group in the room:
 
1 enters 1
2 enters 1,2
1 leaves 2
N=3:
action: group in the room:
 
1 enters 1
2 enters 1,2
1 leaves 2
3 enters 2,3
1 enters 1,2,3
2 leaves 1,3
1 leaves 3
Let's say there's a solution to N1, and build a solution for N.
We'll first play the solution for N1:
action: group in the room:
 
1 enters 1
...
[ 1beforelast N1 action] X, N1
[ last N1 action] X leaves N1
The next action would be:
N enters N, N1
Now, we'll start playing the whole sequence of events that led us to the N1 solution, while N is in the room. The difference is that now we start the solution with 'N1' as the first person to enter the room, and not '1'. So whenever we had in the N1 solution a step saying "1 enters/leaves" we'll replace it with "N1 enters/leaves", and vice versa.
Also, the first step (which is always "1 enters") doesn't have to be repeated, because N1 is already in the room.
Since the last step in the N1 sequence resulted in N1 being the only person in the room, after we repeat the sequence with N in the room and replacing N1 with 1, we get the state:
action: group in the room:
 
[last N1 action] X leaves 1, N
So we got all the N1 states, repeated with N in the room. The only subgroup we're missing is N in the room alone, so now we add the action:
action: group in the room:
 
1 leaves N
Voila.
The reason this works is that every nonempty subgroup of 1..N is either:
1. a nonempty subgroup of 1..N1, or
2. such a subgroup + N, or
3. N alone.
The first part (N1 solution) gave as 1, the second part (N1 solution with N in the room) gave as 2, the 3rd part (N alone) gave us 3
If this was still not clear... here is the solution for N=4:
action: group in the room:
 
1 enters 1
2 enters 1,2
1 leaves 2
3 enters 2,3
1 enters 1,2,3
2 leaves 1,3
1 leaves 3
<= up to here, this is the N=3 solution =>
4 enters 3,4
<= now repeat the N=3 solution, replacing 1 with 3, and with 4 in the room =>
<= the step "3 enters" is not needed since 3 is already in the room =>
2 enters 2,3,4
3 leaves 2,4
1 enters 1,2,4
3 enters 1,2,3,4
2 leaves 1,3,4
3 leaves 1,4
<= Now the only missing subgroup is 4 by itself =>
1 leaves 4
Dov
Monday, September 09, 2002
There's a simple solution to this using Gray codes.
I'm not sure whether 'every combination of people appears once' means 'appears in the inner room' or 'appears in both the rooms', but it doesn't matter.
If you haven't heard of Gray codes, they are essentially sequences of binary numbers which differ in only one bit. It's easy to generate a Gray code over n bits, here's a simple way to do it:
Gray code for 1 bit:
0, 1
Take the Gray code for (n1) bits, and prefix it with '0': 00, 01.
Then follow this with the Gray code for (n1) bits in reverse order, prefixed by '1': 00, 01, 11, 10
This is a Gray code over 2 bits, by construction.
A Gray code over 3 bits is given by:
000, 001, 011, 010, 110, 111, 101, 100
Notice this contains every number from 000111.
If you want every combination of n people to appear in the inner room, use then entire nbit Gray code as the solution, i.e. for n=3 use
000  everyone outside
001  person 1 enters
011  person 2 enters
010  person 1 leaves
110  person 3 enters
111  person 1 enters
101  person 2 leaves
100  person 1 leaves
If you instead want 'every combination of people' to appear just once, whether it appears in the inner room or the outer room, then use the Gray code for n1 bits, and keep person 'n' outside always.
Then every combination without 'n' appears once inside the room, while every combination with 'n' appears outside the room.
DoRon
Monday, October 14, 2002
Recent Topics
Fog Creek Home
