欺诈猜数游戏(下)

接上次的日志,先重复一下谜题: 欺诈猜数游戏在甲和乙之间进行,甲和乙都知道正整数 和 。游戏开始时,甲先选定两个整数 和 ,其中 。甲告诉乙 的值,但对 守口如瓶。乙试图通过提问来获得与 相关的信息:每次提问,乙任选一个由若干正整数组成的集合(可以重复使用之前提问中使用过的集合),问甲“是否属于?”。乙可以提任意数量的问题。每次提问之后,甲立刻回答是或否,甲可以说谎话,但在任意连续 次回答中至少有一次回答是真话。 在乙问完所有想问的问题之后,乙必须指出一个至多包含 个正整数的集合 ,若 属于 ,则乙获胜;否则甲获胜。证明:对所有充分大的整数 ,存在整数 ,使得乙无法保证获胜。 为了解决第二个问题,需要从甲的角度考虑问题,每一次回答问题后,使得乙无法缩小 范围。 为此我们考虑贪心策略:甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点:如果乙每次提问都问“ 是不是 呢?”那甲如果每次只顾眼前利益,应当回答“不是。”但经过 轮之后,甲就能轻松排除 ,从而缩小 的范围。 于是甲的策略必须是一种折中的策略,既要顾及眼前的利益,又不能放弃长期的利益。我们设定 。 于是甲在觉得到底要选择乙提出的集合或是其补集前,对 到 中每个数都进行打分。甲对 的打分是 ,其中 而 满足 在最近连续 次选择的集合中都不出现。根据每个元素的打分,甲在 和 中选择会使得之后整个集合总分较低的那个集合。 为了让证明成立,设定 。下面,我们通过归纳法证明每一次所有元素的总分不超过 。根据打分规则,最开始总分是 ,命题显然那成立。假设目前的总分是 ,乙给出集合 ,如果甲选 ,则总和变为 ,如果甲选 ,则总和变为 。由于甲会选择使得总和变得更小的那个策略,于是他回答后总和至多为 。由于 ,总和小于 。命题成立! 如果 连续 次没有被甲选中,则其得分已经为… Continue reading 欺诈猜数游戏(下)