IMO2012试题：说谎者猜谜游戏（这题很难，暂无答案）

　　说谎者猜谜游戏是一个由玩家A和玩家B两个玩家一起玩的游戏. 游戏的规则依赖于玩家A 和玩家B 都知道的两个正整数 k 和 n.　　在游戏开始时, 玩家A 挑选整数 x 和 N 满足

　　说谎者猜谜游戏是一个由玩家A和玩家B两个玩家一起玩的游戏. 游戏的规则依赖于玩家A 和玩家B 都知道的两个正整数 k 和 n.

　　在游戏开始时, 玩家A 挑选整数 x 和 N 满足 1≤x≤N. 玩家A 将 x 保密, 而将 N 告知玩家B. 玩家B 通过如下方式问玩家A问题以获取关于 x 的信息: 每个问题都是由玩家B 任意指定一个正整数组成的集合 S (允许重复出现), 然后问玩家A x 是否属于 S. 玩家B 可以尽可能多地问问题, 问到满意为止. 每个问题问完之后, 玩家A 必须马上回答"是"或者"不是", 但是玩家A 可以撒谎, 唯一的要求是在连续的 k+1 个问题中, 至少保证有一个回答是正确的.

　　在玩家B 问完足够多次以后, 他需要指定一个不超过 n 个元的正整数组成的集合 X. 如果 x 属于 X, 则玩家B 赢; 否则玩家A 赢.

　　(1).如果 n≥2^k, 那么 B 有必胜策略;

　　(2).对足够大的 k, 存在整数 n 满足 n≥(1.99)^k 使得玩家B 不能确保自己必胜.

答案：暂无