I'll restate the problem since it doesn't have a very good title and is therefore hard to find:
"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?"
The answer is yes. Encode the current state of the system as an N-bit number where each bit represents the in/out state of one particular person. The current state is zero (all bits off = all people out of the room). At each move you can flip a single bit. Now the question is whether you can walk through all the combinations without repeating any. The answer is to flip the bits according to a Gray code, which can be constructed for n-bit numbers.
Tuesday, October 28, 2003
Fog Creek Home