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   Fog Creek Home