wu :: forums
« wu :: forums - People Combinations Room - Easy Answer? »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 12:56am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Grimbal, william wu, SMQ, ThudnBlunder, Eigenray, Icarus, towr)
   People Combinations Room - Easy Answer?
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: People Combinations Room - Easy Answer?  (Read 3427 times)
Nicodemus
Guest

Email

People Combinations Room - Easy Answer?  
« on: Jul 29th, 2002, 2:42pm »
Quote Quote Modify Modify Remove Remove

Use Gray Code.
 
This one seems just way too easy... Am I missing something?
 
IP Logged
-D-
Guest

Email

Re: People Combinations Room - Easy Answer?  
« Reply #1 on: Jul 29th, 2002, 2:48pm »
Quote Quote Modify Modify Remove Remove

this problem is that easy Smiley  
 
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-
IP Logged
Nicodemus
Guest

Email

Re: People Combinations Room - Easy Answer?  
« Reply #2 on: Jul 29th, 2002, 3:04pm »
Quote Quote Modify Modify Remove Remove

Fair point, D. It's only easy for those of us who suffered through boring CS discrete math courses. Wink
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: People Combinations Room - Easy Answer?  
« Reply #3 on: Aug 1st, 2002, 7:34am »
Quote Quote Modify Modify

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.
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
-D-
Guest

Email

Re: People Combinations Room - Easy Answer?  
« Reply #4 on: Aug 1st, 2002, 1:10pm »
Quote Quote Modify Modify Remove Remove

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, 2n 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-
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: People Combinations Room - Easy Answer?  
« Reply #5 on: Aug 12th, 2002, 7:34pm »
Quote Quote Modify Modify

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.
IP Logged
snags697
Newbie
*




Mad Physicist

   


Gender: male
Posts: 14
Re: People Combinations Room - Easy Answer?  
« Reply #6 on: Aug 13th, 2002, 7:53am »
Quote Quote Modify Modify

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!
IP Logged
KPlo
Guest

Email

Re: People Combinations Room - Easy Answer?  
« Reply #7 on: Aug 16th, 2002, 12:30pm »
Quote Quote Modify Modify Remove Remove

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.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: People Combinations Room - Easy Answer?  
« Reply #8 on: Aug 29th, 2002, 5:18am »
Quote Quote Modify Modify

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.
« Last Edit: Aug 29th, 2002, 5:25am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board