Guess the number despite false answer

Question

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!]

Answer 1

Variant 1

We deal with the general case where $x \in \{1..m\}$ for any positive integer $m$, instead of just $x \in \{1..2^n\}$. Let $k$ be the minimum number of queries needed. If $m = 1$ then $k = 0$, so from now on we assume that $m \ge 2$, in which case it is easy to see that $k \ge 3$. $\def\floor#1{\left\lfloor #1\right\rfloor }$ $\def\ceil#1{\left\lceil #1\right\rceil }$

Lower bound

Consider the following strategy by the game-master:

For each $i \in \{1..k\}$ maintain $S_i$ as the collection of all possible $x$ that satisfies the answers to the queries so far where the $i$-th query is assumed to be answered falsely, and maintain $S_0$ as the collection of all possible $x$ that satisfies the answers to all queries so far. Then on each query, pick the answer that maximizes the total of the sizes of the resulting $S_i$, namely $\sum_{i=0}^k \#(S_i)$.

At the start, $\sum_{i=0}^k \#(S_i) = (k+1)m$. On each query, for each $i \in \{0..k\}$ let $T_i$ and $U_i$ be the resulting $S_i$ on answering "yes" and "no" respectively. Then $S_i$ is the disjoint union of $T_i,U_i$ because each possibility remains under exactly one of the two answers. Thus $\sum_{i=0}^k \#(S_i)$ $= \sum_{i=0}^k \#(T_i) + \sum_{i=0}^k \#(U_i)$, and hence the resulting $\sum_{i=0}^k \#(S_i)$ will be at least half the previous value.

At the end, the player is supposed to know $x$, and hence also know which query was falsely answered, if at all. Thus only one of $S_{0..k}$ is non-empty, and hence $\sum_{i=0}^k \#(S_i) = 1$.

Therefore $2^k \ge (k+1)m$. From this we get $k \ge \log_2(4m) = \log_2(m)+2$ and hence:

$k \ge \log_2( \ceil{\log_2(m)+3} \cdot m ) = \log_2(m) + \log_2(\ceil{\log_2(m)+3})$.

Note that the reasoning by Martin is invalid because he claims that the player needs to distinguish $(k+1)m$ possibilities, which is never true at any point during the game; from the player's point of view the number of possible scenarios is always at most $m$. However, the above shows that Martin's idea of how the player can find $x$ efficiently can be turned into a strategy for how the game-master can delay the player from finding $x$.

Note also that this strategy for the game-master may not be optimal! It is conceivable that choosing the answer that leaves a lower $\sum_{i=0}^k \#(S_i)$ might in some rare cases be better because the subsequent 'cuts' might be sufficiently uneven to make it worse than choosing the opposite answer.

Optimal strategy

Note that in the optimal strategy, given any $2$ preceding queries "$<a$" and "$<b$", if the answers are both "yes" then $x < \max(a,b)$ because there can only be at most one false answer, and similarly if the answers are both "no" then $x \ge \min(a,b)$. Since it is useless to make a query that 'cuts' outside the possible interval for $x$, the optimal strategy would always maintain three adjacent intervals of length $p,q,r$ in that order such that $x$ is in one of them and is in the middle interval iff the queries bounding it were truthfully answered. Let $f(p,q,r)$ be the minimum number of queries needed to determine $x$.

Then we immediately get the following recursive program (in Javascript with memoization):

var v=[];
function f(p,q,r)
{ 
    if( p+q+r<=1 ) return 0;
    if( q==0 ) return Math.ceil(Math.log(p+r)/Math.log(2));
    if( !v[[p,q,r]] )
    {
        var m=2*(p+q+r);
        if( p>0 ) m=Math.min(m,Math.max(f(p,0,q),f(0,q,r)));
        if( r>0 ) m=Math.min(m,Math.max(f(p,q,0),f(q,0,r)));
        for(var a=1;a<q;a++) m=Math.min(m,Math.max(f(p,a,q-a),f(a,q-a,r)));
        v[[p,q,r]]=1+m;
    }
    return v[[p,q,r]];
}

Briefly, the base cases are obvious, namely when there is only one possible value for $x$ or the middle interval is empty, meaning that the lie has been used up and we can perform ordinary binary search on the remaining interval. The transition cases are because it is useless to make a query that 'cuts' outside the middle interval (this requires some thought!), and also useless to make the same query the third time if the first two are consistently answered.

Of course, $k = f(0,m,0)$, and it takes $O(M^4)$ to compute all $k$ for $m \in \{1..M\}$, so I ran it for $M = 100$:

If $m = 2$ then $k = 3$.

If $m \in \{3..4\}$ then $k = 5$.

If $m \in \{5..7\}$ then $k = 6$.

If $m \in \{8..12\}$ then $k = 7$.

If $m \in \{13..22\}$ then $k = 8$.

If $m \in \{23..40\}$ then $k = 9$.

If $m \in \{41..70\}$ then $k = 10$.

If $m \in \{71..100\}$ then $k = 11$.

For all these, $k$ is at most $1$ more than the lower bound, so we conjecture:

? $k \le \ceil{ \log_2(m) + \log_2(\ceil{\log_2(m)+3}) } + 1$.

But how to prove it? I tried but couldn't figure out a way. Can anyone prove or disprove it?

A simpler strategy that might be optimal

The player can (given $k$) follow the following strategy:

Maintain the same $S_{0..k}$ as defined above. At each step, choose $y$ and ask the question "$x < y$?" such that the resulting $\sum_{i=0}^k \#(S_i)$ is as close to half the previous value as possible.

It is not clear whether this is the optimal strategy, though it is likely to be so. Martin claims that it is the best, but this is a classic mistake of assuming that the greedy solution is globally optimal. How would we know whether a slightly less even 'cut' at one step may not guarantee easier 'cuts' later? But if we know that the game-master's strategy above is optimal, then optimality of this strategy follows because the resulting possibilities are monotonic in the 'cut' location if the answer to the query is the same.

Let $c_t$ be $\sum_{i=0}^k \#(S_i)$ after step $t$, where $c_0$ is the initial value at the start of the game.

At step $t \in \{1..k\}$, choosing $y = 0$ will make $\sum_{i=0}^k \#(T_i) = 0$, while choosing $y = m$ will make $\sum_{i=0}^k \#(T_i) = \sum_{i=0}^k \#(S_i)$. Also increasing $y$ by $1$ will make $\sum_{i=0}^k \#(T_i)$ increase by some number in the range $[0,k-t+2]$, because $S_i,S_j$ are disjoint for any $i,j \in \{0..t-1\}$. Thus we can always choose $y$ such that $\sum_{i=0}^k \#(T_i)$ is within $\frac{k-t+2}{2}$ of $\frac12 c_{t-1}$, which would imply that $c_t \le \floor{ \frac12 c_{t-1} + \frac{k-t+2}{2} }$.

This is the tightest recurrence I can get, but it is still not good enough! If I didn't make a mistake, solving the recurrence results in the upper bound on $c_k$ always being greater than $3$, which means that we can't guarantee analytically that $k$ queries following this strategy are enough regardless of how big $k$ is! I know this seems ridiculous but I don't see a way to tighten the bounds.

Therefore, since we cannot prove optimality of the game-master's strategy or the success of this player's strategy, even implementing this algorithm as it is is useless, because we do know whether the answer with lower $c_t$ will be better for the game-master or not, and hence we end up having to perform exponential search (whether pruned or not) to ensure correctness.

Moreover, we don't know $k$ so we can't even implement this algorithm unless we find $k$ by some other means first (such as the optimal strategy).

Variant 2

The lower bound extends to this variant by a similar argument. However the optimal strategy does not. The simpler strategy does, but it is even less clear whether it is optimal, and again we still face the problem of finding $k$.

Answer 2

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:

1. The number, between $0$ and $2^n$. That is $n$ bits of information.
2. Whichth answer was a lie. This is a number between $1$ and $Q$, plus $Q+1$ to denote "no lie", which makes $Q+1$ possible values, or $\log_2 (Q+1)$ bits of information.

Since the questions each yield 1 bit of information, the best possible number of questions would seem to 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:

• I am searching not only for the number $x$ but also for the number $f$ of the false answer, where (as before) $f=Q+1$ means that there is no false answer.
• At each stage, my aim is to maximise the information extracted by having as many possibilities coming from a "Yes" answer as from a "No" one. But the possibilities to be counted are not possible values of $x$, as they would be in an ordinary binary search, but possible values of $\langle x,f\rangle$. This gives a different choice of question from the traditional "midpoint of the interval" choice.

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 not enough, 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:

• $x\le 16$ and $1\lt f \le Q+1$: $16Q$ possibilities.
• $x\gt 16$ and $f=1$: $16$ possibilities.

…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:

Yes

• $x\le y$ and $2\lt f \le Q+1$: $(Q-1)y$ possibilities.
• $y\lt x\le 16$ and $f=2$: $16-y$ possibilities.

No

• $y\lt x \le 16$ and $2\lt f\le Q+1$: $(16-y)(Q-1)$ possibilities.
• $16\lt x\le 32$ and $f=1$: $16$ possibilities.
• $x\le y$ and $f=2$: $y$ possibilities.

…which adds up to $16(Q+1)$, as expected. But the possibilities are divided between $Qy+16$ for Yes and the rest for No, 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:

1. Note all the $\langle x,f\rangle$ pairs that are still possible given the questions and answers so far.
2. Go through all possible values of $y$.
3. For each value of $y$, consider how many $\langle x,f\rangle$ pairs match the answer "Yes" to "Is $x\le y$?" and how many match "No".
4. Pick the value of $y$ for which the "Yes" and "No" counts are closest together, and ask the question using that value.

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.

Answer 3

Here is an algorithm for Variant 1 that uses at most $n+2\sqrt{2n}+2$ queries, together with its proof.

1. Let $k = \lceil \sqrt{2n} \rceil$.

2. Follow the binary search algorithm but confirm the current interval every $k$ steps.

   1. The queries used to confirm the current interval $[a,b)$ are "$x < a$" and "$x < b$".

   2. This takes at most $n + 2 \lfloor \frac{n}{k} \rfloor \le (1+\frac2k)n$ queries if executed to the end.

   3. Note that consistent answers to any confirmation query implies that it is truthful.

   4. And inconsistent answers to any confirmation query implies that the lie has been used up.

3. If this modified binary search reaches the end:

   1. It points at a certain number $y$ as the answer (if there has been no lie).

   2. If not already done, use $2$ queries to confirm $y$, namely "$x < y$" and "$x < y+1$".

4. If there is an inconsistent answer to any confirmation query for current interval $I$:

   1. Use ordinary binary search on the previous confirmed interval $J$.

   2. For a confirmation in the middle, $J$ is less than $2^{k+1}$ times the size of $I$.

   3. For a confirmation at the end, if $k \nmid n$ then $J$ is less than $2^k$ times the size of $I$.

5. Therefore the total number of queries used is at most $(1+\frac2k)n + k + 2 \le n + 2 \sqrt{2n} + 2$.

The question is whether this is asymptotically optimal, and if not then what is an asymptotically better algorithm?

Answer 4

This answer builds on the previous one by giving simulation results and program code. Anyone who wishes can therefore verify it by running the program.

Assertion (for Version 1)

A number of questions, $Q$, sufficient to ensure a correct solution even in the worst case satisfies $$Q=\lceil n+\log_2 (Q+1) \rceil$$

In practice, 1 or 2 needs to be added to the number of questions asked, because a perfect binary chop is never precisely attainable: see the Motivation section and the verification results below.

Verification

This assertion has been verified programmatically as follows:

• $n=4$ needs 8 questions.
• $n=5$ needs 9 questions.
• $n=6$ needs 10 questions.
• $n=7$ needs 11 questions.
• $n=8$ needs 13 questions.
• $n=9$ needs 14 questions.
• $n=10$ needs 15 questions.
• $n=11$ needs 16 questions.
• $n=12$ needs 17 questions.
• $n=13$ needs 18 questions.

Higher values can be checked with a more optimised program, and notes for optimisation of running time are given later. However, checking by definition requires $2^n$ operations, of whatever degree of complexity, so checking every single one of $2^100$ cases is not practicable.

Motivation

The key motivation of this algorithm is that it is impossible to deduce $x\in[0,2^n)$ without simultaneously also deducing $q\in[0,Q]$, where $q$ is the number of the question which was answered falsely. One is in fact guessing $\langle x,q\rangle$ pairs, because guessing $x$ alone is not possible. Note: the range of possible values of $q$ covers one more than the number of questions, because we have to account for the possibility that the answerer never lies.

Accordingly the information content of one playing of the game is $n+\log_2 (Q+1)$ bits.

This number is necessary as well as sufficient. To see this, consider the case where the answerer tells an intermediary to do the answering for him. To be able to do this job, it is not enough for the intermediary to know what the value of $x$ is ($n$ bits). He also needs to know which question to lie about ($\log_2 (Q+1)$ bits).

Information-theoretically, the way to get the maximum information out of a question is to ensure that [as exactly as possible] half of the currently possible states of affairs match a "Yes" answer and half match a "No". This is also how a classic one-dimensional binary search works. If the halving were exactly possible then a full bit of information would be obtained with each question and the limit mentioned above would be reached exactly.

In practice, when constructing question $q$ the balance between Yes and No jumps in steps of $Q-q$, which makes it possible that slightly less than one bit of information will be obtained.

Data structures

The basic structure is a bitmap of $2^n$ bits, marking which values of $x$ are currently possible. We need an array of $Q+1$ such bitmaps, one for each possible falsely answered question $q$ plus one for the case where no answer is false. The array of bitmaps is called Guess in the program.

Solution strategy

At any given stage, the Guess structure contains 1-bits for all conclusions ($\langle x,q\rangle$ pairs) that are currently compatible with the answers received so far. When no questions have been asked, the Guess therefore starts with all its bits set to 1. When enough questions have been asked so that the number can be deduced, only one bit in Guess will be 1.

Being told that "$x<k$" as an answer to question $q$ has two effects on Guess:

1. For the $q$th bitmap in Guess, we know that the answer is a lie, and so we can set to zero all the bits corresponding to $x<k$.
2. For all the other bitmaps, we know that the answer is true, and so we can set to zero all the bits corresponding to $x\ge{k}$.

It remains to know which value of $k$ to use when asking the question. The value of $k$ to use is that which will most nearly halve the number of bits in Guess. In the program below, I have used an exhaustive linear search to find this value.

The program in C++

#include <iostream>
#include <bitset>
#include <vector>
#define NBITS 10
#define NQUESTIONS 16 // The maximum number of questions to allow for.
#define NVALUES (1<<(NBITS))
typedef std::bitset<NVALUES> Bits;
class Guess
{Bits valid[NQUESTIONS+1];
public:
 void splitInto(Guess &ifLess,Guess &ifGreaterOrEqual,int questionNumber,int k) const
  {Bits temp;
   for (int i=0;i<k;i++)
    temp.set(i);
   for (int q=0;q<=NQUESTIONS;q++)
    if (q!=questionNumber)
      {ifLess.valid[q] = this->valid[q] & temp;
       ifGreaterOrEqual.valid[q] = this->valid[q] & ~temp;
       }
     else
      {ifGreaterOrEqual.valid[q] = this->valid[q] & temp;
       ifLess.valid[q] = this->valid[q] & ~temp;
       }
   }
 Guess() {for (int q=0;q<=NQUESTIONS;q++) valid[q].set();};
 int count(int maxQ=NQUESTIONS) const {int total=0; for (int q=0;q<=maxQ;q++) total += valid[q].count(); return total;};
 };

The function splitInto takes a pre-existing Guess object and fills in two resultant Guess objects: one on the assumption that the answer to the question is "$x<k$" and one on the assumption that the answer to the question is "$x\ge k$". The two objects, combined, will contain as many bits as the original object. This is not the most efficient way of actually playing the guessing game, but it is the best way of investigating all possible sequences of answers in order to compute worst-case performance.

static int maxQuestion=0;
void recursion(int questionNumber,const Guess &status)
{if (questionNumber>=NQUESTIONS)
   exit(3); // Overflowed the space available in `Guess`.
 if (questionNumber>maxQuestion) maxQuestion=questionNumber;
 Guess ifLess,ifGreaterOrEqual;
 /* The first task is to calculate the best estimate of k. 
    Find the value for which the Yes and No answers generate the most equal numbers of results.
    */
 int k=-1; // Best value so far.
 int deltaLast=NVALUES*(NQUESTIONS+1); // Smallest difference so far.
 for (int k2=1;k2<NVALUES;k2++) // Linear search: inefficient but certain.
  {status.splitInto(ifLess,ifGreaterOrEqual,questionNumber,k2);
   int delta=std::abs(ifLess.count()-ifGreaterOrEqual.count());
   if (delta<deltaLast)
     {k=k2;
      deltaLast=delta;
      };
   };
 /* Now split `Guess` according to "x<k?". */ 
 status.splitInto(ifLess, ifGreaterOrEqual, questionNumber, k);
 /* If more than one possibility in the Yes branch, ask deeper.
 if (ifLess.count(questionNumber+1)>1)
   recursion(questionNumber+1,ifLess);
 /* If more than one possibility in the No branch, ask deeper. */
 if (ifGreaterOrEqual.count(questionNumber+1)>1)
   recursion(questionNumber+1,ifGreaterOrEqual);
 }

The function recursion searches for the most promising value of $k$ (ie. the one with most equally balanced results) and then splits the current guess according to it. If either of the results (the one assuming that the answer is true and the one assuming that the answer is false) has more than one 1-bit in it, that result needs to be investigated further and recursion calls itself recursively to do this.

Finally, start the recursion off with a newly-initialised Guess and 0 questions asked so far.

int main(int argc, const char * argv[])
{Guess base;
 recursion(0,base);
 std::cout << maxQuestion+1;
 return 0;
}

Optimisation

The best optimisations would be:

• Represent the possible results by $[low,high)$ ranges rather than by bitmaps. This restricts the type of question asked from a completely general one, "Does $x$ have property $P$?", to a specific "$x<k$?" one of the kind used in this particular problem. It also reduces the bits required to store the set of possible results.
• Note that the number of results matched by "$x<k$" increases monotonically with $k$ except when looking at the block of results corresponding to a lie at the current question number, when it decreases. Therefore the overall graph of "number of results matching Yes if we choose this value of $k$" is monotone up, then down, then up, and this can be searched in logarithmic rather than linear time.

Version 2 of the question

The same principle should be applicable to the case where up to $rQ$ questions may be answered falsely. Again, the key is that what is being deduced is not the value of $x$ alone but, inevitably, the value of $\langle x,\vec q\rangle$, where $\vec q$ is the list of questions which have been answered falsely. The optimum strategy therefore, once again, is the one which at each stage most nearly bisects the still-possibly-valid $\langle x,\vec q\rangle$ values.

Rewriting the original formula for $Q$ as $$2^Q\ge 2^n(Q+1)$$ and temporarily simplifying "at most $rQ$ lies" to "exactly $rQ$ lies", we get the revised formula for $Q$: $$2^Q\ge 2^n\binom{Q}{rQ}$$ When $r=\frac12$, using the standard approximation for factorials, this is close to $$2^Q\ge 2^n 2^Q$$

This is impossible, corresponding to the verbal argument for impossibility given in the original question. Indeed, with a spare factor of $2^n$ to play with, a slightly lower limit for $r$ should be justifiable.