TOAD 24 - Fair Shares?

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\) 是 ，那么 \(\ni\) 是啥呢……居然是 →_→

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