2012 IMO 第 3 题

The liar's guessing game is a game played between two players $A$ and $B$ . The rules of the game depend on two fixed 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 \leq x \leq 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 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:

(a) If $n \geq 2^{k}$ , then $B$ can guarantee a win.

(b) For all sufficiently large $k$ , there exists an integer $n \geq (1.99)^{k}$ such that $B$ cannot guarantee a win.

说谎者猜谜游戏是两个玩家 $A$ 和 $B$ 之间进行的游戏。游戏规则取决于两个玩家都知道的两个固定正整数$k$和$n$。

游戏开始时 $A$ 选择整数 $x$ 和 $N$ 以及 $1 \leq x \leq N$ 。玩家 $A$ 保守 $x$ 的秘密，并将 $N$ 如实告诉玩家 $B$ 。玩家 $B$ 现在尝试通过询问玩家 $A$ 问题来获取有关 $x$ 的信息，如下所示：每个问题由 $B$ 组成，指定正整数的任意集合 $S$(可能是在前一问题中指定的集合)，并询问 $A$ $x$ 是否属于 $S$ 。玩家$B$可以提出任意数量的问题。每个问题结束后，玩家$A$必须立即回答是或否，但可以说谎多次；唯一的限制是，在任何 $k + 1$ 个连续答案中，至少有一个答案必须是真实的。

在 $B$ 问了他想要的尽可能多的问题后，他必须指定一组最多包含 $n$ 个正整数的 $X$。如果 $x$ 属于 $X$ ，则 $B$ 获胜；否则，他就输了。证明：

(a) 如果 $n \geq 2^{k}$ ，则 $B$ 可以保证获胜。
(b) 对于所有足够大的 $k$ ，存在一个整数 $n \geq (1.99)^{k}$ 使得 $B$ 不能保证获胜。