This is the Guess-The-Number game with a twist!

## Variant 1

Take any positive integer $n$.

The game-master chooses an $n$-bit integer $x$.

The player makes queries one by one, each of the form "Is $x$ (strictly) less than $k$?".

The game-master answers each query immediately, always truthfully except at most once.

At the end the player must guess $x$ correctly to win.

What is the best strategy for the player to minimize the number of queries used in the worst-case? Note that the player can choose each query based on all the answers to the preceding queries. I have an algorithm that takes $n + O(\sqrt{n})$ queries, but I don't know whether this is optimal. Note that we can assume that the game-master does not have to choose $x$ at the start, but only has to keep his answers consistent with at least one possible $x$.

## Variant 2

Also, what is the best strategy if the game-master can answer falsely to a fraction $r$ of the queries (meaning that after the first $k$ queries the game-master has answered at most $rk$ of them falsely). Clearly if $r \ge \frac12$ then the player has no definite winning strategy iff $n>2$ because the game-master can simply answer the first query truthfully by choosing $x$ to be in the larger half, and then any such strategy must work even if the game-master now tells the player two values that he guarantees $x$ is among, in which case there is only one useful question and the game-master simply answers such questions "yes" and "no" alternately (and answers all other questions truthfully), and the player cannot ever tell which of the two $x$ is. What if $r < \frac12$?

[Edit: I don't see why this should be downvoted, because I provided my own algorithm in an answer below, even though I don't know its optimality. If anyone can prove its optimality or can provide a better algorithm, please post an answer!]

## Best Answer

What a lovely question! I'll concentrate on Variant 1.

You are in fact trying to guess two numbers. In the course of $Q$ questions (which I'll number from 1 to $Q$), you are trying to determine:

Since the questions each yield 1 bit of information, the best possible number of questions would

seemto be $Q=\lceil n+\log_2 (Q+1) \rceil$. Yes, this is a transcendental equation with $Q$ on both sides; but it does look a lot better than the bound you have proposed.As for the algorithm itself, what I would do is a straightforward binary search, with the understanding that:

In what follows, I'll take $n=5$, so that $0\le x\le 31$. Simple guesswork implies that $Q$ will be 9: that is, 5 to guess $x$, plus a bit over 3 to guess $1\le f\le 10$. ($Q=8$ is

notenough, because we need to account for the possibility that there is no lie).By symmetry, the first question is quite clearly the same as in the traditional binary search: "is $x\le 16$?". Without loss of generality, let's assume that the answer is Yes. In that case, the possibilities are:

…so indeed we have chopped the $32(Q+1)$ possibilities in half.

For the second question, we ask "Is $x\le y$?" for some integer $y$. I'm going to neglect the possibility that $y>16$ because it seems too inefficient. There are two possible answers:

YesNo…which adds up to $16(Q+1)$, as expected. But the possibilities are divided between $Qy+16$ for

Yesand the rest forNo, so the most even balance is achieved when $Qy+16$ is as near as possible to $8(Q+1)$: that is, when $y$ is as close as possible to $y=8\frac{Q-1}{Q}$.With $Q=9$, the target value is $8\times\frac{8}{9}$, which is $7\frac{1}{9}$. So the second question needs to be not "Is $x\le 8$?", as a naive binary search would ask, but "Is $x\le 7$?".

The overall algorithm before asking each question is therefore:

Although I assert that a binary search in $\langle x,f\rangle$ space is the best possible algorithm, and although I have given an approximate value for $Q$, I have not actually proved anything.