TOAD 4 - Vacancy

似乎这个题仍然比较简单。（但我仍然不会 233）

Problem

有一个只包含正整数的多重集 \(S\) ，A 和 B 博弈。每次 A 把 \(S\) 分成两个多重集 \(C_1, C_2\) ，B 可以：

1. 令 \(S\) 为 \(C_1\) ，并把 \(S\) 里的所有元素减一
2. 令 \(S\) 为 \(C_2\) ，并把 \(S\) 里的所有元素减一

若某时刻 \(S\) 为空集，则 \(B\) 胜利，游戏结束。若某时刻 \(S\) 中存在一个 0 ，则 A 获胜。

求两人获胜的条件。

Solution

我们令 \[\phi(S) = \sum_{x \in S} 2^{-x}\]

则 A 胜利的条件是 \(\phi(S) \geq 1\) ，否则 B 胜利。

首先我们可以很容易得到： \[\phi(S) = \phi(C_1) + \phi(C_2)\]

若 \(\phi(S) < 1\) ，则 \(\min(\phi(C_1) + \phi(C_2)) < \frac{1}{2}\) ，B 只需选择较小的那个即可。胜利条件不改变。

若 \(\phi(S) \geq 1\) ，我们要证明一定存在 \(S\) 可以分成两个集合 \(C_1, C_2\) 使得 \(\phi(C_1), \phi(C_2)\) 均不小于 \(\frac{1}{2}\) 。由于 \(\phi(S)\) 是由若干个 2 的负幂加起来，所以一定存在一个 \(S\) 的子集 \(C\) ，使得 \(\phi(C) = 1\) 。我们证明 \(C\) 可以分成两个相等的集合即可。

对 \(\|C\|\) 用数学归纳法。

\(C\) 中存在两个元素显然是可行的。

否则，易知 \(C\) 中最小的两个元素必定是相等的。我们把这两个元素合成一个小 1 的元素，则 \(\phi(C)\) 不变，元素个数少了 1 。有归纳法知必定有解。Q.E.D.