第一次作业

liblaf2/16/25About 3 min

1.10

Problem

证明任一正整数 $n$ 可唯一地表示成如下形式:

n = \sum_{i ⩾ 1} a_{i} i!, 0 ⩽ a_{i} ⩽ i, i ⩾ 1

Proof

存在性 (构造性证明):

步骤分解: 对于任意正整数 $n$ , 找到最大的整数 $k$ 满足 $k! ⩽ n$ .
确定系数: 令 $a_{k} = ⌊ \frac{n}{k!} ⌋$ , 由于 $k! ⩽ n < (k + 1)!$ , 可得 $a_{k} ⩽ k$ (因为 $\frac{n}{k!} < k + 1$ , 故商 $a_{k} ⩽ k$ ).
递归处理余数: 设余数 $r = n - a_{k} \cdot k!$ , 显然 $r < k!$ . 对余数 $r$ 重复上述步骤, 直到余数为 0.
构造完成: 所有系数 $a_{i}$ 满足 $0 ⩽ a_{i} ⩽ i$ , 且总和为 $n$ .

唯一性 (反证法):
假设存在两种不同的表示:

n = \sum_{i = 1}^{\infty} a_{i} i! = \sum_{i = 1}^{\infty} b_{i} i! (0 ⩽ a_{i}, b_{i} ⩽ i)

且至少存在某个 $i$ 使得 $a_{i} \neq b_{i}$ . 设 $m$ 是最大的下标使得 $a_{m} \neq b_{m}$ . 不妨设 $a_{m} > b_{m}$ , 则:

(a_{m} - b_{m}) m! = \sum_{i = 1}^{m - 1} (b_{i} - a_{i}) i! .

左边至少为 $m!$ , 而右边绝对值不超过:

\sum_{i = 1}^{m - 1} i \cdot i! = m! - 1 (因 \sum_{i = 1}^{k} i \cdot i! = (k + 1)! - 1) .

因此 $m! ⩽ m! - 1$ , 矛盾. 故表示唯一.

1.12

Problem

试证等式: $\sum_{k = 1}^{n} k C (n, k) = n 2^{n - 1}$

Proof

利用二项式定理和求导的方法. 二项式定理给出 $(1 + x)^{n} = \sum_{k = 0}^{n} C (n, k) x^{k}$ .

对两边求导得到 $n (1 + x)^{n - 1} = \sum_{k = 1}^{n} k C (n, k)^{k - 1}$ . 令 $x = 1$ , 左边变为 $n 2^{n - 1}$ , 右边变为 $\sum_{k = 1}^{n} k C (n, k)$ , 即左边表达式等于右边结果.

1.13

Problem

有 $n$ 个不同的整数, 从中取出 2 组来, 要求第一组的最小数大于另一组的最大数, 一共有多少种取法.

Solution

不失一般性, 假设这些整数是 $1, 2, \dots, n$ .

当较小组的最大数为 $i$ 时, 较小组的元素必须包含 $i$ , 并且可以从 $1$ 到 $i - 1$ 中选择任意组合, 因此较小组的组合数为 $2^{i - 1}$ . 较大组的元素必须全部大于 $i$ , 即从 $i + 1$ 到 $n$ 中选择非空组合, 因此较大组的组合数为 $2^{n - i} - 1$ .

我们需要对 $i$ 从 1 到 $n - 1$ 的情况进行求和:

\sum_{i = 1}^{n - 1} 2^{i - 1} \cdot (2^{n - i} - 1)

展开并简化这个和式:

\sum_{i = 1}^{n - 1} (2^{i - 1} \cdot 2^{n - i} - 2^{i - 1}) = \sum_{i = 1}^{n - 1} (2^{n - 1} - 2^{i - 1})

拆分为两个求和式:

\sum_{i = 1}^{n - 1} 2^{n - 1} - \sum_{i = 1}^{n - 1} 2^{i - 1}

第一个求和式共有 $n - 1$ 个 $2^{n - 1}$ , 结果为:

(n - 1) \cdot 2^{n - 1}

第二个求和式为等比数列求和:

\sum_{i = 1}^{n - 1} 2^{i - 1} = 2^{n - 1} - 1

因此, 总和为:

(n - 1) \cdot 2^{n - 1} - (2^{n - 1} - 1) = (n - 2) \cdot 2^{n - 1} + 1

最终答案为:

(n - 2) \cdot 2^{n - 1} + 1

C (k - 1, i) \cdot 9^{k - i} \cdot i

其中, $C (k - 1, i)$ 表示在 $k - 1$ 位中选择 i 个位置放置 0, $9^{k - i}$ 表示非零位的选择方式, i 表示每个数的 0 的个数.

逐位求和
对每个 $k$ (2 到 6) 和 $i$ (1 到 $k - 1$ ) 求和, 得到所有 $k$ 位数中 0 的总数:

\sum_{k = 2}^{6} \sum_{i = 1}^{k - 1} C (k - 1, i) \cdot 9^{k - i} \cdot i

处理特殊值 1,000,000
数字 1,000,000 包含 6 个 0, 需额外加上 6.

最终结果为:

488895