Problem: The liar's guessing game is a game played between two players $A$ and $B$.
The rules of the game depend on two fixed positive integers $k$ and $n$
which are known to both players.

At the start of the game $A$
chooses integers $x$ and $N$ with $1 \le x \le N$.
Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$.
Player $B$ now tries to obtain information about $x$
by asking player $A$ questions as follows:
each question consists of $B$ specifying an arbitrary set $S$
of positive integers (possibly one specified in some previous question),
and asking $A$ whether $x$ belongs to $S$.
Player $B$ may ask as many questions as he wishes.
After each question, player $A$ must immediately answer
it with yes or no, but is allowed to lie as many times as she wants;
the only restriction is that, among any $k+1$ consecutive answers,
at least one answer must be truthful.

After $B$ has asked as many questions as he wants,
he must specify a set $X$ of at most $n$ positive integers.
If $x$ belongs to $X$, then $B$ wins;
otherwise, he loses.
Prove that:

\begin{enumerate}[(a)]
  \ii If $n \ge 2^k$, then $B$ can guarantee a win.
  \ii For all sufficiently large $k$,
  there exists an integer $n \ge (1.99)^k$
  such that $B$ cannot guarantee a win.
\end{enumerate}

Solution: Call the players Alice and Bob.

\textbf{Part (a)}: We prove the following.
\begin{claim*}
If $N \ge 2^k+1$, then in $2k+1$ questions,
Bob can rule out some number in $\{1, \dots, 2^k+1\}$
form being equal to $x$.
\end{claim*}
\begin{proof}
  First, Bob asks the question $S_0 = \{ 2^k+1 \}$
  until Alice answers ``yes''
  or until Bob has asked $k+1$ questions.
  If Alice answers ``no'' to all of these then Bob rules out $2^k+1$.
  So let's assume Alice just said ``yes''.

  Now let $T = \{1, \dots, 2^k\}$.
  Then, he asks $k$-follow up questions $S_1$, \dots, $S_k$
  defined as follows:
  \begin{itemize}
    \ii $S_1 = \{1, 3, 5, 7, \dots, 2^k-1\}$ consists of all numbers
    in $T$ whose least significant digit in binary is $1$.
    \ii $S_2 = \{ 2, 3, 6, 7, \dots, 2^k-2, 2^k-1\}$
    consists of all numbers in $T$ whose second least
    significant digit in binary is $1$.
    \ii More generally $S_i$
    consists of all numbers in $T$ whose $i$th least
    significant digit in binary is $1$.
  \end{itemize}
  WLOG Alice answers these all as ``yes'' (the other cases are similar).
  Among the last $k+1$ answers at least one must be truthful,
  and the number $2^k$ (having zeros in all relevant digits)
  does not appear in any of $S_0$, \dots, $S_k$ and is ruled out.
\end{proof}
Thus in this way Bob can repeatedly find non-possibilities for $x$
(and then relabel the remaining candidates $1$, \dots, $N-1$)
until he arrives at a set of at most $2^k$ numbers.

\textbf{Part (b)}:
It suffices to consider $n = \left\lceil 1.99^k \right\rceil$
and $N = n+1$ for large $k$.
At the $t$th step, Bob asks some question $S_t$;
we phrase each of Alice's answers in the form ``$x \notin B_t$'',
where $B_t$ is either $S_t$ or its complement.
(You may think of these as ``bad sets'';
the idea is to show we can avoid having any number
appear in $k+1$ consecutive bad sets,
preventing Bob from ruling out any numbers.)

Main idea: for every number $1 \le x \le N$,
at time step $t$ we define its \emph{weight}
to be \[ w(x) = 1.998^e \]
where $e$ is the largest number
such that $x \in B_{t-1} \cap B_{t-2} \cap \dots \cap B_{t-e}$.

\begin{claim*}
  Alice can ensure the total weight never exceeds $1.998^{k+1}$
  for large $k$.
\end{claim*}

\begin{proof}
  Let $W_{t}$ denote the sum of weights after the $t$th question.
  We have $W_0 = N < 1000n$.
  We will prove inductively that $W_t < 1000n$ always.

  At time $t$, Bob specifies a question $S_t$.
  We have Alice choose $B_t$ as whichever of $S_t$ or $\ol{S_t}$
  has lesser total weight, hence at most $W_t/2$.
  The weights of for $B_t$ increase by a factor of $1.998$,
  while the weights for $\ol{B_t}$ all reset to $1$.
  So the new total weight after time $t$ is
  \[ W_{t+1} \le 1.998 \cdot \frac{W_t}{2}
    + \# \ol{B_t} \le 0.999 W_t + n. \]
  Thus if $W_t < 1000n$ then $W_{t+1} < 1000n$.

  To finish, note that
  $1000n < 1000 \left( 1.99^k + 1 \right) < 1.998^{k+1}$
  for $k$ large.
\end{proof}

In particular, no individual number can have weight $1.998^{k+1}$.
Thus for every time step $t$ we have
\[ B_t \cap B_{t+1} \cap \dots \cap B_{t+k} = \varnothing. \]
Then once Bob stops, if he declares a set of $n$ positive integers,
and $x$ is an integer Bob did not choose,
then Alice's question history is consistent with $x$ being Alice's number,
as among any $k+1$ consecutive answers
she claimed that $x \in \ol{B_t}$ for some $t$ in that range.

\begin{remark*}
  [Motivation]
  In our $B_t$ setup, let's think backwards.
  The problem is equivalent to avoiding $e = k+1$ at any time step $t$,
  for any number $x$.
  That means
  \begin{itemize}
    \ii have at most two elements with $e = k$ at time $t-1$,
    \ii thus have at most four elements with $e = k-1$ at time $t-2$,
    \ii thus have at most eight elements with $e = k-2$ at time $t-3$,
    \ii and so on.
  \end{itemize}
  We already exploited this in solving part (a).
  In any case it's now natural to try letting $w(x) = 2^e$,
  so that all the cases above sum to ``equally bad'' situations:
  since $8 \cdot 2^{k-2} = 4 \cdot 2^{k-1} = 2 \cdot 2^k$, say.

  However, we then get $W_{t+1} \le \half (2W_t) + n$,
  which can increase without bound due to contributions
  from numbers resetting to zero.
  The way to fix this is to change the weight to $w(x) = 1.998^e$,
  taking advantage of the little extra space we have
  due to having $n \ge 1.99^k$ rather than $n \ge 2^k$.
\end{remark*}