Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
4  
What if the person lies when you go for the number on Question 11? –  Bruce Westbury Jul 17 '10 at 8:02
    
This is a standard ECC (en.wikipedia.org/wiki/Error-correcting_code) problem. –  BlueRaja Jul 18 '10 at 7:22
    
BlueRaja -- no, it's not: see Peter Shor's comment to falagar's answer. –  JBL Jul 18 '10 at 14:37
    
You can see the difference between adaptive and non-adaptive (i.e. ECC's) in shreevatsa's answer below. –  Peter Shor Jul 18 '10 at 18:43
add comment

5 Answers

up vote 24 down vote accepted

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

share|improve this answer
2  
+1- This is really clever! –  Dylan Wilson Jul 17 '10 at 8:32
5  
This is a non-adaptive strategy (meaning the questions don't depend on previous answers. For one lie, I think non-adaptive and adaptive strategies give the same answer, but this is no longer the case for more than one lie. See the survey article by Pelc referenced in another answer. –  Peter Shor Jul 17 '10 at 14:47
    
@Peter Though this comment is a bit late, what you write is not entirely true. For one lie the strategies give the same answer IF the size of the set is such that you can "build" a Hamming-code on it. Otherwise, they can differ, see Pelc 3.1.1. Fully adaptive search. –  domotorp yesterday
add comment

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 ≤ 2q/(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.
share|improve this answer
add comment

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

share|improve this answer
    
Gerry, this discloses the info about yourself! I would be happy to add +1 more for your openness. –  Wadim Zudilin Jul 17 '10 at 14:32
7  
Wadim, considering the subject of this thread, it is of course possible that in alleging that I wrote the paper, I have given my one wrong answer! –  Gerry Myerson Jul 18 '10 at 7:40
add comment

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!

share|improve this answer
    
One could alternatively use the question: Does $Q$ hold if and only if this is a truth-telling round? –  Joel David Hamkins Jul 18 '10 at 3:01
    
Nice trick. :-) The standard formulation of the game avoids this possibility (so that lies do matter) by requiring that questions must be of the form "Does the number lie in set A?" for some $A \subseteq [n]$. –  shreevatsa Jul 18 '10 at 4:08
    
Shreevatsa, in that case, I would make `A_P=\{\,n\,|\,n\in A_Q\iff\text{this is truth-telling round }\}$'. –  Joel David Hamkins Jul 18 '10 at 11:35
    
Yeah, you're right; ignore my previous comment. It has nothing to do with the form of the question; it's rather that the notion of a "lie-telling round" which forces Carole to commit to being a "liar" even internally is too restrictive and self-referential (like the "one who always lies" logic puzzles). To lie here is to give an answer other than the truth, and your restriction on the round effectively takes away that option... I guess the original questioner's statement of "at most one wrong answer" is better after all. :-) –  shreevatsa Jul 18 '10 at 19:54
1  
Shreevatsa, you could say that player 1 must list the elements of $A$ explicitly, since my description of $A$ is a set that only player 2 can compute, and then your remark would regain its effect. –  Joel David Hamkins Jul 19 '10 at 1:21
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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