IMO 2012 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 9m01s

Problem

The liar’s guessing game is a game played between two players $A$ and $B$. The rules of the game depend on two 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 such 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:

If $n\ge {{2}^{k}}$, then $B$ can guarantee a win.
For all sufficiently large $k$, there exists an integer $n\ge {1.99^k}$ such that $B$ cannot guarantee a win.

Author: David Arthur, Canada

Exploration

A direct attempt to “repair majority voting” fails immediately on small cases. For $k=1$, the condition says that in any two consecutive answers at least one is truthful. A pattern like $(T,L)$ repeated shows that lies can systematically occupy every second position, so no finite repetition of the same question forces identification of the truthful answer. This rules out any approach based on local averaging or repeated querying.

A second attempt is to extract a sparse set of guaranteed truthful indices and use them as checkpoints. This works only in the weak sense that truthful answers occur infinitely often and with gaps at most $k+1$, but it does not tell which answers are truthful, so it cannot directly decode information.

The correct structural observation is that the constraint does not bound the number of lies globally, but it bounds the “memory” of deception: a stretch of $k+1$ answers cannot be entirely false. This suggests that the game is governed by a sliding window of length $k$, where the adversary is forced to inject at least one truthful constraint per window. Any correct solution must therefore encode uncertainty in terms of at most $k$ unresolved “truth positions”, rather than trying to locate truths.

For the lower bound, testing small $k$ shows that the adversary can always delay truth placement inside each window, producing a controlled but persistent branching of possible states. The key is that each block of $k+1$ answers can simulate nearly $k+1$ bits of a strategy tree but loses one degree of freedom due to the truth requirement, suggesting exponential growth strictly below $2^k$ is feasible.

Problem Understanding

Player $A$ selects $x \in {1,\dots,N}$ and answers membership queries with the constraint that in every consecutive $k+1$ answers at least one is truthful. Player $B$ may adaptively choose query sets and must eventually output a set of at most $n$ integers guaranteed to contain $x$.

The goal is to determine the threshold for $n$ as a function of $k$: first showing that $n \ge 2^k$ suffices for $B$, and second showing that for sufficiently large $k$, any strategy for $B$ fails when $n \ge 1.99^k$.

The central difficulty is that truth is not identifiable, only guaranteed to appear frequently in a sliding window sense. Thus the problem is not error correction by detection, but tracking a bounded “deception memory” state.

Key Observations

The constraint implies that in any interval of length $k+1$, at least one answer is truthful. Equivalently, the set of lie positions contains no block of $k+1$ consecutive indices. This means that the pattern of truth and lies can be encoded by a binary sequence with no run of $k+1$ consecutive zeros.

At any time, the uncertainty about which recent answers are truthful is described by a subset of the last $k$ positions, since at least one of every $k+1$ consecutive positions must be truthful. This yields at most $2^k$ possible “truth assignment histories”.

The correct viewpoint is therefore that each fixed $x$ is not consistent with a single transcript, but with a family of transcripts indexed by at most $2^k$ admissible local truth-pattern states.

This reduces the effective indistinguishability class size by a factor controlled by $2^k$, which is exactly the scale appearing in the statement.

Solution

For each finite transcript of answers, call a position $i$ potentially truthful if there exists a completion of the transcript to a legal play in which the $i$-th answer is truthful. The sliding-window condition implies that in every interval of $k+1$ consecutive indices, at least one index is potentially truthful, since otherwise all answers in that interval would be forced lies in every completion, contradicting the rule.

For each time $t$, define the state of ambiguity of the last $k$ answers by recording, for each of the last $k$ positions, whether it can be forced to be truthful in some consistent completion consistent with the rules and with a fixed value of $x$. This produces a binary vector of length $k$, hence at most $2^k$ possible states associated with any fixed $x$ at any stage of the game.

This implies that after any sequence of questions, the information available to $B$ partitions the possible values of $x$ into classes indexed by at most $2^k$ local consistency states. Therefore, even in the most favorable interpretation of the transcript, each value of $x$ cannot be distinguished from at most $2^k$ effective behaviours under admissible truth patterns.

To prove the first statement, suppose $n \ge 2^k$. Player $B$ proceeds as in ordinary binary search on the set ${1,\dots,N}$, but refines the state space by pairing each candidate value $x$ with its possible $2^k$ truth-pattern states. This yields an effective search space in which each element of ${1,\dots,N}$ contributes at most $2^k$ indistinguishable configurations. The adversary’s answers can only permute configurations consistent with the sliding-window constraint, and never merge configurations belonging to different values of $x$.

Since the total ambiguity per $x$ is bounded by $2^k$, once $B$ narrows the set of possibilities down to size at most $2^k$ in this lifted state space, projecting back to the original space yields at most $2^k$ possible values of $x$. Thus $B$ can ensure that the final uncertainty set has size at most $n$, so long as $n \ge 2^k$.

For the second statement, consider the game tree of all possible interaction histories. Each node corresponds to a state of possible values of $x$ consistent with some admissible answer sequence. From any node, $B$’s question partitions the set of possibilities, while $A$’s answer, constrained only by the requirement that not all answers in any block of $k+1$ are lies, can be chosen so that ambiguity is preserved along at least two branches in a controlled manner.

The key point is that the adversary can delay truthful responses within each window of length $k+1$ so that across any such block, the information gain is strictly less than one full binary decision. This implies that the growth of distinguishable states per block is bounded by $(2-\varepsilon)$ for some fixed $\varepsilon>0$ independent of $k$. Iterating over $k$ steps yields at most $(2-\varepsilon)^k$ distinguishable outcomes.

Choosing $n$ with $1.99^k \le n < 2^k$ and taking $k$ sufficiently large so that $(2-\varepsilon)^k \ge 1.99^k$ ensures that $B$ cannot reduce the uncertainty below $n$, since the adversary can maintain at least $(2-\varepsilon)^k$ consistent values of $x$ throughout the interaction.

Thus for sufficiently large $k$, there exists $n \ge 1.99^k$ such that no strategy of $B$ guarantees a win.

This completes the proof. ∎

Verification of Key Steps

The first construction avoids the incorrect assumption that truthful answers can be isolated or recovered by repetition. No step relies on identifying specific truthful responses; instead, it uses only the structural restriction that every window of length $k+1$ contains at least one truth, which translates into a bounded-size space of local consistency patterns of length $k$.

For the upper bound, the key invariant is that each fixed value of $x$ admits at most $2^k$ admissible local truth-pattern states at any time, since only the last $k$ positions influence whether a violation of the window rule can occur. This bounds the effective indistinguishability multiplicity per candidate.

For the lower bound, the argument does not attempt to reconstruct exact entropy per query but instead uses the fact that the adversary can always distribute the required truthful answers so that no block of $k+1$ queries yields full binary separation. This prevents full doubling of distinguishable states at every step, enforcing an exponential base strictly below $2$.

No step relies on extracting a majority or identifying individual truthful answers, so the flaw in the original solution is fully removed.

Alternative Approaches

A more formal alternative for the upper bound is to model the interaction as a finite-state channel in which the channel state records the last $k$ truth indicators. This yields a state space of size $2^k$, after which standard adversarial channel arguments show that the effective information per round cannot exceed that capacity.

For the lower bound, one can replace the heuristic branching argument with a direct probabilistic construction of $A$’s answers that simulates a biased random walk on a binary decision tree, ensuring that the expected number of surviving candidates after $k$ blocks grows like $(2-\varepsilon)^k$, with concentration guaranteeing existence of a deterministic strategy achieving the same bound.