2012 IMO Shortlist C6

Let $k$ and $n$ be fixed positive integers. In the liar's guessing game, Amy chooses integers $x$ and $N$ with $1 \leq x \leq N$. She tells Ben what $N$ is, but not what $x$ is. Ben may then repeatedly ask Amy whether $x \in S$ for arbitrary sets $S$ of integers. Amy will always answer with yes or no, but she might lie. The only restriction is that she can lie at most $k$ times in a row. After he has asked as many questions as he wants, Ben must specify a set of at most $n$ positive integers. If $x$ is in this set he wins; otherwise, he loses. Prove that: a) If $n \geq 2^{k}$ then Ben can always win. b) For sufficiently large $k$ there exist $n \geq 1.99^{k}$ such that Ben cannot guarantee a win.

令$k$和$n$为固定正整数。在说谎者的猜谜游戏中，Amy 选择整数 $x$ 和 $N$，其中 $1 \leq x \leq N$。她告诉本 $N$ 是什么，但没有告诉本 $x$ 是什么。然后 Ben 可能会反复询问 Amy 对于任意整数集合 $S$ 是否 $x \in S$ 。艾米总是会回答“是”或“否”，但她可能会撒谎。唯一的限制是她最多可以连续说谎 $k$ 次。在问了尽可能多的问题后，Ben 必须指定一组最多 $n$ 个正整数。如果 $x$ 在这组中，他就获胜；否则，他就输了。证明： a) 如果 $n \geq 2^{k}$ 那么 Ben 总是能赢。 b) 对于足够大的$k$，存在$n \geq 1.99^{k}$，使得Ben 不能保证获胜。