欺诈猜数游戏(下)

上次的日志,先重复一下谜题:

欺诈猜数游戏在甲和乙之间进行,甲和乙都知道正整数 kn。游戏开始时,甲先选定两个整数 xN,其中 1\leq x\leq N。甲告诉乙 N 的值,但对 x 守口如瓶。乙试图通过提问来获得与 x 相关的信息:每次提问,乙任选一个由若干正整数组成的集合S(可以重复使用之前提问中使用过的集合),问甲“x是否属于S?”。乙可以提任意数量的问题。每次提问之后,甲立刻回答是或否,甲可以说谎话,但在任意连续 k+1 次回答中至少有一次回答是真话。

在乙问完所有想问的问题之后,乙必须指出一个至多包含 n 个正整数的集合 X,若 x 属于 X,则乙获胜;否则甲获胜。证明:对所有充分大的整数 k,存在整数 n\geq 1.99^k,使得乙无法保证获胜。

为了解决第二个问题,需要从甲的角度考虑问题,每一次回答问题后,使得乙无法缩小 x 范围。

为此我们考虑贪心策略:甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点:如果乙每次提问都问“x 是不是 1 呢?”那甲如果每次只顾眼前利益,应当回答“不是。”但经过 k+1 轮之后,甲就能轻松排除 1,从而缩小 x 的范围。

于是甲的策略必须是一种折中的策略,既要顾及眼前的利益,又不能放弃长期的利益。我们设定 N=n+1

于是甲在觉得到底要选择乙提出的集合或是其补集前,对 1n+1 中每个数都进行打分。甲对 i 的打分是 a^{m_i},其中a = 1.999m_i 满足 i 在最近连续 m_i 次选择的集合中都不出现。根据每个元素的打分,甲在 SS^c 中选择会使得之后整个集合总分较低的那个集合。

为了让证明成立,设定 n = (2-a)a^{k+1} - 1。下面,我们通过归纳法证明每一次所有元素的总分不超过 a^{k+1}。根据打分规则,最开始总分是 n = (2-a)a^{k+1}-1 < a^{k+1},命题显然那成立。假设目前的总分是 y = \sum_{i=1}^{n+1} a^{m_i},乙给出集合 S,如果甲选 S,则总和变为 y_1 = \sum_{i\in S}1 + \sum_{i\notin S}a^{m_i+1},如果甲选 S^c,则总和变为 y_2 = \sum_{i\notin S}1 + \sum_{i\in S}a^{m_i+1}。由于甲会选择使得总和变得更小的那个策略,于是他回答后总和至多为 \frac{1}{2}(y_1 + y_2) = \frac{1}{2}(ay+n+1)。由于 y < a^{k+1},总和小于 \frac{1}{2}(a\cdot a^{k+1}+(2-a)a^{k+1}) = a^{k+1}。命题成立!

如果 i 连续 k+1 次没有被甲选中,则其得分已经为 a^{k+1}。这不可能,因为总分总是小于 a^{k+1}。也就是说在这样的策略下乙无法缩小 x 的可能范围。证毕!

Leave a Reply

Your email address will not be published. Required fields are marked *