竞赛题变体求证：满足条件的序列可拆分为和相等的两个子序列

首先，我们用数学归纳法来搞定这个问题，甚至可以证明一个更强的命题：对于任意满足 $1 \le a_i \le i$ 的正整数序列 $X = [a_1, a_2, ..., a_n]$，以及任意整数 $t$ 满足 $0 \le t \le \text{sum}(X)$ 且 $t$ 与 $\text{sum}(X)$ 同奇偶，都存在 $X$ 的一个子序列，其和恰好为 $t$。题目要求的 $t = \text{sum}(X)/2$ 显然满足条件，因此原命题直接成立。

基础情况验证 #

• 当 $n=1$ 时：序列只有 $a_1$，且 $a_1 \le 1$，即 $a_1=1$。$\text{sum}(X)=1$，满足条件的 $t$ 是 $0$（空序列）和 $1$（整个序列），显然成立。
• 当 $n=2$ 时：$a_1=1$，$a_2 \le 2$。$\text{sum}(X)=1+a_2$：
  • 若 $\text{sum}(X)$ 为偶数，则 $a_2$ 必为奇数，即 $a_2=1$，此时 $t=1$，可以取子序列 $[a_1]$ 或 $[a_2]$，和为1，完全符合要求；
  • 若 $\text{sum}(X)$ 为奇数，强命题依然成立（比如 $t=0, 3$ 或 $1,2$，都能找到对应子序列）。

归纳假设 #

假设对于所有长度小于 $n$ 的满足条件的序列，上述强命题都成立。

归纳步骤 #

考虑长度为 $n$ 的序列 $X = [a_1, a_2, ..., a_n]$，记前 $n-1$ 个元素的和为 $S'$，整个序列的和为 $S = S' + a_n$，且 $a_n \le n$。

我们需要证明：对于任意 $t$ 满足 $0 \le t \le S$ 且 $t$ 与 $S$ 同奇偶，存在子序列和为 $t$。分两种情况讨论：

1. 情况1：$t \le S'$

   • 如果 $t$ 与 $S'$ 同奇偶：根据归纳假设，前 $n-1$ 个元素中存在子序列和为 $t$，直接取这个子序列即可（不需要包含 $a_n$）。
   • 如果 $t$ 与 $S'$ 不同奇偶：此时 $t + a_n$ 与 $S'$ 同奇偶（因为 $t \equiv S' + a_n \pmod{2}$，两边加 $a_n$ 得 $t + a_n \equiv S' + 2a_n \equiv S' \pmod{2}$）。但更直观的是看补集：$S - t$ 是 $X$ 补集的和，且 $S - t > S'$，直接进入情况2处理。

2. 情况2：$t > S'$
   此时 $t - a_n \le S'$（因为 $t \le S = S' + a_n$），且 $t - a_n$ 与 $S'$ 同奇偶：
   因为 $t$ 与 $S$ 同奇偶，$S = S' + a_n$，所以 $t \equiv S' + a_n \pmod{2}$，即 $t - a_n \equiv S' \pmod{2}$。根据归纳假设，前 $n-1$ 个元素中存在子序列和为 $t - a_n$，将这个子序列加上 $a_n$，就得到了和为 $t$ 的子序列。

综上，两种情况都能找到满足条件的子序列，强命题成立。回到原问题，当 $S$ 为偶数时，取 $t = S/2$，必然存在这样的子序列，其补集的和也是 $S/2$，即序列可拆分为两个等和子序列。

内容的提问来源于stack exchange，提问作者Morgan Zariski