technical riddle This is the question about an empty room, and a group of people outside the room.  You can only put a person in the room, or take them out of the room.  Can you get every combination of people in the room and out? This is an intriguing question.  I believe the answer is yes.  First, treat each person as a bit in a bitstring.  If person i is in the room, then bit i is 1, and if they are outside, then bit i is 0. So now, you want every possible bit pattern given N people.  Furthermore, you want to avoid repeating patterns. Given an N bit number, there is a way to write each 2^N bit number such that you only ever flip 1 bit.  This is called a Gray code.  Essentially, you just go through the bit pattern, in Gray code order, flipping the one bit by moving the person in or out of the room. Gray code for 1 bit: 0, 1 Gray code for 2 bits: 00, 01, 11, 10 Gray code for 3 bits: 000, 001, 011, 010, 110, 111, 100, 100 The Gray code for N bits is defined recursively.  Take the Gray code for N - 1 bits.  Write it forwards, then write it backwards.  Prepend a 0 on the forward part, then prepend a 1 on the backward part. To illustrate: Gray code for 1 bit is: 0, 1 Write it forwards: 0, 1 Then backwards: 1, 0 Prepend the forward with a 0: 00, 01 Prepend the backward with a 1: 11, 10 Put the two together: 00, 01, 11, 10 Tricky! Charles Lin Wednesday, April 06, 2005 You can do gray codes on any even base (base 10 for example) 0-0..9 1-9..0 2-0..9 3-9..0 I believe they were used in analog counting devices such as ticket dispensers / turnstyles. Because Gray codes only have one changing number at a time, this eliminated the need to synchronize simultaneous rotations on separate dials - as a result the number of errors dropped dramatically. WanFactory Wednesday, April 06, 2005 Something is weird about the Gray code for 3 bits above... where is the 101? and the 100 is repeated twice. Michael H. Pryor Fog Creek SoftwareThursday, April 07, 2005 the second last entry should be 101 WanFactory Thursday, April 07, 2005 Yes, you can do it. Recursive proof: Suppose you can do it For N people, from any starting position i.e.: some of the guy are in the room and some are out. I will leave it as an exercise to solve this for N==1. Then for N+1 persons, from any starting position: 1) Ask everybody "who like to play baseball?", pick the first one to answer and nail him to the floor. 2) Shuffle everybody around according to your "N" algorithm. 3) Un-nail the unlucky guy. 4) Have him limp across the door. 5) Nail him back to the floor. 6) Reshuffle everybody else. 7) Un-nail the unlucky guy and send him to the hospital. QED. AlphaBeta AlphaBeta Monday, April 11, 2005   Fog Creek Home