Fog Creek Software
Discussion Board




technical riddles - solution

"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?"

First let us prove that this is achievable for some known number of persons. Take 2 persons' case.
      | AB
A  | B
AB |
  B | A

I will try to prove if it is possible for n persons, then that it is possible in the case of n+1 persons.
You send that one extra person inside the room. Now on the outside of the room there are n persons, who can achieve the challenge, as per our assumption. Since the extra person is inside the room, s/he is participating in this process. Now bring that one person out, and you have the mirror image - the rest of  n persons are inside. Repeat the combination process while the extra persons stays outside (except the last step when everyone would be outside, because this was achieved at the beginning of the process). Thus it is proved that it is possible for n+1 persons' case if it is possible for n persons' case.

Since we proved that it is possible for 3 persons' case in the beginning, we have a solution.

Tada?

Raghuram
Saturday, January 04, 2003

Grey code.

Danil
Tuesday, January 07, 2003

*  Recent Topics

*  Fog Creek Home