wu :: forums - Print Page


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

        riddles >> hard >> Seven boolean questions
        
(Message started by: daniel on May 23^rd, 2005, 4:10am)

Title: Seven boolean questions
Post by daniel on May 23^rd, 2005, 4:10am

Does anybody knows the questions to seek out the number $n \in [0,15]$ ?

I need help..

Title: Re: Seven boolean questions
Post by towr on May 23^rd, 2005, 7:33am

I don't understand the problem you want an answer to..

Title: Re: Seven boolean questions
Post by Deedlit on May 23^rd, 2005, 7:52am

If the question is how to identify a number from 0 to 15 in the fewest number of yes/no questions, that's easy: any number from 0 to 15 is representable by a four-bit string, so the questions are, "what is the first/second/third/fourth bit?"

Title: Re: Seven boolean questions
Post by daniel on May 23^rd, 2005, 7:59am

Sorry, I mean the answer to the riddle about seven question to ask to seek out a number between 0 and 15 if at most one answer coud be wrong:

http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#7booleanQuestions ::)

Title: Re: Seven boolean questions
Post by towr on May 23^rd, 2005, 8:43am

I think some sort of error encoding is in order.
Maybe a parity check.

So you would indeed ask for the 4 bits, but also three redundancy bits, which you can use to remove an error, if there is (at most) one (like the puzzle states).

I can't quite remember how it works though.

Title: Re: Seven boolean questions
Post by Deedlit on May 23^rd, 2005, 9:12am

[hideb]
The three extra bits have to determine which of the eight possible responses are given (each question can be answered wrong, or all seven can be correct.). Number the possible responses 1-7 for answering 1-7 wrong, and 8 for answering them all correctly. Assume for the moment that the first four questions are all answered correctly, and see what that says about questions 5-7. For responses 5-8, the "apparent" correctness of questions 5-7 is:

5: FTT
6: TFT
7: TTF
8: TTT

so we want an incorrect answer for questions 1-4 to correspond to having questions 5-7 appear to have at least two wrong answers. We can choose this arbitrarily:

1: FFT
2: FTF
3: TFF
4: FFF

and questions 5-7 could be:

5: is the sum of bits 1,2, and 4 even?
6: is the sum of bits 1,3, and 4 even?
7: is the sum of bits 2,3, and 4 even?

[/hideb]

Title: Re: Seven boolean questions
Post by River Phoenix on May 23^rd, 2005, 10:10am

This question was on the AIME some years ago :P
I remember taking the test; the problem is somehow equivalent to the finding of a 7x15 matrix with boolean values, I think

Title: Re: Seven boolean questions
Post by towr on May 23^rd, 2005, 10:18am

[hideb]
If you use Deedlit's method and rearrange the answers of the questions to

5 6 1 7 2 3 4

then
[5]^[1]^[2]^[4]*1+
[6]^[1]^[3]^[4]*2+
[7]^[2]^[3]^[4]*4
gives the position of the answer that was a lie.
(Where [x] is 1 is the answer to question x was 'yes', and 0 if it was 'no'. And ^ is XOR)
If it's zero all answers were true.

This is also known as the Hamming code (link (http://en.wikipedia.org/wiki/Hamming_code)).
[/hideb]