欺诈猜数游戏(下)

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

欺诈猜数游戏在甲和乙之间进行,甲和乙都知道正整数 \(k\) 和 \(n\)。游戏开始时,甲先选定两个整数 \(x\) 和 \(N\),其中 \(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\)。

于是甲在觉得到底要选择乙提出的集合或是其补集前,对 \(1\) 到 \(n+1\) 中每个数都进行打分。甲对 \(i\) 的打分是 \(a^{m_i}\),其中\(a = 1.999\) 而 \(m_i\) 满足 \(i\) 在最近连续 \(m_i\) 次选择的集合中都不出现。根据每个元素的打分,甲在 \(S\) 和 \(S^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\) 的可能范围。证毕!

5 (this post is made with love)

Leave a Reply