Fog Creek Software
Discussion Board




technical riddles  aha:!!


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?

The solution to this one should be trivial.
say there are n persons. represent each person with a bit so
n .......... 1
0 .......... 0
1 means the person`s in the room and 0 means he is out.

so we can have number sequences like
0000000000001
0000000000011
0000000000010
0000000000110
0000000000111
0000000000101
and so on
this works because each time only one bit is different which means that only one person is out or in whatever.

Comments welcome !!

Govind Jajoo
Thursday, March 14, 2002

To be more specific, this problem is similar to the towers of Hanoi, in that the solution (sequence) for n contains the sequence for n-1.  The interesting thing is that the n-1 sequence appears exactly twice in the n sequence, once forward and once backward.

For example. let's look at n=2, then 3:

for 2 people, it's simple:
00
01
11
10

for 3 people, it looks like this:
000
001
011
010
110
111
101
100
Notice that the first four steps are just the same as the n=2 sequence.  The fifth step brings in the 3rd person, and then we reverse the steps.

I don't know whether this is the only solution or not.

scott
Thursday, March 14, 2002

Way back when I was doing basic comp sci, I came across a method of storing binary data which ensured that the number of bits that only one bit every changed between subsequent numbers (exactly as has been described above).

I wondered whether this storage system was ever used in any actual chip architectures -- but I never heard it mentioned again.

Presumably having one-bit changes between subsequent integers doesn't trade off well against having each bit represent a power of two, being easily able to represent negatives, being easily able to add and subtract, etc...

Adrian

Adrian Gilby
Sunday, March 17, 2002

*cough* Gray Code *cough*
http://mathworld.wolfram.com/GrayCode.html

Ed Kaulakis
Wednesday, March 20, 2002

Yes, the solutions are Gray codes, and they correspond to paths through hypercubes.  It's an easy induction proof to show that solutions do exist, and if you think about it for a little while, you can see that there are at least n! solutions (though these solutions are not different in any fundamental way, though for n=3 there are solutions that are "more" different).
An interesting twist is if the only person who can leave the room is the one who's been there longest.  The problem becomes *much* harder, and not possible in general (IIRC).

Brian McKeever
Tuesday, April 02, 2002

*  Recent Topics

*  Fog Creek Home