算法导论B.1 Exercises 答案

发表于 2022-12-05 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 2.9k 阅读时长 ≈ 3 分钟

B.1-1

B.1-2

考虑使用数学归纳法进行证明。

已知两个集合下的德摩根律$\overline{B\cap C}=\overline{B}\cup\overline{C},\overline{B\cup C}=\overline{B}\cap \overline{C}$是成立的。

那么假设$\overline{A_1\cap A_2\cap\dots\cap A_n}=\overline{A_1}\cup\overline{A_2}\cup\dots\cup\overline{A_n}$成立，考虑如下等式：

$\begin{aligned}
\overline{A1\cap A_2\cap\dots\cap A_n\cap A{n+1}}&=\overline{(A1\cap A_2\cap\dots\cap A_n)\cap A{n+1}}\
&=\overline{A1\cap A_2\cap\dots\cap A_n}\cup \overline{A{n+1}}\
&=\overline{A1}\cup\overline{A_2}\cup\dots\cup\overline{A_n}\cup \overline{A{n+1}}
\end{aligned}$

因此对于$n+1$的情况成立。

假设$\overline{A_1\cup A_2\cup\dots\cup A_n}=\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_n}$成立，考虑如下等式：

$\begin{aligned}
\overline{A1\cup A_2\cup\dots\cup A_n\cup A{n+1}}&=\overline{(A1\cup A_2\cup\dots\cup A_n)\cup A{n+1}}\
&=\overline{A1\cup A_2\cup\dots\cup A_n}\cap \overline{A{n+1}}\
&=\overline{A1}\cap\overline{A_2}\cap\dots\cap\overline{A_n}\cap \overline{A{n+1}}
\end{aligned}$

因此对于$n+1$的情况同样也成立。

$\star$ B.1-3

此处使用一个临时符号$\mathbb{N}_n^+$表示正整数集合${1,2,3,\dots,n}$。

考虑使用数学归纳法证明这个定理。

当$n=2$时，容斥原理$|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|$成立。

当$n>1$时，假设$n-1$的情况成立，也就是有：

$\displaystyle{\left |\bigcup{i=1}^{n-1} A_i\right|=\sum{S \subseteq \mathbb{N}{n-1}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap{i\in S}A_i\right|}$

现在考虑证明$n$的情况，那么有

$\begin{aligned}
\left |\bigcup{i=1}^{n} A_i\right|&=\left |\left(\bigcup{i=1}^{n-1} Ai\right) \cup A_n\right|\
&=\left |\bigcup{i=1}^{n-1} Ai\right|+|A_n|-\left |\left(\bigcup{i=1}^{n-1} Ai\right) \cap A_n\right|\
&=\left |\bigcup{i=1}^{n-1} Ai\right|+|A_n|-\left |\bigcup{i=1}^{n-1} (Ai \cap A_n)\right|&\qquad(A)\
&=\sum{S \subseteq \mathbb{N}{n-1}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap{i\in S}Ai\right|+|A_n|-\sum{S \subseteq \mathbb{N}{n-1}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap{i\in S\cup{n}}Ai\right|&\
&=\sum{S \subseteq \mathbb{N}{n-1}^+,S\neq \varnothing}\left( (-1)^{|S|+1}\cdot \left|\bigcap{i\in S}Ai\right|+ (-1)^{|S|+1+1}\cdot \left|\bigcap{i\in S\cup{n}}Ai\right|\right) +|A_n|\
&=\sum{S \subseteq \mathbb{N}{n}^+,S\neq \varnothing,S\neq {n}}\left( (-1)^{|S|+1}\cdot \left|\bigcap{i\in S}Ai\right|\right) +|A_n|&\qquad(B)\
&=\sum{S \subseteq \mathbb{N}{n}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap{i\in S}A_i\right|
\end{aligned}$

因此$n$的情况也成立。

其中，步骤$(A)$使用了分配律，步骤$(B)$则是将$\mathbb{N}{n-1}^{+}$的所有非空子集，都添加上一个元素$n$后，和原来的$\mathbb{N}{n-1}^{+}$的所有非空子集，共同组成$\mathbb{N}_{n}^{+}$的所有非空子集（除了集合${n}$）。

B.1-4

假设奇数集合是$O$，那么定义一个从集合$\mathbb{Z}$到$O$的映射$f(k)$：

$f(k)=2k+1$

在集合$\mathbb{Z}$中的每个元素恰好能映射到$O$中的每个元素。由于集合$\mathbb{Z}$是可数的，因此集合$O$也是可数的。

B.1-5

对于一个集合$S$中的任何元素$x$，它在$S$的每一个子集中，都存在$2$个选择：出现在这个子集，或者是不出现在这个子集。

对于集合$S$中的$|S|$个元素，它们都有着平等的选择。只要存在一个元素的选择不一样，那么最终产生的子集也不一样。因此，$S$的幂集的大小为$2^{|S|}$。

B.1-6

当$n=1$时，元组$b_1=(a_1)$。

当$n>1$时，元组$b{n-1}=(a_1,a_2,\dots,a{n-1})$已经定义，在$b_{n-1}$后面再多添加一个元素$a_n$即可形成$b_n$，即

$bn=(b{n-1},an)=((a_1,a_2,\dots,a{n-1}),an)=(a_1,a_2,\dots,a{n-1},a_n)$