
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)
00..9
19..0
20..9
39..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 Software Thursday, 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) Unnail the unlucky guy.
4) Have him limp across the door.
5) Nail him back to the floor.
6) Reshuffle everybody else.
7) Unnail the unlucky guy and send him to the hospital.
QED.
AlphaBeta
AlphaBeta
Monday, April 11, 2005
Recent Topics
Fog Creek Home
