※ 引述《FAlin (FA（バルシェ应援）)》之铭言：
: 3. The "liar's" guessing game is a game played between two players A and B.
: The rules of the game depend on two 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≦x≦N. Player 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 wins; otherwise, he loses.
: Prove that:
: 1. If n≧2^k, then B can guarantee a win.
: 2. For all sufficiently large k , there exists an integer n ≧(1.99)^k such
: that B cannot guarantee a win.
====第3题防雷页===
Part 1.
此部份只需要证明假如现在有超过2^k个可能性 在有限次的问题之后
可以把一个可能的答案淘汰
不妨假设现在可能的数字为 1,2,...,2^k+1
B首先连续询问是否答案是2^k+1 假如连续 k+1次A都回答否 则我们知道2^k+1不是x
可以把其淘汰。此种情形解决。
假如A某一次回答是 这么一来 假如正确答案在1,2,...,2^k中，A就已经讲了一次假话
接下来的问题 B根据1,2,...,2^k的二进制表现法中的least significant k位来询问
(2^k+1在不在询问的集合中不重要)
如此又可以得到k个答案，且1,2,...,2^k中洽有一个数跟这k个答案都不合
加上前面一个答案也不合 可以排除那个数目。
Part 2.
定义 a为某数使得 1.99<a<2
定义M为大于1.99^k的最小整数
当k够大时 会有 M < (2-a)a^(k+1)
接下来要证明B无法排除 S={1,2,...,M} 中任何一个数
定义b_i为 S中目前连续i次 答案不符合现状的数字的个数
因此 b_0 + b_1 + b_2 + ... + b_k + ... = M
现在A回答问题，使下列和最小:
b_0 + a b_1 + a^2 b_2 +... + a^k b_k + ...
假设A回答n次问题后 此和为s_n
我们可以证明不变量：s_n < M/(2-a)
当n=0时 s_0 = M < M/(2-a) 此不等式成立
n->n+1:
因为A回答是跟回答否
新的两种 b_0 + a b_1 + a^2 b_2 +... + a^k b_k + ...总和刚好是
M + a (b_0 + a b_1 + a^2 b_2 +... + a^k b_k + ... ) (旧的b_0,b_1,b_2,...)
因此
s_{n+1} < M/2 + a/2 s_n < M/2 + 1/2 M/(2-a) = M/(2-a)
故此不等式永久成立
而根据我们的选择 M/(2-a) < a^(k+1)
故b_i=0 for all i >= k+1 永远成立
因此任何一个在S中的数字 都不能被排除可能性
B无法保证获胜