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 3 of 3: A weighted adversary prevents a much smaller target

Previous step Next step

In plain words

A candidate that is repeatedly absent from the possible truthful sets becomes exponentially expensive, so A can keep every candidate alive.

x_i^{j+1}=\begin{cases}x_i^j,&i\in P_j,\\ qx_i^j,&i\notin P_j,\end{cases}\qquad T_j=\sum_i x_i^j

Detailed analysis

Choose $1.99<p<q<2$ and, for all sufficiently large k, an integer n with $1.99^k\le n<p^k-1$ and $(p/q)^k\le2-q$ . Start with $N=n+1$ candidates and $x_i^0=1$ , so $T_0=N\le p^k<q^k$ . For a question D, the two possible next totals are $T(D)=\sum_{i\notin D}qx_i+|D|$ and $T(D^c)=\sum_{i\in D}qx_i+|D^c|$ . Their sum is $qT+N\le q^{k+1}+p^k\le2q^k$ , so one choice is at most $q^k$ (by the displayed condition). Choose that side as P. Inductively $T_j\le q^k$ . If some candidate i were absent from $k+1$ consecutive sets P, its weight would become at least $q^{k+1}$ , contradicting $T_j\le q^k$ ; hence every candidate belongs to every block union required in step 1. Therefore all $N=n+1$ candidates remain possible, while B may name only n of them, so B cannot guarantee a win.