MathLabs

第3题

在说谎猜数游戏中，A 选择满足 1≤x≤N1\le x\le N 的整数 xx 并告诉 B 整数 NN。B 可询问任意正整数集合 DD，问题是“xx 是否属于 DD？”。A 每次可以如实或说谎回答，但任意连续 k+1k+1 个回答中至少有一个必须真实。经过有限次询问后，B 指定一个至多含 nn 个正整数的集合 XX；若 x∈Xx\in X 则 B 获胜。证明：(a) 若 n≥2kn\ge2^k，B 可以保证获胜；(b) 对充分大的每个 kk，存在 n≥1.99kn\ge1.99^k 使任何策略都不能保证获胜。
第 1/3 步：把回答改写为候选集合
上一步下一步
通俗地说

真实回答表示 x 属于所选集合，说谎回答表示 x 属于其补集；因此每个连续 k+1 个回答对应的集合并必须覆盖真实的 x。

Pj∈{Dj,Djc},x∈Pj∪⋯∪Pj+kP_j\in\{D_j,D_j^c\},\qquad x\in P_j\cup\cdots\cup P_{j+k}
详细分析

对第 j 个问题设 B 的集合为 DjD_j；若 A 回答是，则令 PjP_j 为 DjD_j，若回答否，则令 P_j 为 DjcD_j^c。每连续 k+1k+1 个回答中至少一个真实，因此未知的 x 对每个 j 都属于 Pj∪⋯∪Pj+kP_j\cup\cdots\cup P_{j+k}。