riddle of the day

Sixteen possibilities and one answer that may be false. All questions must be fixed before the game begins.

Sixteen Numbers and One Lie

Genius
Pure logic

Riddle statement

I am thinking of an integer between 1 and 16.

You may ask any questions whose answers are yes or no, with one condition: every question must be prepared before you receive the first answer. You may not change them afterwards.

I will answer every question, but I may lie at most once during the conversation. I may also tell the truth every time.

What is the smallest number of questions that guarantees you can determine the number?

Show solution

Solution

Answer: exactly 7 questions are required.

Why six are not enough

Suppose we ask \(q\) questions. Every number has a sequence of \(q\) truthful answers.

Because one lie is allowed, that number may produce \(q+1\) different received sequences:

  • the truthful sequence;
  • one for each possible altered answer.

Sequences belonging to different numbers must not overlap, or the chosen number could not be identified.

With six questions, we would need

$ 16(6+1)=112 $

different sequences, but only

$ 2^6=64 $

exist.

Thus six questions, and therefore any smaller number, cannot suffice.

How seven questions work

Write the chosen number minus one in binary using four bits:

$ n-1=abcd, $

where \(a\) is the most significant bit.

Let \(\oplus\) denote addition modulo 2: it equals 1 when an odd number of its inputs are 1.

Prepare these seven truthful answers:

$ \begin{aligned} c_1&=a\oplus b\oplus d, & c_2&=a\oplus c\oplus d, & c_3&=a,\\ c_4&=b\oplus c\oplus d, & c_5&=b, & c_6&=c, & c_7&=d. \end{aligned} $

Question \(i\) is simply:

Is \(c_i=1\)?

After receiving \(r_1,\ldots,r_7\), calculate:

$ \begin{aligned} s_1&=r_1\oplus r_3\oplus r_5\oplus r_7,\\ s_2&=r_2\oplus r_3\oplus r_6\oplus r_7,\\ s_3&=r_4\oplus r_5\oplus r_6\oplus r_7. \end{aligned} $

If every answer was truthful, all three parities are zero.

If one answer was false, the number

$ j=s_1+2s_2+4s_3 $

gives its exact position from 1 to 7. Correct \(r_j\), then recover:

$ a=r_3,\qquad b=r_5,\qquad c=r_6,\qquad d=r_7. $

Those four bits determine \(n-1\), and hence the chosen number.

Therefore seven questions suffice while six do not:

$ \boxed{7}. $

The fit is perfect:

$ 16(7+1)=128=2^7. $

Each of the 16 numbers occupies exactly eight possible received sequences: the truthful one and the seven containing one lie.

Key idea: the three parity checks do more than detect a false answer; they identify exactly which answer must be corrected.