Fog Creek Software
Discussion Board




technical riddles - further exploration

Hi,

the common answer I found to this problem involved Gray Code. That's essentially the answer I

came up with, too, upon first seeing the question.

A friend of mine came up with this pattern for three people A, B, C:

A__
AB_
ABC
A_C
__C
_BC
_B_

I realized, that one can expand this solution to work with four people, by inserting additional steps into the above sequence (marked by a '<'):

A___
A__D <
AB_D <
AB__
ABC_
ABCD <
A_CD <
A_C_
__C_
__CD <
_BCD <
_BC_
_B__
_B_D <
___D <

Please note that the steps I inserted beginning between the first and the second original step are just original step 1 + D, and original step 2 + D. In general, I just inserted two steps which resemble the step right before and right after them with an additional D.

Any idea if this holds for any number of people?


Stefan

Stefan
Monday, July 05, 2004

Here's the question, btw:

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?

I think your solution may be generalizable, but it is easier to generalize it like this:

Solution for 1:
_
A

Solution for 2: (Repeat the solution for 1 twice, once forward and once backward, with an intervening move for person B)

__
A_
AB < B moves
_B

Solution for 3: Repeat the solution for 2 twice, once forward and once backward, with an intervening move for person C)

___
A__
AB_
_B_
_BC < C Moves
ABC
A_C
__C

Solution for n: Repeat the solution for n-1 twice, once forward and once backward, with an intervening move for person n.

Brad Corbin
Friday, July 09, 2004

There's probably a way to do this using some binary math, but it doesn't immediately occur to me. Doing simple binary counting doesn't work because several people would have to move at once, which isn't allowed here.

Brad Corbin
Friday, July 09, 2004

Your solution, Brad, is the classic Gray code approach, and I think that's what Stefan was refering to at the beginning of his post.

Basically, your soulution, Stefan, is the same, as you just changed the order of the steps. As Brad pointed out, his solution is, however, far easier to remember.

The more general question, I think, would then be, whether there are other patterns, according to whom one could solve this problem. Are there others who have come up with a different approach?

John K.
Tuesday, July 13, 2004

The state is determined by which people are in the room, ie. an n-vector, each coord being 0 (out) or 1 (in). All the possibilities represent the corners of the 0-1 n-diml cube, and possible moves the edges of it.

A solution is a root starting from 0 passing along edges visiting each vertex exactly once. Drawing a 3-cube, it's easy to see there's lots of them. (18 in this case. 6 possibilities for the first two moves, all of which are the same up to isomorphism, and 3 routes from there.)

It's obvious there are lots more for more people, but I don't have a general formula at the moment.

Jack
Friday, July 30, 2004

If we map each person's in/out state to a bit position in an n-bit register, then cycling the register as a Gray code counter specifies the sequence in which people should enter or leave the room.  (The Gray code is the only code in which adjacent count states differ by exactly one bit position, so no other sequencing strategies exist.) Since there are n! possible ways to map people to bit positions, there are n! corresponding entry / exit sequences.  Each 'legal' path along the vertices of Jack's n-cube corresponds to one of those n! sequences.

If you treat the register as a  binary number, the sequence for 2 people would be 0, 1, 3, 2; for 3 people it would be 0,1,3,2,6,7,5,4; for 4 people it would be 0,1,3,2,6,7,5,4,12, 13,15,14,10,11,9,8; etc...  In general, when each new bit position is toggled, you reverse the count direction on the lower order bits.

Chuck Boyer
Saturday, August 07, 2004

For n people, just consider an N dimensional hypercube. The problem boils down to the fact that any dimension hypercube has a hamiltonial path.

Aryabhatta
Monday, August 09, 2004

Please note, any sequence that implements the solution to htis problem is a Gray code by definition. The "binary reflected Gray code" is just one that is easy to construct.

Ham Fisted
Saturday, August 21, 2004

*  Recent Topics

*  Fog Creek Home