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?



Guess a number with at most one wrong answer
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$.


