How to guess a number between 1~16 in 7 attempts?
The person who answers the question CAN either lie once or never.
Can you make the proper 7 questions to guess what number between 1–16 will be, and when does the person lie? (Or find out that there wasn't any lie?)
To do this, we could use
the "Hamming(7,4)" code, a way of using 7 bits to transfer a 4-bit number and correct up to one error.
Just take the below table:
1 0000000
2 1110000
3 1001100
4 0111100
5 0101010
6 1011010
7 1100110
8 0010110
9 1101001
10 0011001
11 0100101
12 1010101
13 1000011
14 0110011
15 0001111
16 1111111
and make your questions "Is the first bit in this number's entry 1? Is the second bit in this number's entry 1?", and so on. (If you don't want to reference a table, you can always just list numbers explicitly: your first question might be "Is the number 2, 3, 6, 7, 9, 12, 13, or 16?".)
This table has the special property that any two rows differ by at least three bit-flips. So if you only have one lie, you can't have two possible secret numbers: there will be only one way to flip a bit and get to a row in the table.
This will be equivalent to the other answer, but shows how to construct it. For convenience, I will treat the question as "guess a number between 0 and 15", just add 1 to all numbers in questions.
The Hamming code can also be considered to work for a world where a honest person wants to send us a 4-bit number using 7 bits, but the evil messenger (channel) may choose to flip at most one.
First, ask 4 questions which, without lying, would pinpoint which number it is, using the usual binary expansion.
This is equivalent to sending the 4-bit number itself without modification.
Let [Q1] be 1 if they said yes, 0 if they said no to the first question. At this point, without any lie, we know which number it is by reading off the binary number [Q1][Q2][Q3][Q4].
We can do some fancy footwork to double-check for lies:
Note that this is basically asking "did you lie on Q1 or Q2 or Q4", etc.
In other words, also send a specific parity check on (Q1,Q2,Q4), (Q1,Q3,Q4), and (Q2,Q3,Q4).
Now, using these answers, we can exactly pinpoint which of the 7 questions, if any, were lied to:
Exactly one of the 8 cases for consistency of Q5-7 must occur, so we can correct for the lie by flipping the bit corresponding to Q1-4 (if lied to), then reading off the corrected binary number.
This constructs the error syndrome, which is used for decoding, that is, error-correction. In the general formulation of the $(2^{2^n}+2^n-1,2^n)$-Hamming code, the $n$ parity bits are placed at positions $2^k$ (so Q5 is shifted to Q1, Q6 is Q2, Q7 is Q4).
The real easy answer given the criteria:
Ask them what the number is three times. They can lie at most one time, so they will tell you the correct number at least two of those times :).
I assume the author intended to restrict the answers to questions with 'yes' or 'No' answers though, or to groups of numbers...
To extend on tyobrien's idea you ask the following question:
If I asked you, "are you answering this question falsely" would you always say yes?
Then if the say yes:
they have used their lie up admitting they've lied on this question.
and if they say no:
they've also used their lie by saying they'd never lie which is a lie.
So:
you now have 6 questions that must be answered truthfully to find the 4 bit number so proceed as usual in a binary search: is it less than 8? etc.
There is a way to do it in 6 questions. This way forces the answerer to lie within the first 2 questions without confronting the answerer with paradoxes or posing questions about future answers.
1. Ask a completely random question.
2. "Was the previous answer a lie AND does 1=1?"
3. "Is the first bit on the right of the number's binary representation a 1?"
4. "Is the 2nd-to-right bit of the number's binary representation a 1?"
5. "Is the 3rd-to-right bit of the number's binary representation a 1?"
6. "Is the 4th-to-right bit of the number's binary representation a 1?"
If the answer to question 2 is "yes", then either the first answer is a lie or the second answer is a lie. If the first answer was a lie, the answerer can't lie about that part saying "no", because this would be his second lie. The answerer also can't say "no" and be telling the whole truth because obviously 1=1. Therefore any answer either incriminates or forces a lie.
Once we know he has lied we can ask the next four questions about the binary representation to find the answer.
First I am going to separate the numbers into two groups. The first group has numbers from 1 to 8 and the second group has numbers from 9 to 16. My first question is ″ Does your number belong to group 1 or 2?″ If the answer is ″group 1″, then I will ask if the number is odd or even. If he says it is odd, then I know he lies because I have to ask 3 more questions to find the chosen number. So in total I asked 5 questions instead of 7. The alternative is that he tells me group 1 and won't say whether the number is even or odd, saying he will only answer for one number at a time: is it 1, is it 2, is it 3...? Then I have to ask 7 questions to find the chosen number. So in all I asked 7+1=8 questions. In both cases the man is lying.
