接上次的日志，先重复一下谜题：
欺诈猜数游戏在甲和乙之间进行，甲和乙都知道正整数 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 的可能范围。证毕！