4
$\begingroup$

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$ (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 ?

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 tried to use the 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

$\endgroup$
  • 2
    $\begingroup$ You are asking many questions. The usual rule is one question per post. For your third question, see this paper: cs.bu.edu/~gacs/papers/liars.pdf. $\endgroup$ – Yuval Filmus Feb 21 '17 at 15:03
  • $\begingroup$ For your second question, let $\log n = \log m + \log\log m + c$. Can you use this idea to solve your second question, by partitioning $\{1,\ldots,n\}$ into $m$ intervals in a smart way? $\endgroup$ – Yuval Filmus Feb 21 '17 at 15:05
  • $\begingroup$ @ Yuval Filmus for second question if the size of the each interval is constant then I can have a constant approximation factor otherwise I am not able to see it. $\endgroup$ – aaag Feb 21 '17 at 15:22
  • $\begingroup$ You can do better by varying the size of the intervals. In particular, intervals corresponding to smaller numbers should be shorter. $\endgroup$ – Yuval Filmus Feb 21 '17 at 15:26
  • 1
    $\begingroup$ For your first question, try using a standard sphere packing bound from coding theory. $\endgroup$ – Yuval Filmus Feb 21 '17 at 15:33
4
$\begingroup$

For the first question, suppose that you have an algorithm that supports one error, and uses $m$ questions. For each element $i \in \{1,\ldots,n\}$, let $x_{i0}$ be the vector containing the answers to all questions when A doesn't lie, and let $x_{ij}$ be the vector containing the answers to all questions when A lies in question $j$. In total, we have $n$ collections of $m+1$ vectors. All these vectors are distinct: the $m+1$ vectors in a collection are distinct by definition, and vectors belonging to different collections must be distinct since the correct answer is different. We deduce that $(m+1)n \leq 2^m$, and so $m \geq \log n + \log\log n + \Omega(1)$.

For the second question, here is something to try. Let $m$ be a number so that $\log n$ queries suffice to find an element in $\{1,\ldots,m\}$, even when A is allowed to lie at most once. Partition $\{1,\ldots,n\}$ into $m$ intervals $[x_1,x_2),[x_2,x_3),\ldots,[x_m,x_{m+1})$, where $[a,b) = \{a,\ldots,b-1\}$, $x_1 = 1$, and $x_{m+1} = n+1$. Then this gives an $\alpha$-approximation for $\alpha = \max \frac{x_{i+1}-1}{x_i}$. I leave the rest to you.

The third question is addressed in Three thresholds for a liar by Spencer and Winkler. The threshold is $n/3$ (a strategy exists if $\ell < n/3$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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