wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> People Combinations Room - Easy Answer?
        
(Message started by: Nicodemus on Jul 29^th, 2002, 2:42pm)

Title: People Combinations Room - Easy Answer?
Post by Nicodemus on Jul 29^th, 2002, 2:42pm

Use Gray Code.

This one seems just way too easy... Am I missing something?

Title: Re: People Combinations Room - Easy Answer?
Post by -D- on Jul 29^th, 2002, 2:48pm

this problem is that easy :)

But notice it isn't listed as a CS problem, even some of the best logical thinkers don't know what gray code is.

Really though, even those of us who know what gray code is, can't count in it beyond 2 or 3 bits. The logic behind determining what bit to change next is pretty intense.
-D-

Title: Re: People Combinations Room - Easy Answer?
Post by Nicodemus on Jul 29^th, 2002, 3:04pm

Fair point, D. It's only easy for those of us who suffered through boring CS discrete math courses. ;)

Title: Re: People Combinations Room - Easy Answer?
Post by Eric Yeh on Aug 1^st, 2002, 7:34am

Actually guys, I'd neevr heard of this gray code before but it is still simple -- pf by induction. So I don't think it's just a CS thing.

Title: Re: People Combinations Room - Easy Answer?
Post by -D- on Aug 1^st, 2002, 1:10pm

Graycode is a counting method that satisfies the conditions that a number 'k' and it's adjacent values 'k-1' or 'k+1' differ from k by only 1 bit. Examples are:

00, 01, 11, 10
000, 001, 011, 010, 110, 111, 101, 100

For an 'n' bit field, 2ⁿ possible values still exist, therefore every possible bit combination has been excercised. Gray-code is especially useful in hardware logic design of state machines and counters. When you limit changes between states to only one bit, it significantly lowers the chance for bit errors in your logic, race conditions, and intermediate incorrect results.

As far as this problem goes the solution is very easy, you can just take a very long time putting people into the room and out of the room to make every combination. The worst case would be to identify all combinations, put one combination in the room, remove all the people, put another combination in the room, repeat.

Graycode is just an efficient way of doing it.
-D-

Title: Re: People Combinations Room - Easy Answer?
Post by AlexH on Aug 12^th, 2002, 7:34pm

Gray code certainly works and Eric is right its an easy proof without it. Note that you can do it for 1 person. Assume you can do it for n, then do n+1 by doing the solution for n, adding the n+1st person, then doing the n solution in reverse (this is how to make a Gray code).

D's "easy" solution doesn't work because as you're adding/subtracting to get into a combination you'll be passing through other combinations and the problem specifies you may only hit each combination once.

Title: Re: People Combinations Room - Easy Answer?
Post by snags697 on Aug 13^th, 2002, 7:53am

I once had a mechanical puzzle that forced the player to count out part of an 8-bit gray code, though I didn't know it at the time. The puzzle was round with 8 vertical sliding posts sticking out the top. Each post could slide in our out, but only if the other posts were in the right positions. I thought of each post as a bit, with the "in" position being 0 and the "out" position being "1". The criterion for being able to move a particular bit was that the next lower bit had to be 1, while all lower bits were 0. This combination (1000...) is the end of the lower-level gray code that AlexH had mentioned.

At any given time, two bits could possibly be changed. One would take you forward in the sequence, and one would take you back. So, you just had to remember where you came from and move the other post that could move. As I did the puzzle, the least significant bit (LSB) would have to be moved every other turn. Then the next bit would go every other remaining turn, etc. Once I figured out this pattern, it got pretty quick.

The only hitch was that when you got to all 1's, you were done. In trying to restore the 0's, there were 2 possible ways to go. One would leave you with all 0's, which is what you wanted. The other would finish the gray code and leave you with 10000000.

Figuring out which bit to change without "remembering" what you had just done would be much more difficult, but there's a trick. Since at each step in the sequence you change one bit, at each step the parity (whether you have an odd or even number of 1's) changes. Every other step you want to change the LSB. Every other step the parity is even. So, check the parity. If it's even, change the LSB. If it's odd, change the "other" available bit to be changed (based on the 100... criterion). For example, if you're at:
01101000, this is odd parity. The next in the sequence is therefore
01111000.
Going backwards, just reverse the parity rule. That's it.

In addition to the reasons -D- gave, gray codes are important in any system where it takes energy or effort to change a bit. Unfortunately, if the bits "wear out", the LSB will be affected first. In the riddle, one person is going to get motion sickness stepping in and out of the room 2^n times!

Title: Re: People Combinations Room - Easy Answer?
Post by KPlo on Aug 16^th, 2002, 12:30pm

You can also think of the problem as visiting all of the corners of an n-dimensional cube (where n is the number of people) once each by traversing edges of the cube.

For any graph theory fans out there, that amounts to finding a Hamiltonian path on an n-cube.
The inductive methods mentioned above work for this as well.

Title: Re: People Combinations Room - Easy Answer?
Post by James Fingas on Aug 29^th, 2002, 5:18am

Guys, grey code isn't as hard to count out as you make it out to be. The bits you flip follow a very easy to see pattern. On the first move, you flip bit 1, on the second you flip bit 2, on the third, you flip bit 1, on the fourth, you flip bit 3, on the fifth move, you flip bit 1.

Take a look at the ticks on an inch ruler.

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 . . .

Another way of looking at it (this is based in that puzzle that snags697 is talking about). You can always change bit 1, but the only other bit you can change is the next bit after the first "set" bit.

01100010 you can set either the first bit, or the third
------|-| (The vertical bars are pointing out which bits you can change)

01111001 you can set the second bit or clear the first
-------||

11000000 you can clear the 8th bit or set the first
|-------|

As you can see, there are two possibilites. One of these will count up, and the other will count down. How do you know which is which? If there's an even number of bits set, then setting bit 1 will count up (and clearing it will count down). For an odd number of bits set, the opposite is true.