14
$\begingroup$

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?)

$\endgroup$
5
  • 2
    $\begingroup$ Must the questions be independent, or dependent on one another? $\endgroup$
    – Cloudy7
    Apr 17 '20 at 3:38
  • $\begingroup$ It should be independent $\endgroup$
    – YooN
    Apr 17 '20 at 3:40
  • 19
    $\begingroup$ You should give more details on what kind of questions we can ask, and what kind of answer the answerer can give. For example, is it a yes/no question? Or is it we give a number then the answerer give "larger, equal, or smaller"? $\endgroup$
    – justhalf
    Apr 17 '20 at 7:20
  • 34
    $\begingroup$ For example, I can just ask "What is the number?" 3 times in a row, and the answer that is repeated is the right answer. $\endgroup$
    – Spencer
    Apr 17 '20 at 17:08
  • 1
    $\begingroup$ or just say "is the number 1,2,3,4,5,6,7... or 16?" and ask "are you lying?" and ask it again... and you'll get the right answer $\endgroup$ Apr 20 '20 at 7:54
69
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

  1. Is the number 8-15?
  2. Is the number 4-7 or 12-15?
  3. Is the number 2-3 or 6-7 or 10-11 or 14-15?
  4. Is the number odd?

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:

  1. Did you answer "yes" to an odd number of: Q1, Q2, and Q4?
  2. Did you answer "yes" to an odd number of: Q1, Q3, and Q4?
  3. Did you answer "yes" to an odd number of: Q2, Q3, and Q4?

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:

  1. If Q1 was the lie, then Q5 and Q6 will be inconsistent (with Q1-4)
  2. If Q2 was the lie, then Q5 and Q7 will be inconsistent
  3. If Q3 was the lie, then Q6 and Q7 will be inconsistent
  4. If Q4 was the lie, then Q5, Q6, and Q7 will be inconsistent
  5. If Q5-7 was the lie, then only that single question itself will be inconsistent
  6. If there was no lie, everything is consistent

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).

$\endgroup$
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yeah, that was my thought too $\endgroup$
    – Kevin
    Apr 20 '20 at 4:34
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I don't think this works as a solution. If they say yes then they haven't exactly lied, they've said a statement of indeterminate truthiness (a paradoxical statement along the lines of "this statement is false") $\endgroup$
    – JDL
    Apr 20 '20 at 7:58
  • $\begingroup$ It seems to me that the "no" answer doesn't use up their lie. Since the two parts of your question are joined by an "and", it is truthful to answer "no" when only the second half is false, i.e., they could still be reserving the right to lie in the future while truthfully answering this question. (IMO there is no paradox either: a person can truthfully say that they sometimes lie – this is not equivalent to saying that they are lying now.) $\endgroup$
    – Arkku
    Apr 20 '20 at 11:40
  • $\begingroup$ @Arkku Edited the question asked so it's more logically sound. $\endgroup$
    – Paul Evans
    Apr 20 '20 at 13:52
  • $\begingroup$ Currently the question you are asking seems to be incorrect: everyone can truthfully answer "no" to that question (because no-one will always, or indeed ever, say "yes" when asked "are you answering falsely"). The explanation for the "no" answer seems to indicate that you meant to ask something like "will you lie when answering this or any of my following questions?" in which case a "no" would lead to two lies if they were to lie to a following question, but a truthful "yes" allows them to lie to any other question. $\endgroup$
    – Arkku
    Apr 20 '20 at 14:05
  • $\begingroup$ (It seems that you may be trying to apply the classic knights and knaves "If I were to ask you 'do you always tell the truth'" solution, but it can't work since they are never forced to lie and can truthfully answer "no, I don't always tell the truth" without a paradox. Or simply choose to say "yes, I would tell the truth if you were to ask me that question" while still being able to lie to a different question.) $\endgroup$
    – Arkku
    Apr 20 '20 at 14:11
2
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ This doesn't work. If you ask a question "Is X true AND is Y true?", then the correct answer is "Yes" if and only if both X and Y are true. Hence one may just answer your first question without lying and then answer "no" to your second question, which is also not lying. $\endgroup$
    – WhatsUp
    Apr 18 '20 at 20:04
  • 1
    $\begingroup$ You are right @WhatsUp . You found a fatal flaw. $\endgroup$
    – tyobrien
    Apr 18 '20 at 20:44
0
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.