Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ).

**Game** : 

 1. $A$ chooses an element in {1,2....,n}
 
 2. $B$ tries to guess this number by asking Yes/No
questions.



Binary search is a way to solve the problem, so with $\log n$ many queries will be sufficient to solve the problem when player $A$ does not lie. But if player $A$ lie exactly one time than we can problem with $2\log n$ many queries (by just asking the same query two times). There is an optimal way to solve this problem with $ \log n + \log \log n +c$ , where $c$ is a constant. We will first ask $\log n $ many queries to $B$ and going to get a $\log n $ bits long binary string and now apply binary search on this binary string. In **general** when A is allowed to lie say $l$ then also the number of queries need to solved the problem is $ \log n + \log\log n + c $


**Questions** : 1) How to prove that $ \log n + \log\log n + c$ is a **lower bound** ?

2) If only $\log n$ many queries are allowed in the general case Is there an approximation algorithm for this game ( original solution = $a$ * algorithm's solution, where $a$ is constant).

3) If $l$ is very large (say order of $n$) Is it possible in that case to correctly find out the guessed number ? I try to use Hamming distance but not able to come up with a precise answer.

**Reference** :http://ac.els-cdn.com/S0304397503005814/1-s2.0-S0304397503005814-main.pdf?_tid=a880fa14-f82d-11e6-81df-00000aacb35e&acdnat=1487678746_7307f01621c154d9f6e006fc8b992ad0