“欺诈猜数游戏”在两个玩家甲和乙之间进行，游戏依赖于两个甲和乙都知道的正整数 $k$ 和 $n$．
游戏开始时甲先选定两个整数 $x$ 和 $N$，$1\leqslant x\leqslant N$．甲如实告诉乙 $N$ 的值，但对 $x$ 守口如瓶．乙现在试图通过如下方式的提问来获得关于 $x$ 的信息：每次提问，乙任选一个由若干正整数组成的集合 $S$（可以重复使用之前提问中使用过的集合），问甲“$x$ 是否属于 $S$？”乙可以提任意数量的题．在乙每次提问之后，甲必须对乙的提问立刻回答“是”或“否”，甲可以说谎话，并且说谎的次数没有限制，唯一的限制是甲在任意连续 $k +1$ 次回答中至少有一次回答是真话．
在乙问完所有想问的问题之后，乙必须指出一个至多包含 $n$ 个正整数的集合 $X$，若 $x$ 属于 $X$，则乙获胜；否则甲获胜．证明：
（1）若 $n\geqslant 2^k$，则乙可保证获胜；
（2）对所有充分大的整数 $k$，存在整数 $n\geqslant 1.99^k$，使得乙无法保证获胜．（加拿大）
游戏开始时甲先选定两个整数 $x$ 和 $N$，$1\leqslant x\leqslant N$．甲如实告诉乙 $N$ 的值，但对 $x$ 守口如瓶．乙现在试图通过如下方式的提问来获得关于 $x$ 的信息：每次提问，乙任选一个由若干正整数组成的集合 $S$（可以重复使用之前提问中使用过的集合），问甲“$x$ 是否属于 $S$？”乙可以提任意数量的题．在乙每次提问之后，甲必须对乙的提问立刻回答“是”或“否”，甲可以说谎话，并且说谎的次数没有限制，唯一的限制是甲在任意连续 $k +1$ 次回答中至少有一次回答是真话．
在乙问完所有想问的问题之后，乙必须指出一个至多包含 $n$ 个正整数的集合 $X$，若 $x$ 属于 $X$，则乙获胜；否则甲获胜．证明：
（1）若 $n\geqslant 2^k$，则乙可保证获胜；
（2）对所有充分大的整数 $k$，存在整数 $n\geqslant 1.99^k$，使得乙无法保证获胜．（加拿大）
【难度】
【出处】
2012年第53届IMO试题
【标注】
【答案】
略
【解析】
（1）我们将问题改述如下：甲选定一个有限集 $T$ 和其中一个元素 $x$，将 $T$ 告诉乙，但乙不知道 $x$，乙每次任选一个 $T$ 的子集 $S$，问甲："是否 $x\in S$？"．甲回答"是"或"否"，甲至多连续说 $k$ 次说谎．如果在有限次提问后，乙可指定 $T$ 的一个 $n$ 元子集，使得 $x\in T$，则乙获胜．
我们只需说明当 $|T|>2^k$ 时，乙总可确定某个 $y\in T$，使得 $y\ne x$，这样乙总可以将 $x$ 的范围缩小到 $2^k$ 个数中．乙采取如下策略，不妨将 $T$ 的其中 $2^k+1$ 个元素记为 $\{0,1,\cdots,2^k-1,2^k\}$．乙先反复问："是否 $x\in\{2^k\}$？"，若甲连续 $k+1$ 次回答"否"，则可确定 $x\ne 2
^k$．
如果甲有一次回答"是"，从这次回答之后，乙依次对 $i=1,2,\cdots,k$，问："是否 $x\in\{t\in\mathbb{Z}|0\leqslant t<2^k$，且 $x$ 的二进制表示中 $2^{i-1}$ 的系数为 $0\}$？"
不论甲对这 $k$ 个问题的回答如何，恰存在一个 $y\in\{0,1,\cdots,2^k-1\}$，使得若 $x=y$，则这 $k$ 个回答皆为谎言，连同之前的一次回答，甲便连续撒谎 $k+1$ 次，故 $y\ne x$．
（2）我们证明对任意 $1<\lambda<2$，如果 $n=[(2-\lambda)\lambda^{k+1}]-1$，则乙无法保证获胜．特别地，取定一个 $\lambda$ 满足 $1.99<\lambda<2$，对充分大的整数 $k$，有 $n=[(2-\lambda)\lambda^{k+1}]-1>1.99^k$，既得所要结论．
甲选取 $T=\{1,2,\cdots,n+1\}$，以及任选 $x\in T$，对甲的一组回答，记 $m_i$ 为假设 $x=i$ 时，甲的回答中包含最后一个回答的连续说谎次数的最大值．甲的策略如下：每次在两种回答中选择使得 $\phi\displaystyle =\sum\limits_{i=1}^{n+1}\lambda^{m_i}$ 较小的那个答案．我们说明甲按此方式回答，任何时候总有 $\phi<\lambda^{k+1}$，从而每个 $m_i\leqslant k$，特别有 $m_x\leqslant k$，即甲至多说谎 $k$ 次，并且乙在假设 $x=i$ 时，甲的回答仍是合法的，即乙在任意有限次提问后无法确定任何一个 $i\in T$ 是否不等于 $x$，从而乙不能保证获胜．
下面证明 $\phi<\lambda^{k+1}$，一开始各 $m_i=0,\phi=n+1<\lambda^{k+1}$．假设若干次回答后 $\phi<\lambda^{k+1}$，现乙问："是否 $x\in S$？"，回答"是"或者"否"分别产生的两个 $\phi$ 值为
$\displaystyle \phi_1=\sum\limits_{i\in S}1+\sum_{i\not\in S}\lambda^{m_i+1}$
和 $\displaystyle \phi_2=\sum\limits_{i\not\in S}1+\sum_{i\in S}\lambda^{m_i+1}$
由定义
$\begin{aligned}
&\phi=\min(\phi_1,\phi_2)\\
&\leqslant \dfrac{1}{2}(\phi_1+\phi_2)\\
&=\dfrac{1}{2}(\lambda\phi+n+1)\\
&<\dfrac{1}{2}(\lambda^{k+2}+(2-\lambda)\lambda^{k+1})=\lambda^{k+1}
\end{aligned}$
结论证毕．
我们只需说明当 $|T|>2^k$ 时，乙总可确定某个 $y\in T$，使得 $y\ne x$，这样乙总可以将 $x$ 的范围缩小到 $2^k$ 个数中．乙采取如下策略，不妨将 $T$ 的其中 $2^k+1$ 个元素记为 $\{0,1,\cdots,2^k-1,2^k\}$．乙先反复问："是否 $x\in\{2^k\}$？"，若甲连续 $k+1$ 次回答"否"，则可确定 $x\ne 2
^k$．
如果甲有一次回答"是"，从这次回答之后，乙依次对 $i=1,2,\cdots,k$，问："是否 $x\in\{t\in\mathbb{Z}|0\leqslant t<2^k$，且 $x$ 的二进制表示中 $2^{i-1}$ 的系数为 $0\}$？"
不论甲对这 $k$ 个问题的回答如何，恰存在一个 $y\in\{0,1,\cdots,2^k-1\}$，使得若 $x=y$，则这 $k$ 个回答皆为谎言，连同之前的一次回答，甲便连续撒谎 $k+1$ 次，故 $y\ne x$．
（2）我们证明对任意 $1<\lambda<2$，如果 $n=[(2-\lambda)\lambda^{k+1}]-1$，则乙无法保证获胜．特别地，取定一个 $\lambda$ 满足 $1.99<\lambda<2$，对充分大的整数 $k$，有 $n=[(2-\lambda)\lambda^{k+1}]-1>1.99^k$，既得所要结论．
甲选取 $T=\{1,2,\cdots,n+1\}$，以及任选 $x\in T$，对甲的一组回答，记 $m_i$ 为假设 $x=i$ 时，甲的回答中包含最后一个回答的连续说谎次数的最大值．甲的策略如下：每次在两种回答中选择使得 $\phi\displaystyle =\sum\limits_{i=1}^{n+1}\lambda^{m_i}$ 较小的那个答案．我们说明甲按此方式回答，任何时候总有 $\phi<\lambda^{k+1}$，从而每个 $m_i\leqslant k$，特别有 $m_x\leqslant k$，即甲至多说谎 $k$ 次，并且乙在假设 $x=i$ 时，甲的回答仍是合法的，即乙在任意有限次提问后无法确定任何一个 $i\in T$ 是否不等于 $x$，从而乙不能保证获胜．
下面证明 $\phi<\lambda^{k+1}$，一开始各 $m_i=0,\phi=n+1<\lambda^{k+1}$．假设若干次回答后 $\phi<\lambda^{k+1}$，现乙问："是否 $x\in S$？"，回答"是"或者"否"分别产生的两个 $\phi$ 值为
$\displaystyle \phi_1=\sum\limits_{i\in S}1+\sum_{i\not\in S}\lambda^{m_i+1}$
和 $\displaystyle \phi_2=\sum\limits_{i\not\in S}1+\sum_{i\in S}\lambda^{m_i+1}$
由定义
$\begin{aligned}
&\phi=\min(\phi_1,\phi_2)\\
&\leqslant \dfrac{1}{2}(\phi_1+\phi_2)\\
&=\dfrac{1}{2}(\lambda\phi+n+1)\\
&<\dfrac{1}{2}(\lambda^{k+2}+(2-\lambda)\lambda^{k+1})=\lambda^{k+1}
\end{aligned}$
结论证毕．
答案
解析
备注
