Fog Creek Software
Discussion Board




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 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) 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

*  Recent Topics

*  Fog Creek Home