Fog Creek Software
Discussion Board




technical riddles (#61)

You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?

.... solution follows .....




Mention this to a (digital) electrical engineer and they should remember about "Gray codes" and work out the solution from there.

http://mathworld.wolfram.com/GrayCode.html

If the link tests your patience, it's easy to work up the solution of this problem by induction.

Let's say you just have one person. Send him into the empty room and you're done. Or, if we represent the presence of a person in the room as 1 and the absence as 0,

A
0 (empty)
1 (A goes in)

For two people named A and B, the solution is almost as easy:

AB
00 (empty)
10 (A goes in)
11 (B goes in)
01 (A comes out)

Now, if you are thinking inductively, the question becomes, "how do we construct the solution for N+1 people, given the solution for N people?"

Assume we can achieve all combinations of N people in a room while moving one at a time and not repeating states. With N+1 people we need to achieve twice as many states--all combinations of N people without Mr. N+1, and all combinations of N people with Mr. N+1.

Below is the soluiton for three people, with whitespace added for emphasis.

AB C
00 0
10 0
11 0
01 0

01 1
11 1
10 1
00 1

So we just run the solution for N people, then send Mr. N+1 in, then run the solution for N people again, only... (here's a very minor "aha"...) backwards.

Peter Meilstrup
Tuesday, April 08, 2003

*  Recent Topics

*  Fog Creek Home