Author |
Topic: Seven boolean questions (Read 2870 times) |
|
daniel
Guest
|
Does anybody knows the questions to seek out the number $n \in [0,15]$ ?
I need help..
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Seven boolean questions
« Reply #1 on: May 23rd, 2005, 7:33am » |
 Quote  Modify
|
I don't understand the problem you want an answer to..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Seven boolean questions
« Reply #2 on: May 23rd, 2005, 7:52am » |
Quote Modify
|
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?"
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Seven boolean questions
« Reply #4 on: May 23rd, 2005, 8:43am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Seven boolean questions
« Reply #5 on: May 23rd, 2005, 9:12am » |
Quote Modify
|
| hidden: |
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?
|
|
|
IP Logged |
|
|
|
River Phoenix
Guest
|
|
Re: Seven boolean questions
« Reply #6 on: May 23rd, 2005, 10:10am » |
Quote Modify
 Remove
|
This question was on the AIME some years ago 
I remember taking the test; the problem is somehow equivalent to the finding of a 7x15 matrix with boolean values, I think
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Seven boolean questions
« Reply #7 on: May 23rd, 2005, 10:18am » |
Quote Modify
|
| hidden: |
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).
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print