IMO 2012 · Problem 3

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:

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

Official text of the problem. Official problem paper (PDF)

Solution

For a given history of questions and answers, call \(y\in\{1,\ldots,N\}\) possible if that history would satisfy the restriction on lies when \(x=y\). The actual value \(x\) always remains possible.

For each possible \(y\), let \(d(y)\) be the number of consecutive lies at the end of the history, assuming \(x=y\). Initially \(d(y)=0\). A truthful answer resets \(d(y)\) to \(0\); a lie increases it by \(1\). If it reaches \(k+1\), the value \(y\) becomes impossible and is discarded.

1. The winning strategy when \(n\ge 2^k\).

We show that whenever more than \(2^k\) values remain possible, \(B\) can force at least one of them to be discarded after finitely many questions.

Define \[ w_i=2^{k+1}-2^i\qquad(0\le i\le k+1), \] so that \(w_{k+1}=0\). If \(C\) is the current set of possible values, put \[ m=|C|,\qquad \Phi=\sum_{y\in C}w_{d(y)}. \] The quantity \(\Phi\) is a nonnegative integer.

For a question specified by \(S\), let \(\Phi_{\mathrm{yes}}\) and \(\Phi_{\mathrm{no}}\) be the potentials after the two possible answers. Each candidate of age \(i\) contributes \(w_0\) after one answer and \(w_{i+1}\) after the other. Since \[ w_0+w_{i+1}=2w_i-1, \] we have \[ \Phi_{\mathrm{yes}}+\Phi_{\mathrm{no}}=2\Phi-m. \tag{1} \] Also, writing \[ a(y)=w_0-w_{d(y)+1}=2^{d(y)+1}-1, \] we obtain \[ \Phi_{\mathrm{yes}}-\Phi_{\mathrm{no}} =\sum_{y\in C\cap S}a(y)-\sum_{y\in C\setminus S}a(y). \tag{2} \]

Suppose now that \(m>2^k\).

If at least two candidates have age \(k\), \(B\) asks a question whose set contains one of them and excludes another. Either answer is a lie for one of these candidates, so at least one is discarded.

Otherwise, at most one candidate has age \(k\). Set \[ T=2^k-1. \] All the weights \(a(y)\) are positive integers at most \(T\), except possibly one weight equal to \[ 2^{k+1}-1=2T+1. \] We claim that these weights can be divided into two groups whose sums differ by at most \(T\).

To prove this, place the weights, in nonincreasing order, into whichever group currently has the smaller sum. Once the difference between the sums is at most \(T\), it remains so: each subsequent weight is at most \(T\). Thus only an initial weight \(2T+1\) could cause difficulty. Until the difference becomes at most \(T\), every subsequent weight goes into the opposite group. The total of those subsequent weights is at least \[ m-1\ge 2^k=T+1, \] so the difference must eventually become at most \(T\). This proves the claim.

Let \(S\) consist of the candidates in one of these two groups. By (1) and (2), either answer gives \[ \Phi_{\mathrm{next}} \le \frac{2\Phi-m+T}{2} =\Phi-\frac{m-T}{2} \le \Phi-1, \] because \(m\ge 2^k+1=T+2\).

Consequently, whenever \(m>2^k\), \(B\) can ask a question which either guarantees a discard or decreases \(\Phi\) under both answers. If no candidate were discarded, the nonnegative integer \(\Phi\) would decrease at every step, which cannot continue indefinitely. Hence \(B\) can force a discard in finitely many questions.

Repeating this procedure, \(B\) eventually has at most \(2^k\) possible values. He chooses these values as \(X\). Since the actual \(x\) is among them and \(2^k\le n\), he wins.

2. The lower bound.

We first prove a counting claim. Suppose that \(N\) and a real number \(r\), with \(1<r<2\), satisfy \[ N\le (2-r)r^k. \tag{3} \] Then, for any strategy of \(B\), there exists an infinite sequence of answers which satisfies the restriction on lies simultaneously for every \(x\in\{1,\ldots,N\}\).

Fix a strategy of \(B\). It determines the next question after every answer history. If the strategy stops at some history, extend it beyond that history by arbitrary questions; this merely lets us discuss answer sequences of every length.

Call an answer history good if it is legal for every \(x\in\{1,\ldots,N\}\), and let \(g_t\) be the number of good histories of length \(t\). In particular, \[ g_0=1,\qquad g_t=2^t\quad(1\le t\le k). \tag{4} \]

For \(t\ge k+1\), consider the \(2g_{t-1}\) one-answer extensions of good histories of length \(t-1\). If such an extension is not good, its last \(k+1\) answers must all be lies for at least one candidate \(y\).

For any fixed history of length \(t-k-1\) and any fixed \(y\), there is exactly one continuation of length \(k+1\) consisting entirely of lies for \(y\): at every step, give the opposite of the truthful answer to the question prescribed by \(B\)'s strategy. This remains true even though the questions depend on earlier answers.

The prefix of length \(t-k-1\) of a newly bad extension is good. Therefore the number of newly bad extensions is at most \(Ng_{t-k-1}\), giving \[ g_t\ge 2g_{t-1}-Ng_{t-k-1}. \tag{5} \]

We prove inductively that \[ g_t\ge r g_{t-1}\qquad(t\ge1). \tag{6} \] For \(t\le k\), this follows from (4) and \(r<2\). For \(t\ge k+1\), the preceding \(k\) instances of (6) give \[ g_{t-1}\ge r^k g_{t-k-1}. \] Using (5) and then (3), \[ g_t \ge \left(2-\frac{N}{r^k}\right)g_{t-1} \ge r g_{t-1}. \] Thus (6) holds, and in particular \(g_t>0\) for every \(t\).

There is consequently an infinite answer sequence all of whose finite prefixes are good. Indeed, good histories form a tree with at most two children at each vertex and vertices at arbitrarily large depths. Starting at the root, repeatedly choose a child having good descendants at arbitrarily large depths; such a child always exists because there are only two children. The resulting infinite path proves the counting claim.

Now choose \[ r=1.995,\qquad n=\left\lceil1.99^k\right\rceil,\qquad N=n+1. \] For all sufficiently large \(k\), condition (3) holds. To see this, observe that \[ \frac{N}{r^k} \le \left(\frac{1.99}{1.995}\right)^k+\frac{2}{1.995^k} \longrightarrow 0, \] whereas \(2-r=0.005>0\).

Fix any proposed strategy of \(B\), with this value of \(N\), and take the infinite answer sequence provided by the claim. Every candidate \(1,\ldots,N\) remains possible throughout that sequence.

If \(B\) never stops along this sequence, his strategy does not guarantee a win in finitely many questions. If he stops and announces \(X\), then \[ |X|\le n=N-1, \] so some \(y\in\{1,\ldots,N\}\) is absent from \(X\). Player \(A\) can choose this \(y\) as her secret value initially and give the constructed answers up to the stopping point. All these answers satisfy the restriction for \(x=y\), and \(B\) loses. The secret value is chosen before play: the argument first analyzes the fixed strategy of \(B\), then specifies this counterplay.

Thus \(B\) cannot guarantee a win for the integer \(n=\lceil1.99^k\rceil\ge1.99^k\), for every sufficiently large \(k\).

The solution was checked against the official IMO shortlist solutions.