整数区间覆盖定理：基于二项幂与余项的构造

命题陈述

对于任意整数 $c_i > 0$，定义拆分序列 $S = \{2^0, 2^1, 2^2, \dots, 2^k, R\}$，其中：

1. $k$ 为满足 $2^{k+1} - 1 \le c_i$ 的最大整数；
2. $R = c_i - (2^{k+1} - 1)$。

命题： 利用集合 $S$ 中的元素进行加法组合，可以表示出 $[0, c_i]$ 区间内的任意整数 $x$。

证明过程

1. 引理：二进制幂的完备性

引理： 集合 $S_{base} = \{2^0, 2^1, \dots, 2^k\}$ 可以唯一表示 $[0, 2^{k+1}-1]$ 范围内的所有整数。

证明（利用归纳法）：

• 基础步骤：当 $k=0$ 时，$S_{base}=\{1\}$，可表示 $[0, 1]$；
• 归纳假设：假设 $\{2^0, \dots, 2^{k-1}\}$ 可以表示 $[0, 2^k-1]$ 的所有整数。
• 归纳步骤：对于任意 $x \in [0, 2^{k+1}-1]$：
  • 若 $x \le 2^k - 1$，由归纳假设可知其可被 $\{2^0, \dots, 2^{k-1}\}$ 表示。
  • 若 $x \ge 2^k$，则 $x' = x - 2^k \in [0, 2^k - 1]$。由归纳假设，$x'$ 可被表示，故 $x = x' + 2^k$ 可由 $\{2^0, \dots, 2^{k-1}, 2^k\}$ 表示。
  • 证毕。

2. 剩余值 R 的覆盖证明

现需证明对于 $x \in [2^{k+1}, c_i]$，该区间内的所有整数均可被表示。

根据 $R$ 的定义，$R = c_i - (2^{k+1} - 1)$，即 $c_i = (2^{k+1} - 1) + R$。

对于任意 $x \in [2^{k+1}, c_i]$，我们令 $x' = x - R$。

• 由于 $x \le c_i$，则 $x' = x - R \le c_i - R = 2^{k+1} - 1$。
• 由于 $x \ge 2^{k+1}$ 且 $R < 2^{k+1}$（若 $R \ge 2^{k+1}$，则 $k$ 的取值将更大，与定义矛盾），故 $x' = x - R \ge 2^{k+1} - 2^{k+1} = 0$。

因此，$x' \in [0, 2^{k+1} - 1]$。根据引理 1，该范围内的任何整数均可由 $S_{base}$ 组合表示。

结论

通过上述证明，我们得出：

1. 区间 $[0, 2^{k+1}-1]$ 由二进制基 $\{2^0, \dots, 2^k\}$ 覆盖；
2. 区间 $[2^{k+1}, c_i]$ 通过 $R$ 加上区间 $[0, c_i-R]$ 内的数进行覆盖，而 $[0, c_i-R]$ 是 $[0, 2^{k+1}-1]$ 的子集。

因此，集合 $\{2^0, 2^1, \dots, 2^k, R\}$ 是 $[0, c_i]$ 的完备基。