Fog Creek Software
Discussion Board




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 sub-groups 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 N-1, and build a solution for N.

We'll first play the solution for N-1:

action:                      group in the room:
-----------          -----------------------
1 enters                                  1
...
[ 1-before-last N-1 action]    X, N-1
[ last N-1 action] X leaves     N-1

The next action would be:

N enters            N, N-1

Now, we'll start playing the whole sequence of events that led us to the N-1 solution, while N is in the room. The difference is that now we start the solution with 'N-1' as the first person to enter the room, and not '1'. So whenever we had in the N-1 solution a step saying "1 enters/leaves" we'll replace it with "N-1 enters/leaves", and vice versa.

Also, the first step (which is always "1 enters") doesn't have to be repeated, because N-1 is already in the room.

Since the last step in the N-1 sequence resulted in N-1 being the only person in the room, after we repeat the sequence with N in the room and replacing N-1 with 1, we get the state:

action:               group in the room:
-------                -----------------
[last N-1 action] X leaves    1, N


So we got all the N-1 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 non-empty subgroup of 1..N is either:

1. a non-empty subgroup of 1..N-1, or
2. such a subgroup + N, or
3. N alone.
The first part (N-1 solution) gave as 1, the second part (N-1 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 (n-1) bits, and prefix it with '0': 00, 01.
Then follow this with the Gray code for (n-1) 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 000-111.

If you want every combination of n people to appear in the inner room, use then entire n-bit 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 n-1 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