具体数学(第2版)习题解析

-1-1递归问题1.1知识点总结1.2练习题1.2.1热身题【1.1】所有的马都有同样的颜色，我们可以对给定集合中的马匹数量运用归纳法来证明之。理由就是：“如果恰有一匹马，那么它与它自身有相同的颜色，故而基础是显然的。根据归纳法的步骤，假设有n匹马，标号从1到n。根据归纳假设，标号从1直到n-1的马都有同样的颜色，类似地，标号从2直到n的马也有同样的颜色。但是，处于中间位置标号从2直到n-1的马，当它们在不同的马群中时不可能改变颜色，因为这些是马，而不是变色龙。故而依据传递性可知，标号从1直到n的马也必定有同样的颜色，于是全部n匹马都有同样的颜色。证毕。”如果这一推理有误，那么错在哪儿？解：略。【1.2】把有个圆盘的塔从左边的桩柱A移动到右边的桩柱B，不允许在A和B之间直接移动，求最短的移动序列（每一次移动都必须是移动到中间的桩柱或者从中间的桩柱移出。像通常一样，每次只能移动一个圆盘，且较大的圆盘永远不能放在较小圆盘的上面）。解：【1.2a】现有3个排成一行的桩柱A、B和C，柱B位于柱A和柱C之间。初始状态是在A柱上叠放了个尺寸不同的圆盘，其叠放规则是自上而下按圆盘尺寸从小到大进行叠放。现要求将个圆盘从柱A移动到柱C，移动规则如下：（1）每次只能移动一个圆盘；（2）所有的圆盘不可以在柱A和柱C之间直接移动，而必须经过中间的桩柱B（可以移入到柱B或从柱B移出）；（3）较大的圆盘永远不得放在较小圆盘的上面。对于上述问题，我们已知最短的移动序列满足如下递归式：。请求解：（1）上述递归式的封闭形式解。（2）如果放宽第3个条件，即：只允许最大的那个圆盘可以放在较小圆盘之上，而其它所有圆盘仍遵守小盘在上、大盘在下的叠放和移动规则，那么最短的移动序列是多少？解：（1）由递归式，可得：令，则有：-2-可解得：，因此有：（2）依然采用分治法，分而治之，把大问题化解成小问题。最开始在A柱子上有个盘子，我们可以把个盘子看成：前个盘子、第个盘子和第个盘子。令为移动个盘子的最短移动序列。S1：把前个盘子从A柱移动到C柱，至少需要移动步；S2：把第个和第个盘子从A柱依次移动到B柱，需要移动2步；S3：把前个盘子从C柱移回到A柱，这又需要步；S4：把第个和第个盘子从B柱依次移动到C柱上，需要移动2步；S5：把前个盘子从A柱移动到C柱，至少又需要移动步。最终按要求完成了个盘子的移动，因此有：【1.5】由3个重叠的圆做成的维恩图常用来描述与3个给定集合有关的8个可能得子集：请问：由4个给定集合给出的16种子集的子集能否用4个重叠的圆来描述？解题分析：此题与直线的平面划分问题相同。思考方法：考虑每增加一个圆圈，增加的交点与增加的区域的关系。因为每增加一个圈，与每一个已存在的圈相交，最多每个圈有2个交点，而所增加的区域正好与增加的交点数目相同。设为n个圈划分的区域个数，可得：最终可求得：，【1.6】平面上由条直线定义的某些区域是无界的，而另一些区域则是有界的。有界区域的最-3-大个数是多少？解：解题思路：当时，每增加一条直线，增加的有限区域个数是(原直线个数-1)，所以设当有条直线时，设有限区域个数为。可求得递归式：最终可求得：1.2.2作业题【Z1.1】楼梯有级台阶，上楼时可以一步上一级台阶，也可以一步上两级台阶，请问有多少种不同的走法？答：（1）解法一：待定系数法构造等比数列（初等代数解法）令为级台阶的走法，则有：设常数和，使得如下等式成立：即：可知：可求得：当时，有如下方程组：-4-可得：由于，进一步可得：这样又可得到一个联立方程组：可得：以下计算过程，略。（2）解法二：利用特征方程（线性代数解法）令为级台阶的走法，则有：线性递推数列的特征方程为：可得：于是：-5-将初值代入上述方程，可得：最终可得：（3）解法三：生成函数法令为级台阶的走法，则有：设数列的生成函数为，则：注：在这种生成函数的构造方法中，项的系数为，后面求解时，也要求解项对应的系数。进而有：将上述三个等式相加，可得：上述等式右端的和式为0，且已得，因此有：可得：进而有：-6-以下略。【1.8】解递归式假设对所有都有。提示：。解：（1）首先研究小的情形。依据题目给定的递归式，分别求解、、、和的值，进而观察值的变化是否存在某种规律。经计算和观察，可推测是周期性函数，循环周期为5，即：（2）证明。可采用数学归纳法进行证明，此处可假设、、、-7-、，现只需证明、、、、的值均符合我们所推测的结论，即可完成证明。实际上结论是很显然的，证明略。【1.10】设是将一个有n个圆盘的塔从A移动到B所需要的最少移动次数，要求所有的移动都必须是顺时针方向的，也就是说，从A到B，从B到其他的桩柱，再从其他的桩柱到A。又设是在这一限制下从B返回到A所需要移动的最少次数。证明：（无需解这些递归式，我们将在第7章里介绍怎么做。）解：（1）首先理解题意。是什么？是n个圆盘按顺时针方向，从A柱到其相邻的B柱所需要的最少移动次数。进而可知，从B柱到其相邻的C柱，或从C柱到其相邻的A柱，也一定都是次。是n个圆盘按顺时针方向，从B柱经过C柱再到A柱的最少移动次数。进而可知，从C经A到B，或从A经B到C的最少移动次数也一定都是次。（2）研究小的情形。可考虑3个圆盘按照题中规则进行移动的步骤和过程，以进一步理解题意。（3）证明=？当n=0时，=0是显然的。当n0时，若n个圆盘从B到C，则应首先将前n-1个圆盘从B经C移到A，这需要次，此时才能够将最大的圆盘从B移到C，这需要1次；然而，还需要将前n-1个圆盘从A经B移到C，这仍需要次。因此，可得。-8-（4）证明=？当n=0时，是显然的。以下证明当n0时，等于多少？要想求出符合移动规则的最少移动次数，需分三个步骤进行移动：首先考虑什么时候能够开始移动最大的圆盘？只有将前n-1个圆盘从B经C移到A时，才能开始移动最大的那个圆盘，而此时最大的圆盘只能从B柱移动到C柱。否则，或者违反“大盘放在小盘下面”这个规则，或者违反“按顺时针移动”这个规则。此时，需要（+1）次移动。这时，n个圆盘的状态是：前n-1个圆盘在A柱上，而最大的圆盘在C柱上。然后考虑到必须前n-1个圆盘从A移到B时，最大的圆盘才能从C移到A，这需要（+1）次移动。此时，n个圆盘的状态是：前n-1个圆盘在B柱上，而最大的圆盘在A柱上。最后只需将前n-1个圆盘从B经C移到A，这需要次移动。可得：请思考：可否得出：？即：可否得出“n个圆盘按照上述规则，从B经C到A的最少移动次数等于从B到C（或从C到A、或从A到B）的最少移动次数的2倍”？【1.11】双重河内塔包含2n个圆盘，它们有n种不同的尺寸，每一种尺寸的圆盘有两个。如通常那样，要求每次只移动一个圆盘，且不能把较大的圆盘放在较小的圆盘上面。（a）如果相同尺寸的圆盘是相互不可区分的，要把一个双重塔从一根桩柱移动到另一根桩柱需要移动多少次？（b）如果在最后的排列中要把所有同样尺寸的圆盘恢复成原来的从上到下的次序，需要移动多少次？提示：这是一个难题，实在应该是“附加题”。题目解释：问题（a）和问题（b）的区别在于：问题（a）移动完成后，不要求尺寸相同的两个盘子之间的上下叠放次序保持原来的情况；而问题（b）则恰恰要求所有的盘子均需保持原有的上下叠放关系。解：（a）如下图所示，该问题与原始的汉诺塔问题类似。设为符合该问题要求的移动2n个圆盘的解。-9-解题思路1：●当移动两个最大的尺寸相同的圆盘时，前2n-2的圆盘一定在某根桩柱上，当然此时这2n-2个圆盘也只能在同一根桩柱上，否则若分散在两根或三根桩柱上，是无法移动那两个尺寸相同的最大的圆盘的。因此，移动2n-2个圆盘的最少次数为。●然后移动两个最大圆盘，需要2次。●最后仍需要将2n-2个圆盘移动到两个最大圆盘的上面，还需要次移动。综上并考虑到，可得递归式：，进而可求得：有一点需要说明的是，当移动两个尺寸相同的最大圆盘到其它桩柱后，它们两个互相交换了上下位置。请思考：为什么前2n-2个圆盘中的每两个尺寸相同的圆盘在移动完成后，仍能够保持原来的上下位置关系？解题思路2：在移动这些圆盘时，对每两个尺寸相同的圆盘的移动过程都是先后紧邻次序的进行移动的，因此若将每两个尺寸相同的圆盘看做一个圆盘的话，那么该问题等价于对n个不同尺寸的圆盘进行移动的原始汉诺塔问题。因此，与存在如下关系：（b）设为符合要求的移动2n个圆盘的解。该问题的最终移动结果如下图所示。-10-移动过程分以下几个步骤，其中步骤1、3、5、7均等价于问题（a）的移动规则：Step1：将前2n-2个圆盘从A→C，需移动次，每对同尺寸圆盘将颠倒叠放次序；Step2：将第2n-1号圆盘从A→B，需移动1次；Step3：将前2n-2个圆盘从C→B，需移动次，每对同尺寸圆盘又恢复叠放次序；Step4：将第2n号圆盘从A→C，需移动1次；Step5：将前2n-2个圆盘从B→A，需移动次，每对同尺寸圆盘将颠倒叠放次序；Step6：将第2n-1号圆盘从B→C，需移动1次；Step7：将前2n-2个圆盘从A→C，需移动次，每对同尺寸圆盘又恢复叠放次序。综上，可得：，经计算可得：扩展思考1：双色河内塔包含3个桩柱和2n个圆盘，这些圆盘有n种不同的尺寸，每种尺寸的圆盘有2个且颜色不同。每次只移动一个圆盘，且不能把较大的圆盘放在较小的圆盘上面。如下图所示，若将不同颜色的圆盘移动到不同的桩柱上，那么足够且最少（充分且必要）的移动次数是多少？-11-扩展思考2：三色河内塔问题。如果3n个圆盘有n种尺寸，每种尺寸的圆盘又有3种颜色，要想做到如下图所示的移动结果，足够且最少的移动次数是多少？【1.13】有n条Z形线所定义的区域的最大个数是多少？每条Z形线由两条平行的无限半直线和一条直线段组成。提示：如上图所示，两条Z形线可分割出12个区域。解：思路1：令为n个Z形线所围成的区域的最多数。-12-由于第n个Z形线与前n-1个Z形线中的每个Z形线最多可有9个交点，共计最多可有9(n-1)个交点，可新增9(n-1)+1=9n-8个区域。因此，可得：进一步计算，可得：思路2：先研究n个等号“=”和n个不等号“≠”的情况；然后再研究n个Z形线的求解思路。注：这种方法虽然麻烦些，但有利于深入分析问题，有利于训练思维。（1）研究n个等号“=”最多可以围成多少个区域的问题，其中：等号中的两条平行线均为无限长的直线。令为n个等号所围成的区域的最多数。第n个等号的每条平行线与前n-1个等号各有2(n-1)个交点，各自均产生2(n-1)+1个新区域，因此，可得，经计算可得：总结：注意研究题中给定的规则和几何图形的形态、注意研究小情形下区域分割的变化规律，进而研究、猜测并总结新增区域的产生机理是什么。（2）研究n个不等号“≠”最多可以围成多少个区域的问题，其中：不等号中的三条线均为无限长的直线。令为n个不等号所围成的区域的最多数。-13-第n个不等号中的两条平行线，每条均与前n-1个不等号有3(n-1)个交点，均新增3(n-1)+1个区域，第n个不等号的两条平行线共计新增2(3(n-1)+1)个区域。第n个不等号中的斜线与前n-1个不等号也有3(n-1)个交点，而又与第n个不等号中的两条平行线存在2个交点，共计新增3(n-1)+2+1个区域。综上，可得：。经计算，可得：（3）研究n个Z形线的问题。令为n个Z形线所围成的区域的最多数。提示1：此处对“直线”定义为无限长且没有端点的线，“半直线”被定义为一端为无限延展而另一端有端点的线，“线段”为两端均有端点的有限长度的线。按此定义，则Z形线包含2条平行的“半直线”和1条“线段”。提示2：对Z形线中“半直线”与“线段”相交的点称为“顶点”，而“交点”被定义为两条无限长的直线相交所产生的点。由于在Z形线中包含1个斜向的“线段”，在顶点处形成了“半直线”和“线段”，因此1个Z形线比1个不等号少4个区域，这样n个Z形线就比n个不等号少4n个区域，因此，可得：【1.15】约瑟夫有一个朋友，他站在倒数第二的位置上因而获救，当每隔一个人就有一人被处死时，倒数第二个幸存者的号码I(n)是多