Guess a number with at most one wrong answer

Question

Consider a game where one player picks an integer number between 1 and 1000 and other has to guess it asking yes/no questions.

If the second player always gives correct answers than it's clear that in worst case it's enought to ask 10 questions. And 10 is the smallest such number.

What if the second player is allowed to give wrong answers? I'm interested in a case when the second player is allowed to give at most one wrong answer.

I know the strategy with 15 guesses in worst case. Consider a number in range [1..1000] as 10 bits. At first you ask the values of all 10 bits ("Is it true that $i$-th bit is zero?"). After that you get some number. Ask if this number is the number first player guessed. And if not you have to find where he gave wrong answer. There are 11 positions. Using the similar argument you can do it in 4 questions.

Is it possible to ask less then 15 questions in worst case?

Answer 1

Yes, there is a way to guess a number asking 14 questions in worst case. To do it you need a linear code with length 14, dimension 10 and distance at least 3. One such code can be built based on Hamming code (see http://en.wikipedia.org/wiki/Hamming_code).

Here is the strategy.

Let us denote bits of first player's number as $a_i$, $i \in [1..10]$. We start with asking values of all those bits. That is we ask the following questions: "is it true that i-th bit of your number is zero?" Let us denote answers on those questions as $b_i$, $i \in [1..10]$.

Now we ask 4 additional questions:

Is it true that $a_{1} \otimes a_{2} \otimes a_{4} \otimes a_{5} \otimes a_{7} \otimes a_{9}$ is equal to zero? ($\otimes$ is sumation modulo $2$).

Is it true that $a_{1} \otimes a_{3} \otimes a_{4} \otimes a_{6} \otimes a_{7} \otimes a_{10}$ is equal to zero?

Is it true that $a_{2} \otimes a_{3} \otimes a_{4} \otimes a_{8} \otimes a_{9} \otimes a_{10}$ is equal to zero?

Is it true that $a_{5} \otimes a_{6} \otimes a_{7} \otimes a_{8} \otimes a_{9} \otimes a_{10}$ is equal to zero?

Let $q_1$, $q_2$, $q_3$ and $q_4$ be answers on those additional questions. Now second player calculates $t_{i}$ ($i \in [1..4]$) --- answers on those questions based on bits $b_j$ which he previously got from first player.

Now there are 16 ways how bits $q_i$ can differ from $t_i$. Let $d_i = q_i \otimes t_i$ (hence $d_i = 1$ iff $q_i \ne t_i$).

Let us make table of all possible errors and corresponding values of $d_i$:
position of error -> $(d_1, d_2, d_3, d_4)$

no error -> (0, 0, 0, 0)
error in $b_1$ -> (1, 1, 0, 0)
error in $b_2$ -> (1, 0, 1, 0)
error in $b_3$ -> (0, 1, 1, 0)
error in $b_4$ -> (1, 1, 1, 0)
error in $b_5$ -> (1, 0, 0, 1)
error in $b_6$ -> (0, 1, 0, 1)
error in $b_7$ -> (1, 1, 0, 1)
error in $b_8$ -> (0, 0, 1, 1)
error in $b_9$ -> (1, 0, 1, 1)
error in $b_{10}$ -> (0, 1, 1, 1)
error in $q_1$ -> (1, 0, 0, 0)
error in $q_2$ -> (0, 1, 0, 0)
error in $q_3$ -> (0, 0, 1, 0)
error in $q_4$ -> (0, 0, 0, 1)

All the values of $(d_1, d_2, d_3, d_4)$ are different. Hence we can find where were an error and hence find all $a_i$.

Answer 2

BTW, this problem is known as the Ulam(-Renyi) liar problem or Ulam's searching game (or just "playing Twenty Questions with a liar"), and has an extensive literature. The following is a survey as of 2002:

• Andrzej Pelc, Searching games with errors--fifty years of coping with liars, Theoretical Computer Science, Volume 270 (2002), pp. 71-109

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2^q/(q+1), which for n=1000 is indeed 14. There are alternative solutions to the one-lie game in more recent papers like this and this. As observed by Peter Shor in a comment above, the general adaptive strategy when multiple lies are allowed does not look like Hamming codes.

---

Edit: Since this has been bumped up, I may as well mention a nice result in the more general setting, proved by Joel Spencer and Peter Winkler in their paper Three Thresholds for a Liar.

It is traditional to name the two players Paul and Carole, where Paul (named after Paul Erdős) is the one who asks the questions, and Carole (an anagram of oracle) is the one who answers them. Paul asks $q$ questions in all, and Carole is allowed to lie a fraction $r$ of the time. We will consider three progressively harder (for Paul) versions of what this means. In Version A, Carole is allowed to lie at most $\lfloor ri\rfloor$ times to the first $i$ questions, for all $i$. In Version B, Carole is only required to lie at most $\lfloor rq \rfloor$ times in total — she can choose to exhaust all her lies at the beginning, for instance. In Version C (nonadaptive), Paul must ask all his questions in one batch, and Carole can choose up to $\lfloor rq \rfloor$ ones to lie to.

Note that if no lies are allowed ($r = 0$), the number of questions needed is exactly $\lceil \log_2 n\rceil$, and that, intuitively, if $r$ is too large, Paul cannot guess correctly at all. Specifically, they show that:

• In version A, Paul wins with $\Theta(\log n)$ questions if $r < 1/2$, but Carole wins if $r \ge 1/2$.
• In version B, Paul wins with $\Theta(\log n)$ questions if $r < 1/3$, but Carole wins if $r \ge 1/3$.
• In version C, Paul wins with $\Theta(\log n)$ questions if $r < 1/4$, Carole wins if $r > 1/4$, and if $r = 1/4$, Paul wins but needs $\Theta(n)$ questions.

Answer 3

I wrote an expository paper on this kind of problem, http://www.austms.org.au/Publ/Gazette/2009/May09/TechPaperMeyerson.pdf

Answer 4

The other answers are truly excellent and have settled the intended question. For a bit of fun, however, allow me to mention the following paradoxical solution.

Namely, with a certain precise and reasonable understanding of the rules of your game, which I shall presently give, I claim that no additional questions are required for the lie-telling game over the truth-telling game. In particular, in your case 10 questions still suffice!

Specifically, to be a bit more definite about what it means to give a wrong answer, I propose that the rules should allow that the second player, at most once during the game, decides that a given round will be a lie-telling round, for which he will privately ponder the correct truthful answer, but then give as his answer precisely the opposite of the correct answer. So if a truthful answer would have been Yes, then on this lie-telling round he says No, and conversely. (In particular, in this version of the game, the wrong answer is not a random answer in any sense, although it could be that the choice of which round is to be a lie-telling round is determined randomly.) On the other rounds, he tells the truth. Secondly, I note that you didn't insist that the questions of player 1 must have a particular form.

With these rules for the liar game, I claim that no additional questions over the fully truthful case are required to determine the secret number.

The reason is a simple logic trick: if in the fully truthful game, one would want on a round to ask a question $Q$, then in this liar game, one should instead ask the question $P$:

• If I were to have asked $Q$ on this round, would you have said Yes?

Consider how the second player will react. First, if he is on a truth-telling round, then he will give the same answer to this question that he would have given to $Q$. If in contrast he is on a lie-telling round, then he ponders question $P$, and considers that if the first player had asked $Q$ on this round and a truthful answer had been Yes, then he would have said No, since this is a lie-telling round, and so a truthful answer to $P$ is No, but since it is a lie-telling round, he answers Yes to $P$. Similarly, if a truthful answer to $Q$ would have been No, then a lie-telling answer to $Q$ would be Yes, and so a truthful answer to $P$ would be Yes, but since it is a lie-telling round, he answers No. Thus, because of the double-negation effect, the lie-telling answer to $P$ is the same as the truth-telling answer to $Q$.

Therefore, the first player can in effect gain exactly the same information from the second player in the liar game that he can in the fully truth-telling game.

The same argument shows that, in fact, it doesn't matter how often the second player decides to lie, as long as he lies by stating each time the exact opposite of a truthful answer. Indeed, the second player could randomly decide for each round whether he will lie or tell the truth on that round, but the double-negation trick of question $P$ allows the first player nevertheless to gain exactly the same information, and so no additional questions beyond the truth-telling case are required, even if the second player decides randomly at the beginning of every round whether to lie or tell the truth on that round.

Ha!

Answer 5

Some more references.

Joel Spencer's web page has several downloadable papers on searching with lies:

http://cs.nyu.edu/spencer/papers/papers.html

Ivan Niven, "Coding Theory applied to a Problem of Ulam", http://www.jstor.org/pss/2689543 , gives the Hamming code approach.

Andrszej Pelc, who solved the original Ulam liar problem with $n=10^6$ and one optional lie, also has a number of papers on extensions of the problem to more lies and to other models of searching with noisy queries: http://w3.uqo.ca/pelc/search.html