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 2 of 3: B can eliminate one candidate whenever more than

2^k

remain

Previous step Next step

In plain words

Choose each next question inside the candidates not yet covered by the previous possible truthful sets, keeping two large halves until one candidate is uncovered.

N\ge2^k+1\Longrightarrow\text{reduce the candidate set by one}

Detailed analysis

Assume the current candidate set S has $N\ge2^k+1$ elements. Choose $D_1$ so both sides have at least $2^{k-1}$ elements. After $P_1$ is known, choose $D_2$ so both $D_2\cap P_1^c$ and $D_2^c\cap P_1^c$ have at least $2^{k-2}$ elements; continue so that after j answers the uncovered set has two such halves of size at least $2^{k-j}$ . After k answers choose $D_{k+1}$ to be a singleton outside $P_1\cup\cdots\cup P_k$ . If $P_{k+1}=D_{k+1}^c$ , discard that singleton. If $P_{k+1}=D_{k+1}$ , repeat the k-step construction on $S\setminus D_{k+1}$ ; the union $P_{k+1}\cup\cdots\cup P_{2k+1}$ contains x and omits at least one candidate. Thus B reduces N by one. Iterating leaves at most $2^k$ candidates, which B may name as X.