似乎这个题仍然比较简单。（但我仍然不会 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.