Friday, February 9, 2007
You have an empty room, and a group of people waiting outside the room
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?
Subscribe to:
Post Comments (Atom)
Yes it is possible. Think about the analogy of binary numbers and proceed with induction. Trivial for n=1. For n=2 the series: 00, 01, 11, 10
ReplyDeleteFor n=3: 000, 001, 011, 010, 110, 111, 101, 100
For n>3: using the same algorithm: when we finish the previous step, the n+1-th digit can be flip to 1 and then the remaining combinations can be achieved as previously.
Perhaps someone could give a more formal answer.
Nice answer. This is basically Grey code.
ReplyDeleteWe can think of each person as 1 bit that is 0 if the person is outside and 1 if the person is inside. The problem now is how to generate all n bit combinations by modifying just one bit. We use mathematical induction to prove that there is a solution for any arbitrary n number of bits, n>0: Starting with n=1, there is one person, and the solution is obvious. For n=2, we have 00 01 11 10 Assume we have a solution for n=k. For n=k+1, we keep the most significant bit 0 and concatenate the n=k solution, then we change the MSB to 1 and concatenate the n=k solution in reverse order. Example: n=3. We know the n=2 solution (00, 01, 11, 10). We obtain 000, 001, 010, 011 and then 111, 110, 101, 100. By using mathematical induction, it means that we have a solution for any n>0 Thanks to Mihai
ReplyDelete2-bit list: 00, 01, 11, 10
ReplyDeleteReflected: 10, 11, 01, 00
Concatenated: 00, 01, 11, 10, 10, 11, 01, 00
Prefix old entries with 0: 000, 001, 011, 010, 10, 11, 01, 00
Prefix new entries with 1: 000, 001, 011, 010, 110, 111, 101, 100
say we have 2 persons so combination wud be
ReplyDelete00,01,10,11 ..so total number of possible
combination for 2 ppl os 2^2=4
similarly for 2 ppl it wud be 2^3=8
000, 001, 011, 010, 110, 111, 101, 100
so for N ppl total combination is N^2.
But here Q is asking for subsequent steps .1.e
how you wud move ppl in and out...if m not wrong
nice answer
ReplyDelete