0%

TOAD-puzzle-24

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 。