Problem

有两个多重集 $A, B$ ，每个多重集内有 $n$ 个元素，所有元素都是 1 到 $n$ 之间的整数。

求证：一定存在两个多重集 $a \subseteq A, b \subseteq B$ ，使得 $\sum_{x \in a} x = \sum_{y \in b} y$

Solution

如果 $\sum_{x \in A} x = \sum_{y \in B} y$ 那么找到一组解了。否则不妨设 $\sum_{x \in A} < \sum_{y \in B}$ 。令 $p$ 为序列化 $A$ 后的前缀和， $q$ 为序列化 $B$ 后的前缀和。我们有对于每个 $i$ ，均存在一个 $j$ 满足 $p_i = q_j + R_i \quad (0 \leq R_i < n)$ 。如果某个 $R_i$ 为 0 则找到一组解了，否则 $\forall 1 \leq i \leq n, 0 < R_i < n$ ，所有可能的 $R_i$ 只有 $n - 1$ 种，而 $R$ 有 $n$ 个元素。因此必定存在 $R_l = R_r (l < r)$ 。由 $R$ 的定义知： $p_l - q_{j_l} = R_l = R_r = p_r - q_{j_r}$ ，可得 $p_r - p_l = q_{j_r} - q_{j_l}$ 。由 $p$ 和 $q$ 的定义可以发现找到一组解了。

nonsense

TeX 里 $\in$ 是 \in，那么 $\ni$ 是啥呢……居然是 \ni →_→

想起了 bash 里面 if 的结束是 fi 。