※ 引述《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无法保证获胜 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 24.61.21.64 ※ 编辑: Dawsen 来自: 24.61.21.64 (07/14 14:12) ※ 编辑: Dawsen 来自: 24.61.21.64 (07/14 14:14) ※ 编辑: Dawsen 来自: 24.61.21.64 (07/14 14:23) ※ 编辑: Dawsen 来自: 24.61.21.64 (07/14 14:24) ※ 编辑: Dawsen 来自: 24.61.21.64 (07/14 14:26)