1问题
0.10 证明每个包含两个或更多节点的图都包含两个度数相等的节点。
0.11 找出以下证明所有马匹颜色相同中的错误。
主张：在任何由 $h$ 匹马组成的集合中，所有马匹的颜色都相同。
证明：通过对 $h$ 进行归纳。
基础：对于 $h=1$。在任何只包含一匹马的集合中，所有马匹的颜色显然相同。
归纳步骤：对于 $k \geq 1$，假设该主张对于 $h=k$ 成立，并证明它对于 $h=k+1$ 成立。取任意一个由 $k+1$ 匹马组成的集合 $H$。我们证明此集合中的所有马匹颜色都相同。从该集合中移走一匹马，得到一个只有 $k$ 匹马的集合 $H_{1}$。根据归纳假设， $H_{1}$ 中的所有马匹颜色都相同。现在放回移走的马，并移走另一匹不同的马，得到集合 $H_{2}$。根据同样的论证， $H_{2}$ 中的所有马匹颜色都相同。因此， $H$ 中的所有马匹颜色都必须相同，证明完成。
0.12 设 $S(n)=1+2+\cdots+n$ 是前 $n$ 个自然数的和，设 $C(n)=1^{3}+2^{3}+\cdots+n^{3}$ 是前 $n$ 个立方数的和。通过对 $n$ 进行归纳，证明以下等式，从而得出有趣的结论：对于每个 $n$， $C(n)=S^{2}(n)$。
a. $S(n)=\frac{1}{2} n(n+1)$。
b. $C(n)=\frac{1}{4}\left(n^{4}+2 n^{3}+n^{2}\right)=\frac{1}{4} n^{2}(n+1)^{2}$。
0.13 找出以下证明 $2=1$ 中的错误。
考虑方程 $a=b$。两边同乘以 $a$ 得到 $a^{2}=a b$。两边同减去 $b^{2}$ 得到 $a^{2}-b^{2}=a b-b^{2}$。现在对两边进行因式分解， $(a+b)(a-b)= b(a-b)$，然后两边同除以 $(a-b)$ 得到 $a+b=b$。最后，令 $a$ 和 $b$ 都等于 1，这表明 $2=1$。
28 章 O / 引言
${ }^{\mathrm{A}}$ 0.14 使用定理 0.25 推导出计算抵押贷款月供金额的公式，该公式以本金 $P$、利率 $I$ 和付款次数 $t$ 表示。假设在完成 $t$ 次付款后，贷款金额减少到 0。使用该公式计算初始贷款金额为 $100,000 美元，年利率为 5\%，30 年抵押贷款（360 次月供）的每月付款金额。
${ }^{\mathrm{A} \star} \mathbf{0 . 1 5}$ 拉姆齐定理。设 $G$ 为一个图。图 $G$ 中的团是其中任意两个节点都由一条边连接的子图。反团，也称为独立集，是其中任意两个节点都不由一条边连接的子图。证明每个包含 $n$ 个节点的图都包含一个至少有 $\frac{1}{2} \log _{2} n$ 个节点的团或反团。
选定解决方案
0.14 我们令 $P_{t}=0$ 并求解 $Y$ 以得到公式： $Y=P M^{t}(M-1) /\left(M^{t}-1\right)$。对于 $P=\$ 100,000, I=0.05$ 和 $t=360$，我们有 $M=1+(0.05) / 12$。我们使用计算器得出月付款约为 $Y \approx \$ 536.82$。
0.15 为两堆节点留出空间： $A$ 和 $B$。然后，从整个图开始，重复地将每个剩余节点 $x$ 添加到 $A$ 中，如果其度数大于剩余节点数量的一半，否则添加到 $B$ 中，并丢弃所有 $x$ 未连接（已连接）到的节点，如果它被添加到 $A(B)$ 中。继续直到没有节点剩下。在这些步骤中的每一步，最多有一半的节点被丢弃，因此在过程终止之前至少会发生 $\log _{2} n$ 步。每一步都会向其中一堆添加一个节点，因此其中一堆最终将至少有 $\frac{1}{2} \log _{2} n$ 个节点。 $A$ 堆包含一个团的节点，$B$ 堆包含一个反团的节点。
