4

Alice has a hidden random integer $a$ in range $[1, 2^n]$. Each time, Bob can guess a number $x$, and Alice will answer whether $x \ge a$ or $x < a$. However, Alice can give a wrong answer for at most 1 times. In the worst case, how many guesses does Bob need to surely find out $a$?

The best result I could get is about $n + 2\sqrt{n}$. Are there any better solutions?

AlumKal
  • 87
  • 3
    Please add details about your solution, so others don't waste time re-creating it. Maybe hide it under a "spoiler", as this is tagged "recreational math"? – JonathanZ Apr 20 '23 at 15:13
  • 3
    https://www.jstor.org/stable/2689593 (copy here: https://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/guess-a-number-with-lying) – Jean-Claude Arbaut Apr 20 '23 at 15:15
  • 1
    Also worth a look: Searching games with errors—fifty years of coping with liars, by Andrzej Pelc. Some similar question on the SE network: https://mathoverflow.net/questions/32269/guess-a-number-with-at-most-one-wrong-answer https://mathoverflow.net/questions/308503/number-guessing-game-with-lying-oracle https://stackoverflow.com/questions/5680581/guess-the-number-with-lying-allowed Interesting problem, with ramifications in applied CS (error correcting codes, searching data with errors...) – Jean-Claude Arbaut Apr 20 '23 at 15:28
  • Some basic information considerations indicates a lower bound of $n + \log_2 n + 1$, $n$ to get the $n$ bits of $a$ with the possible lie + $\log_2 n + 1$ to get location of the bit where she lied ($0$ if she didn't, $1$ to $n$, if she did). – Paul Sinclair Apr 21 '23 at 12:06

1 Answers1

1

Thanks for the comments! It seems that I can't mark a comment as answer, so I have to post one.

This problem has been solved previously.

If one can ask a general yes-no question (whether or not $a \in S$), the answer is the smallest integer k that satisfies $2^{k-n} \ge k+1$. Therefore, $k \approx n + \log_2{n}$. The proof can be found here.

This paper shows that when only comparisons are allowed, the answer $k' \le k+1$. However, I haven't found out how to obtain an exact answer.

AlumKal
  • 87
  • 2
    So my lower bound (with a small correction) was actually achievable. Good to know. – Paul Sinclair Apr 21 '23 at 13:40
  • 1
    Actually, Andrzej Pelc's question is slightly different than yours. He allows Bob to ask any yes-no question, in particular "Is $a \in T$?" for any set $T$, Your version only allows $T$ to be unbounded intervals. So the answer to your problem may be higher (though apparently not much). – Paul Sinclair Apr 21 '23 at 13:53
  • Thanks for finding that out. I've updated my answer. – AlumKal Apr 21 '23 at 15:12