What is the least amount of questions to find out the number that a person is thinking between 1 to 1000 when they are allowed to lie at most once

A person is thinking of a number between 1 and 1000. What is the least number of yes/no questions that we can ask and know what that person's number is given that the person is allowed to lie on at most one of her answers.

Solution 1:

This is known as Ulam's problem of searching with lies. For one lie it was first solved by Andrzej Pelc. The minimum number of questions is not hard to calculate but the strategy attaining this number in the worst case takes several pages to describe. Later the solution was simplified.

For $n$ objects with $1$ lie, $n$ even, the number $q$ of questions needed is the smallest solution to $\frac{2^q}{q+1} \geq n$ which is $14$ when $n=1000$. There is a non-adaptive solution using Hamming codes that uses at most one more question than Pelc's method, but can specify all the questions before gameplay begins.

Solution 2:

For distinguishing from $n$ options we need $\lceil \log_2 n \rceil$ bits of information. However, when we allow some bit to be faulty, we get $nk$ possibilities where $k$ is the number of asked questions. Optimally we would have to use at least logarithm of it, so

$$k = \log_2 (n k)$$

which with $n = 1000$ could be solved numerically, with appropriate ceils we get $k = 14$. This is the lower bound, that is, in the worst case we can't get the answer with smaller number of questions (there might be, of course, better lower bounds). To get the upper bound you can apply the coding theory, some sample approaches include "repeat every question 2 times", which will get you something like $2\lceil\log_2 n\rceil+1$ questions ($21$ for $n = 1000$), or search for the faulty place with binary search, arriving at about $\lceil\log_2 n\rceil +\big\lceil\log_2\lceil\log_2 n\rceil\big\rceil+1$ questions ($15$ for $n = 1000$).

I hope this helps ;-)

Edit: Hamming(15,11) code corrects 1 error and achieves even better bound: you would be able to distinguish $2^{11} = 2048$ possibilities. Of course, it also applies in your case.

Solution 3:

Here is a quick proof that it cannot be done in $13$ questions. Suppose there was a strategy that could do this; we may safely assume that $13$ questions are asked in all cases (just fill up with dummy questions if you happen to know the answer earlier). Then after $13$ questions, one will have found out both the number the person was thinking of, and the number of the answer that was a lie (taking $0$ if there was no lie). But the person may start with deciding both on the number and the number of the question that she will lie to. That gives $1000\times14>2^{13}=8192$ possibilities, too much to sort out using $13$ yes/no answers.

By this argument it still remains possible that $14$ questions will do, as $15000<2^{14}=16384$.