Problem 3

In the liar's guessing game, A chooses an integer

x

with

1\le x\le N

and tells B the integer

N

. B asks questions of the form “does

x

belong to the set

D

?”, where

D

is any set of positive integers. A may answer each question truthfully or falsely, but among every

k+1

consecutive answers at least one must be truthful. After finitely many questions B names a set

X

of at most

n

positive integers and wins if

x\in X

. Prove (a) if

n\ge2^k

then B can guarantee a win; (b) for all sufficiently large

k

, some

n\ge1.99^k

defeats every strategy.

Step 1 of 3: Reformulate the answers as candidate sets

Previous step Next step

In plain words

A truthful answer says that x lies in the chosen set, while a lie says it lies in the complement; every block of k+1 answers must therefore cover the true x.

P_j\in\{D_j,D_j^c\},\qquad x\in P_j\cup\cdots\cup P_{j+k}

Detailed analysis

For the j-th question let $D_j$ be B's set and let $P_j$ be $D_j$ when A answers yes, or $D_j^c$ when A answers no. At least one answer in every $k+1$ consecutive answers is truthful, so the unknown x belongs to $P_j\cup\cdots\cup P_{j+k}$ for every j.