※ 引述《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)