Title

有 $n$ 个红色骰子和 $n$ 个蓝色骰子，每个骰子有 $n$ 个面并标有 $1$ - $n$ 的点数，抛掷这 $2n$ 个骰子，试证：其中某些红色骰子的点数之和等于某些蓝色骰子的点数之和.

Proof

这个问题等价于：有两个长度都为 $n$ 的序列 $(a_{i}^{})_{i=1}^{n}$ 和 $(b_{i}^{})_{i=1}^{n}$，对于一切 $1 \leq i \leq n$，有 $1 \leq a_i,\ b_i \leq n$，那么存在序列 $(a_i)_{i=1}^{n}$ 的若干项和序列 $(b_i)_{i=1}^{n}$ 的若干项之和相等.

我们不妨来证明一个更强的命题：就是序列 $\{a\}$ 的连续若干项与序列 $\{b\}$ 的连续若干项之和相等.

不妨构造原来两个序列的部分和序列：

$$A_k=\sum_{i=1}^{k} a_i \\ B_k=\sum_{i=1}^{k} b_i \\ \text{where}\quad 1 \leq k \leq n$$

显然这两个部分和序列是严格递增的，且不失一般性，假设 $A_n \geq B_n$. 对于一切 $1 \leq k \leq n$，定义 $q_{k}^{} \geq 0$ 如下：

$$q_{k}^{}=\max \{i \mid A_{k}^{} \geq B_{i}^{}\}$$
注意到由于我们假设 $A_{n}^{} \geq B_{n}^{}$，因此此定义对于一切 $k$ 都是良定义的.

于是我们来考虑序列 $(A_{k}^{}-B_{q_k})_{k=1}^{n}$，易知此序列长度为 $n$，且每一项数值都不大于 $n$；后者是非常重要的性质，但我们仍不难证明：

假设存在某个 $k$ 使得 $A_{k}^{}-B_{q_k} > n$，而我们注意到 $1 \leq b_i \leq n$，从而我们可以在指标 $q_{k}^{}$ 的基础上再加 $1$ ，得到 $A_{k}^{}-B_{q_k+1} \geq 0$，那么这就与 $q_{k}^{}$ 的定义矛盾；所以，$A_{k}^{}-B_{q_k} \leq n$ 必成立.

  1. 若存在某个 $k$，使得 $A_{k}^{}-B_{q_k} =0$，那么序列 $\{a\}$ 的前 $k$ 项与序列 $\{b\}$ 的前 $q_k$ 项之和相等；

  2. 若不存在这样的 $k$，那么由抽屉原理可知，长度为 $n$ 的序列 $(A_{k}^{}-B_{q_k})_{k=1}^{n}$ 只有 $n-1$ 个取值， 那么必定有两项，不妨记为 $A_{k_1}^{}-B_{q_{k_1}}$ 和 $A_{k_2}^{}-B_{q_{k_2}}$，具有相同的取值；

    即，$A_{k_1}^{}-B_{q_{k_1}} = A_{k_2}^{}-B_{q_{k_2}}$，从而有

    $$A_{k_1}-A_{k_2} = B_{q_{k_1}}-B_{q_{k_2}}$$

    也即，原序列 $\{a\}$ 的第 $k_{1}^{}+1$ 至 第 $k_{2}^{}$ 项之和等于 序列 $\{b\}$ 的第 $q_{k_{1}}^{}+1$ 至 第 $q_{k_{2}}^{}$ 项之和

综上所述，命题得证.

Q.E.D.

Title 2

第一行有 $19$ 个不大于 $88$ 的自然数，第二行有 $88$ 个不大于 $19$ 的自然数，称同一行的连续若干个数（至少一个）为 “一段”，试证：可以从两行中各取一段，使得这两段中各自之和相等.

Proof of Title 2

设第一行为序列 $(a_{i}^{})_{i=1}^{19}$，第二行为 $(b_{i}^{})_{i=1}^{88}$

不妨构造原来两个序列的部分和序列：

$$A_j=\sum_{i=1}^{j} a_i \\ B_k=\sum_{i=1}^{k} b_i \\ \text{where}\quad 1 \leq j \leq 19,\ 1 \leq k \leq 88$$

显然这两个部分和序列是严格递增的，且不失一般性，假设 $A_{19} \geq B_{88}$. 对于一切 $1 \leq j \leq 19$，定义 $q_{j}^{} \geq 0$ 如下：

$$q_{k}^{}=\max \{i \mid A_{j}^{} \geq B_{i}^{}\}$$
注意到由于我们假设 $A_{19}^{} \geq B_{88}^{}$，因此此定义对于一切 $j$ 都是良定义的.

于是我们来考虑序列 $(A_{j}^{}-B_{q_j})_{j=1}^{19}$，易知此序列长度为 $19$，且每一项数值都不大于 $19$；后者是非常重要的性质，但我们仍不难证明：

假设存在某个 $j$ 使得 $A_{j}^{}-B_{q_j} > 19$，而我们注意到 $1 \leq b_i \leq 19$，从而我们可以在指标 $q_{j}^{}$ 的基础上再加 $1$ ，得到 $A_j^{}-B_{q_j+1} \geq 0$，那么这就与 $q_{j}^{}$ 的定义矛盾；所以，$A_{j}^{}-B_{q_j} \leq 19$ 必成立.

  1. 若存在某个 $j$，使得 $A_{j}^{}-B_{q_j} =0$，那么序列 $\{a\}$ 的前 $j$ 项与序列 $\{b\}$ 的前 $q_j$ 项之和相等；

  2. 若不存在这样的 $j$，那么由抽屉原理可知，长度为 $19$ 的序列 $(A_{j}^{}-B_{q_j})_{j=1}^{n}$ 只有 $19-1=18$ 个取值， 那么必定有两项，不妨记为 $A_{j_1}^{}-B_{q_{j_1}}$ 和 $A_{j_2}^{}-B_{q_{j_2}}$，具有相同的取值；

    即，$A_{j_1}^{}-B_{q_{j_1}} = A_{j_2}^{}-B_{q_{j_2}}$，从而有

    $$A_{j_1}-A_{j_2} = B_{q_{j_1}}-B_{q_{j_2}}$$

    也即，原序列 $\{a\}$ 的第 $j_{1}^{}+1$ 至 第 $j_{2}^{}$ 项之和等于 序列 $\{b\}$ 的第 $q_{j_{1}}^{}+1$ 至 第 $q_{j_{2}}^{}$ 项之和

综上所述，命题得证.

Q.E.D.

Title 3

给定正整数 $m$, $n$，设 $x_{1}^{}$, $x_{2}^{}$, $x_{3}^{}$, $\ldots$, $x_{m}^{}$ 都是正整数，且它们的算术平均值小于 $n+1$，又 $y_{1}^{}$, $y_{2}^{}$, $y_{3}^{}$, $\ldots$, $y_{n}^{}$ 都是正整数，且它们的算术平均值小于 $m+1$，试证：存在若干个（至少一个） $x_{i}^{}$ 的和与若干个 $y_{i}^{}$ 的和相等.

Proof

构造部分和序列 $s_{j}^{}=\sum_{i=1}^{j}x_{i}^{}$，其中 $1 \leq j \leq m$；以及，$t_{k}^{}=\sum_{i=1}^{k}y_{i}^{}$，其中 $1 \leq k \leq n$.

因为题设中关于算术平均值的约束，我们有 $s_{m}^{} < m(n+1)$ 以及 $t_{m}^{} < n(m+1)$.

如果 $s_{m}^{}=t_{n}^{}$，那么命题自然成立.

若不然，我们不失一般性地假设 $s_{m}^{}>t_{n}^{}$. 我们构造这样的二元组 $(s_{j}^{}, t_{k}^{})$，其中 $0\leq j \leq m-1， \ 0 \leq k \leq n$，即共有 $m(n+1)>s_m$ 个二元组，由抽屉原理可知，存在两个不同的二元组 $(s_j,t_k)$, $(s_{j'},t_{k'})$ 使得

$$s_j+t_k \equiv s_{j'}+t_{k'} \mod s_m$$
即
$$s_j-s_{j'} \equiv t_{k'}-t_k \mod s_m$$
不妨假设 $k' \geq k$，因为 $\lvert s_j - s_{j'} \rvert < s_m$，且 $0 \leq t_{k'}-t_k \leq t_n < s_m$，所以 $t_{k'}-t_k > 0$.

于是，$s_j-s_{j'} = t_{k'}-t_k$ 或者 $s_j-s_{j'}+s_m= t_{k'}-t_k$.

对于前者，有

$$\sum_{i=j'+1}^{j}x_i = \sum_{i=k+1}^{k'}y_i$$
对于后者，有
$$\sum_{i=1}^{j}x_i+\sum_{i=j'+1}^{m}x_i=\sum_{i=k+1}^{k'}y_i$$
综上所述，命题得证.

Q.E.D.

≡