具体数学第一章课后习题详解
最近在拜读高老头的大作《具体数学》, 并力所能及地完成习题. 习题的具体步骤将会以 Blog 文章的形式发出来, 就像这篇. 考虑到考试题可能涉及多个章节的内容, 第一遍通读我会先行跳过, 之后再来补上.
由于这一系列 Blog 文章都使用 Typst 排版, 所以网页上的显示效果可能会略差, 请多包涵.
热身题
1.
"标号从 直到 的马都有同样的颜色" 并不能推出 "标号从 直到 的马都有同样的颜色". 实际上, 这直接假定了我们要证明的结论.
2.
考虑到要把整个塔移动到 B 柱, 首先要把最底下的盘移动到 B 柱. 移动最底下的盘时, 必须先移动到中间的柱, 然后将 B 柱上的盘移动回 A 柱, 再将最底下的盘移动到 B 柱. 然后再将剩余的盘移动到 B 柱.
设移动 个盘的最短步数为 , 那么我们有:
这是我们得到的递归式, 为了得到一个封闭形式, 我们可以:
与此同时, 我们也得到了具体的移动策略:
3.
这个题目的描述有些模糊, 我认为应当删除 "在3根桩柱上都" 几个字, 因为这样描述隐含了一种 " 种排列在三根桩柱上各出现一次, 共 次" 的意味, 这样会把研究对象转为 "一根桩柱上的排列", 然而实际上作者要求我们思考的是 个圆盘作为整体, 在三个桩柱上的排列情况.
容易发现 个圆盘的排列方式共有 种, 除去初始状态之外, 剩余的 种排列恰好与上述的最短步长相等. 于是我们只需要说明上述每一步的末状态均不相同. 而这是显而易见的, 因为如果相同, 那么上述步骤就不是最短步骤.
4.
如果以 个圆盘的某种叠放方式为结束状态, 那么
- 当 时, 显然最多只需要 步就能达成, .
-
设当 时, 最多需要 步达成, 那么当 时,
- 若要求最大的圆盘在左侧柱桩, 则同样需要至多 步达成.
- 否则, 需要先把其他圆盘移动到剩余的一个空闲柱桩, 再将最大的圆盘移动到要求位置, 再将剩余圆盘移动到要求位置, 需要至多 步达成.
综上所述, 以 个圆盘的某种叠放方式为结束状态, 至多需要 次移动. 若以 个圆盘的某种叠放方式为开始状态, 则将 "以 个圆盘的某种叠放方式为结束状态" 时得出的步骤倒放即可, 同样至多需要 次移动.
故不存在 个圆盘在 根桩柱上的某种开始叠放或结束叠放, 使得按照卢卡斯原来的规则, 需要多于 次的移动.
5.
根据平面图的 Euler 定理, 对于任意连通图, , 其中 , 则
也即, .
而两个圆之间至多有 个交点, 对于四个圆, 则至多有 个交点, 故至多把平面分成 个面. 因此并不能描述.
6.
至少有 条直线相交才能确定一个有界的区域, 所以对于 条两两相交的直线, 确定的有界区域数 :
故有
7.
第一项不成立.
作业题
8.
多列几项就会发现数列 是以 为周期循环的, 具体来说是
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9.
a.
令 , 则根据 , 有
成立, 故 蕴涵 .
b.
令 = , = , 则由 , 有
又根据 , 有
成立, 故 和 蕴涵 .
c.
成立, 根据 小节 b. 的结论, 对于任意大的 也成立, 再根据 小节 a. 的结论, 对于任意大的 , 都有 在 时成立.
于是 对任意 成立.
10.
实际上 相当于将 个圆盘顺时针移动一个桩柱的最少移动次数, 则是将 个圆盘逆时针移动一个桩柱的最少移动次数.
和 在 时的值显然是 , 因为这不需要任何移动.
若 , 要把 个圆盘顺时针移动一个桩柱, 则需要先把最大的圆盘顺时针移动一个桩柱, 这时 柱必须是空的, 因此首先要把其余 个圆盘逆时针移动一个桩柱, 再将最大的圆盘顺时针移动一个桩柱, 然后再把其余圆盘逆时针移动一个桩柱, 这时其余的圆盘就在 柱上了. 也即 . 所有步骤如下表格
| 步骤 | 步数 |
|
|
剩余的一个盘 |
| 0 |
|
|||
| 1 |
|
|
|
|
| 2 |
|
|
|
|
| 3 |
|
|
若要把 个圆盘逆时针移动一个桩柱, 步骤与上一种情况类似. 首先需要把最大的圆盘逆时针移动一个桩柱, 实际操作时则是顺时针移动两个桩柱, 这就需要 桩柱是空的. 所以首先我们要把其余 个圆盘逆时针移动一个桩柱, 再将最大的圆盘顺时针移动一个桩柱, 接下来我们需要再把最大的圆盘顺时针移动一个桩柱, 这需要第三个桩柱是空的, 所以我们需要把其余 个桩柱先顺时针移动一个桩柱, 再把最大的圆盘顺时针移动一个桩柱, 最后我们需要把其余 个圆盘移动到 桩柱, 所以最终的步骤数为 . 所有步骤如下表格
| 步骤 | 步数 |
|
|
剩余的一个盘 |
| 0 | ||||
| 1 |
|
|
|
|
| 2 |
|
|
|
|
| 3 |
|
|
|
|
| 4 |
|
|
|
|
| 5 |
|
|
11.
a.
考虑到要把整个塔移动到 B 柱, 首先要把最底下的两个盘移动到 B 柱. 移动最底下的盘前, 必须先把其余 个大小的盘移动到另一个柱子, 然后将 A 柱上的两个最大的盘移动到 B 柱, 然后再将剩余的盘移动到 B 柱.
设移动 个尺寸的圆盘的最小步数为 , 则有
这是我们得到的递归式, 为了得到一个封闭形式, 我们可以:
b.
暂时跳过
12.
与 小节 a. 同理, 我们有
这是我们得到的递归式, 为了得到一个封闭形式, 我们可以:
故 .
13.
我们可以构想一个更大的圆把所有 Z 包围, 然后根据平面图的 Euler 定理, 对于任意连通图, 有
这里我们忽略大圆外面的一个面, 所以等式的右侧是1.
关于 和 , 我们可以根据几种不同的交点讨论求出. 经过观察, 交点的类型和对应的度有以下几种:
- Z 和外面大圆的交点: 个, 度为
- Z 自身的两个折点: 个, 度为
- 两个 Z 之间的交点: 个, 度为 (为了让产生的面最多, 我们保证任意两个 Z 的三条线都是相交的)
于是我们有
接下来我们只需要求出 . 经过观察, 我们发现两个 Z 之间最多产生 个交点, 又根据两个 Z 的三条线都相交, 我们可以得知
我们把递归式展开
然后再代入原式
14.
考虑到当我们添加一个新的平面时, 新增的某个多面体不会同时有两个面在这个新的平面上, 因此新增的多面体数实际上等于该平面被其他平面截出的区域数, 也即
15.
根据与正文中问题相同的讨论步骤, 我们有
参考书中的方法, 我们可以设 , 于是递推式可以化成
参考书中的方法, 我们用二进制表示
则
16.
我们可以把通项的形式设为
考虑 , 则本问题退化为正文中讨论过的问题, 可以得到
令 , 则有
由于上面的结果对于任意 都成立, 所以
故
故