接上次的日志，先重复一下谜题：

欺诈猜数游戏在甲和乙之间进行，甲和乙都知道正整数 $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$ 的可能范围。证毕！