0%

TOAD-puzzle-4

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