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 :
$A$ chooses an element in {1,2....,n}
$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$ (constant) 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 ?
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).
If $l$ is very large (say order of $n$) Is it possible in that case to correctly find out the guessed number ? I trytried to use Hammingthe Hamming distance but not able to come up with a precise answer.