Puzzle Toad-4 Vacancy Puzzle

Puzzle Toad-4 Vacancy Puzzle #

题目翻译 #

敬爱的领袖 Aldan 的提前退休给 Zocor 的 Malthusian 市的执政三巨头留下了一个空缺. 现在有两个政党, 肉食爱好者党 (The Meat Lovers Party, MLP) 以及国民素食党 (the Vegetarian Party of the People, VPP) .目前, 在三巨头中, 每一方都有一个代表. MLP 的代表 Arctan 的级别最高, 另一个统治者是 Arcsin . 替代 Aldan 的神秘投票规则如下: 有一个由 $n$ 人构成的大型主席团, 目前所有人都是 VPP 的成员. 每个成员都有一个值为整数的优先级. 现在起选举过程将会一轮一轮地进行: 每一轮的开始, Arcsin 会提名主席团剩余参选人集合 $C$ 的一个子集 $S$ (最开始, $C$ 就是整个主席团), Arctan 有两个选择: 他可以吞噬 $S$ , 但之后必须把 $C \setminus S$ 的每个成员的优先级都减少 $1$ ; 或者, 他可以吞噬 $C \setminus S$ 并且把 $S$ 中每个成员的优先级减少 $1$ . 选举过程会一直持续, 直到出现接下来两种情况之一. 第一种情况是整个主席团都被吞噬了, 这之后 Arctan 可以从他的党派中选一个成员填补 Aldan 的空位; 另一种情况是某个成员的优先级到达 $0$ , 这之后 Arcsin 可以从优先级为 $0$ 的成员中选择一个填补 Aldan 的空位. 假设初始的主席团优先级为 $a_1, a_2, …, a_n$ , 哪个党派最终会竞选成功?

解答 #

结论 #

让我们换一种符号来解决这道题. 我们用 $a(c)$ 来记录参选者 $c\in C$ 的优先级. 事实上, Arctan 能够取胜当且仅当初始情况满足 $$ \phi(C) = \sum_{c\in C}2^{-a(c)} < 1 $$ 我们下面用归纳法来证明这一点. 在竞选过程的最后, 要么 $C=\emptyset$ 且 $\phi(C) = 0$ , Arctan 获胜, 要么 $\exist c\in C$ 满足 $a(c) = 0$ 且 $\phi(C) \geq 1$ , Arcsin获胜.

Arctan 必胜的情况 #

现在考虑竞选过程中的某一步. 记 $\phi’$ 为 Arctan 作出选择后 $\phi$ 函数的新值, 那么有 $$ \phi(C) = \frac{1}{2}\phi’(S) + \frac{1}{2}\phi’(C\setminus S) $$ 因此, 如果 $\phi(C) < 1$ , 必然有 $min{\phi’(S), \phi’(C\setminus S)} < 1$ . 因此, Arctan 总是能够通过合适的选择来保证下一个阶段 $\phi’ < 1$ , 如此反复直到 $C = \emptyset$ , 从而获得最终的胜利.

Arcsin 必胜的情况 #

引理 #

如果 $\phi(C)\geq 1$ , 我们可以应用如下的引理:

• 设 $x_1\geq x_2\geq …\geq x_r, r\geq 2$ 满足 $x_i$ 都是 $2$ 的负幂项, 并且有 $x_1 + x_2 + … + x_r \geq 1$ , 则存在一种把 $x_i$ 划分成两个集合中的划分方式, 使得两个集合的和都 $\geq \frac{1}{2}$ .

引理的应用 #

由此可见, 假如 $\phi(C)\geq 1$ , 那么 Arcsin 一定能找到 $S$ 使得 $min{\phi’(S), \phi’(C\setminus S)} \geq 1$ , 由此归纳, 随着集合大小的不断减少, 总会出现 $c\in C$ 满足 $a(c) = 0$ , 故 Arcsin 总能获胜.

引理的证明 #

下面我们来证明这个引理. 不失一般性, 我们可以假定 $x_1 + x_2 + … + x_r = 1$ . $r = 2$ 时, 引理的正确性是显而易见的. $r \geq 3$ 时, 由于 $x_i$ 都是 $2$ 的负幂, 且 $x_1 + x_2 + … + x_r = 1$ , 故必有 $x_{r - 1} = x_r$ , 在集合划分时, 我们把 $x_{r - 1}$ 和 $x_r$ 放到一个集合里, 可以视作在原序列中用 $x_{r - 1} + x_r$ 代替了 $x_{r - 1}, x_r$ . 这个过程可以不断重复直到只剩下 $2$ 个元素的平凡情况. 这样我们就归纳地构造了合法的划分.

补充 #

本题的出处是 Joel Spencer 的论文 Randomization, Derandomization, and Antirandomization: Three games 中提出的 “Tenure Game” . 该论文发表于 Theoretical Computer Science 131 (1994), 415-430 .