Re: [問題] IMO 2012 in Argentina Day 1
※ 引述《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)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：