Deducing an integer from $0$-$15$ and lying

Question

I'm interested in reducing the upperbound of the number of questions needed and in finding alternate solutions to solve the following question:

Suppose I have thought up an integer between $0$ and $15$ inclusive. Is it possible to deduce the number by asking me seven true or false questions if I may lie on at most one of the questions?

A possible solution (not my own) can be found below:

We work in binary: write the hidden number as $x_1$ $x_2$ $x_3$ $x_4$.

Q$1$: is $x_1 = 0$?

Q$2$: is $x_2 = 0$?

Q$3$: is $x_3 = 0$?

Q$4$: is $x_4 = 0$?

Q$5$: is $x_1 + x_2 = 0$?

Q$6$: is $x_3 + x_4 = 0$?

Q$7$: is $x_2 + x_3 = 0$?

Below, $[\text{Q}i] := 0$ if the answer to question $i$ was yes, and $[\text{Q}i] :=1$ otherwise. We must have exactly one of the following cases:

1. [Q$5$] does not equal $[\text{Q}1] + [\text{Q}2]$. Then exactly one of $\text{Q}1$, $\text{Q}2$, $\text{Q}5$ was not truthfully answered, so the answers to $\text{Q}3$, $\text{Q}4$, $\text{Q}7$ must be truthful, hence $x_3 = [\text{Q}3]$, $x_4 = [\text{Q}4]$, and $x_2 = [\text{Q}7] - [\text{Q}3]$. Depending on whether $[\text{Q}2] = x_2$ we can recover $x_1$. Done.
2. We’re not in case 1, but $[\text{Q}6]$ does not equal $[\text{Q}3] + [\text{Q}4]$. Then exactly one of $\text{Q}3$, $\text{Q}4$, $\text{Q}6$ was not truthfully answered, so the answers to $\text{Q}1$, $\text{Q}2$, $\text{Q}7$ must be truthful, hence $x_1 = [\text{Q}1]$, $x_2 = [\text{Q}2]$, and $x_3 = [\text{Q}7] - [\text{Q}2]$. Depending on whether $[\text{Q}3] = x_3$ we can recover $x_4$. Done.
3. We’re in neither case 1 or case 2. Then $[\text{Q}5] = [\text{Q}1] + [\text{Q}2]$ and $[\text{Q}6] = [\text{Q}3] + [\text{Q}4]$, so there $\text{Q}1$-$\text{Q}4$ must have been truthfully answered. Done! (It does not matter how $\text{Q}7$ was answered in this case.)

PS: Better tags would be appreciated!

Answer 1

This problem is closely related to that of single-error correction on a $4$-bit number. That is, you add some number $e$ of additional bits to the $4$ data bits, for example a fifth bit that is the XOR of the bits $0$ and $1$, a sixth that is the XOR of the bits $2$ and $3$, and a seventh that is the $XOR$ of the previous six. You choose the means of calculating the $e$ extra bits in such a way that any possible seven-bit number formed by accurately calculating the $e$ extra bits (analagous to answering the $e$ questions) and then changing none or precisely one bit in the result, can have been formed by only one combination of the $4$ data bits.

This is a problem which is answered by Hamming codes, which are in the most basic form just ways to choose $2^d$ vertices among the $2^{d+e}$ vertices of a $d+e$-dimensional hypercube, such that no two of the chosen vertices are one or two edges distant from each other. Looking up Hamming single-error-correction codes for $4$ bits of data, we see that $3$ additional bits are required, and one solution is $$e_0 = x_0 \oplus x_2\\ e_1 = x_0 \oplus x_1\\ e_1 = x_0 \oplus x_1 \oplus x_2 \oplus x_3 $$ by the way, the $\oplus$ means addition mod $2$. Your solution also should be using $\oplus$ rather than ordinary $+$ to form the extra questions. The questions generated by this solution are:

• Is $x_0 = 1? \implies $ Is the number $n$ odd?
• Is $x_1 = 1? \implies $ Is $\left \lfloor \frac{n}{2}\right \rfloor$ odd?
• Is $x_2 = 1? \implies $ Is $\left \lfloor \frac{n}{4}\right \rfloor$ odd?
• Is $x_3 = 1? \implies $ Is $n \geq 8$?
• Is $x_0 \oplus x_1 = 1?$
• Is $x_0 \oplus x_2 = 1?$
• Is $x_0 \oplus x_1 \oplus x_2 \oplus x_3 = 1??$

The solution you give replaces the last question with the knowledge of the fifth question to ask about just $x_2 \oplus x_3$.

But this begs a question: Can you get the answer with certainty in seven questions if the only allowed form of the question is "Is $x \geq k$" for some sequence of $k$'s (which of course may depend on the answers to previous questions)?

Answer 2

It is not possible with six or fewer questions.

Your integer can take one of $16$ values. For each value, there are $7$ possible sets of responses, which makes $112$ possible responses in total.

But after asking just six questions, I have at most $2^6=64$ possible sets of responses. This is less than $112$, so in general I don't have enough information to deduce the integer.