《具体数学》第一章 递归问题

· · 个人记录

注：我将《具体数学》电子版的 pdf 文档放在文末的链接中，同时，若该博客中图片损坏，也请到文末链接中下载，并私信我或发到文末的邮箱中告诉我，谢谢。

第一章 递归问题

1.1 汉诺塔问题

给定由 n 个圆盘组成的塔，这些圆盘按照大小递减的方式套在三根桩柱中的一根上。

我们的目标是要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动的过程中不能放置在较小的圆盘上面。

求最少移动次数。

解法

设 T_n 表示将 n 个圆盘从一根桩柱移动到另一根桩柱上所需的最少次数，因为 0 个圆盘无需移动，所以得出

T_0 = 0

同时，我们可以直接将一个圆盘从一根桩柱移动到另一根桩柱上，则

T_1 = 1

以及将 n = 2 ，以下将三根桩柱称为柱1、柱2和柱3，两个圆盘称为小盘、大盘

  1. 将小盘从柱1移动到柱2；
  2. 将大盘从柱1移动到柱3；
  3. 将小盘从柱2移动到柱3。

这样就完成了将两个圆盘从柱1到柱3的移动，所以

T_2 = 3

我们可以拓展出 n = 3 的情况，我们将较小的两个圆盘看做一个整体

  1. 将两个圆盘从柱1移动到柱2；
  2. 将第三个圆盘从柱1移动到柱2；
  3. 将两个圆盘从柱2移动到柱3。

可得

\begin{aligned} T_3 & = 2T_2 + 1 \\ & = 2 \times 3 + 2 \\ & = 8 \end{aligned}

更一般的，以此类推，可以将 ( n - 1 ) 个圆盘当成一个整体

  1. 将 ( n - 1 ) 个圆盘从柱1移动到柱2；
  2. 将第 n 个圆盘从柱1移动到柱2；
  3. 将 ( n - 1 ) 个圆盘从柱2移动到柱3。

即

T_n = 2T_{n-1} + 1 , n > 0 .

综上所述，得出

\begin{aligned} & T_0 = 0 ; \\ & T_n = 2T_{n-1} +1 , n > 0 . \end{aligned}

以上是递归式定义，不便于直接计算，所以我们尝试将它转换成封闭形式，使我们可以对其进行快捷运算，以及估计 T_n 的大小。

我们可以先将 T_n 展开

\begin{aligned} T_n & = 2T_{n-1} + 1 \\ & = 2( 2T_{n-2} +1 ) + 1 \\ & = 2( 2( 2( \cdots ( 2( 2T_0 + 1 ) + 1 ) \cdots ) + 1 ) + 1 ) + 1 \\ & = 2( 2( 2( \cdots ( 2( 2 \times 0 + 1 ) + 1 ) \cdots ) + 1 ) + 1 ) + 1 \\ & = 2( 2( 2( \cdots ( 2 \times 1 + 1 ) \cdots ) + 1 ) + 1 ) + 1 \\ & = 2( 2( 2( \cdots ( 2 + 1 ) \cdots ) + 1 ) + 1 ) + 1 \\ & = 2^{n-1} + 2^{n-2} + 2^{n-3} + ... + 2^2 + 2^1 + 2^0 \\ & = \sum_{i=0}^{n-1} 2^i \end{aligned}

看上去 T_n = \sum_{i=0}^{n-1} 2^i 已经足够简洁了，但这个和式实际上还可以再一步化简，我们发现这个和式的每一项都是二的整次幂，所以我们可以把他写成一个 n 位二进制数

( \underbrace{111 \cdots 111}_n )_2

当我们给它加上 1 时，这个二进制数就会不断进位得到一个第 ( n + 1 ) 位为 1 其余 n 位为 0 的二进制数

(1 \underbrace{000 \cdots 000}_n)_2

即得到 2^n ，所以

T_{n} + 1 = 2^n

移项得

T_n = 2^n - 1

所以我们就从最开始的递归式

\begin{aligned} & T_0 = 0 ; \\ & T_n = 2T_{n-1} +1 , n > 0 . \end{aligned}

得到了

T_n = 2^n - 1 ， n \ge 0 .

证毕。

1.2 平面上的直线

平面上 n 条直线最多能把该平面分成几部分？

解法

设 L_n 表示平面上 n 条直线最多能把该平面分成几部分。

我们可以从小数据入手，尝试发现规律，即如何得出“最多”方案。

很明显，当 n = 0 时，即没有直线分割平面，则

L_0 = 1

同时如果 n = 1 ，有一条直线分割平面，就会将平面分割成两部分，像这样

所以

L_1 = 2

当 n = 2 时

也就是

L_2 = 4

似乎还不够得出普遍规律，再看看 n = 3 的情况

此时

L_3 = 7

已经可以大致看出最优策略了，我们应该让每条直线分割尽量多的区域，换个说法，应该让直线产生尽量多的交点，所以我们应该让直线两两相交，并且避免超过两条直线交于一点，这个时候，结果是“最多”的。

那么继续探究，我们的目标不仅仅是策略，而是求 L_n 。

我们可以采用递推的思想，假设我们再求 L_n 时， L_0 \sim L_{n-1} 都是已知的，则可以将问题转化成在原有的用最优方案分割好的平面上，用一条直线切割尽量多的区域，依据上文所说，我们应该使该直线与每条直线相交，且不交于原有的交点，此时由于第 n 直线没有穿过其他任意两条直线的交点，即它穿过的区域可以看做一个平面被 ( n - 1 ) 条平行线分割成了 n 部分，则第 n 条直线将 n 个区域分割成了 2n 个区域，增加了 n 个区域，所以得出

L_n = L_{n-1} + n , n > 0 .

这样就得出了 L_n 的递归式形式

\begin{aligned} & L_0 = 1 ; \\ & L_n = L_{n-1} + n , n > 0 . \end{aligned}

当然，这是不够的，我们依然要致力于求出 L_n 的封闭形式。

与上一题相同，将递归式展开得到

\begin{aligned} L_n & = L_{n-1} + n \\ & = L_{n-2} + ( n - 1 ) + n \\ & = L_0 + 1 + 2 + 3 + \cdots + ( n - 2 ) + ( n - 1 ) + n \\ & = L_0 + \sum_{i=1}^n i \\ & = \sum_{i=1}^n i + 1 \end{aligned}

接下来就是解决 \sum_{i=1}^n i 的过程了。

可以看出这是一个等差数列求和，可以通过高斯求和化成封闭形式，下面给出证明。

高斯求和证明

高斯求和用于将形如

a + ( a + p ) + \cdots + ( a + (n - 1)p ) + ( a + np )

的等差数列写成封闭形式，方法接下来会介绍。

我们设 S = a + ( a + p ) + \cdots + ( a + (n - 1)p ) + ( a + np ) ，则我们先将 S 复制一份，反着写在原式下方，得到

\begin{aligned} & a & + & ( a + p ) & + & \cdots & + & ( a + ( n - 1 )p ) & + & ( a + np ) \\ & ( a + np ) & + & ( a + ( n - 1 )p ) & + & \cdots & + & ( a + p ) & + & a \end{aligned}

上下两两对应相加，则可得

\begin{aligned} 2S & = ( 2a + np ) + ( 2a + np ) + \cdots + ( 2a + np ) + ( 2a + np ) \\ & = ( n + 1 ) ( 2a + np ) \end{aligned}

两边同时除以 2 得

S = \frac{(n+1)(2a+np)}{2}

显然，这个写法不太优雅，因为我们常常不关心等差数列的差值，所以可以将等差数列换种方式表示：

但 ( n + 1 ) 项总归有些拗口，所以将所有 ( n + 1 ) 改为 n ，将 n 改为 ( n - 1 ) ，即将 n 的值全部加 1 ，就将 S 表示成了

S = \frac{n(a+b)}{2}

用中文表示为

等差数列的和 = \frac{( 首项 + 末项 ) \times 项数}{2}

证毕。

言归正传，有了高斯求和的铺垫，我们就可以轻松得出 L_n 的值

\begin{aligned} L_n & = \sum_{i=1}^n i + 1 \\ & = 1 + 2 + \cdots + ( n - 1 ) + n + 1 \\ & = \frac{(1+n)n}{2} + 1 \\ & = \frac{n(n+1)}{2} + 1 \\ \end{aligned}

综上所述

L_n = \frac{n(n+1)}{2} + 1 , n \ge 0 .

证毕。

1.3 约瑟夫问题

一个 1 \sim n 的序列，首尾相接连成一个环，从 1 开始，每隔一个数删去一个，问最后会留下哪个数？

解法

设 J_n 表示 1 \sim n 的序列，首尾相接连成一个环，从 1 开始，每隔一个数删去一个，问最后会留下哪个数。

开始的环是这样的

1 , 2 , 3 , \cdots , ( n - 2 ) , ( n - 1 ) , n

即

首先，从小数据开始，只有 1 个数的环留下的数肯定是 1 ，所以

J_1 = 1

研究完小数据，当然要向大数据推广，很明显，因为是隔一个删去一个，每轮删去哪些数，留下哪些数与 n 的奇偶性息息相关，所以我们分两种情况讨论：

当 n 是偶数时，第一轮删去 2 , 4 , 6 , \cdots , ( n - 2 ) , n ，则得到序列

1 , 3 , 5 , \cdots , ( n - 3 ) , ( n - 1 )

图是这样的

我们发现当 n 为偶数，一轮删去了 \frac{n}{2} 个数，而删去以后的数列可以表示为

1 , 3 , 5 , \cdots , 2( n - 1 ) - 1 , 2n - 1

也就是

同时 n 的规模削减一半，所以得出

J_n = 2J_\frac{n}{2} - 1 , n 取偶数 .

当 n 是奇数时，第一轮删去了 2 , 4 , 6 , \cdots , ( n - 3 ) , ( n - 1) ，紧随其后删去了 1 ，所以剩下

3 , 5 , 7 , \cdots , ( n - 2 ) , n

如图

删去后的数列也可以这样表示

3 , 5 , 7 , \cdots , 2( n - 1 ) + 1 , 2n + 1

即

我们也可以发现， n 的规模削减了 ( \frac{n-1}{2} + 1 ) ，通过计算

\begin{aligned} n - ( \frac{n-1}{2} + 1 ) & = n - \frac{n-1}{2} - 1 \\ & = ( n - 1 ) - \frac{n-1}{2} \\ & = \frac{2(n-1)-(n-1)}{2} \\ & = \frac{n-1}{2} \end{aligned}

即， n 的规模削减至 \frac{n-1}{2} ，所以

J_n = 2J_\frac{n-1}{2} + 1 , n > 1 且 n 取奇数 .

综上所述

\begin{aligned} & J_1 = 1 ; \\ & J_n = 2J_\frac{n}{2} - 1 , n 取偶数 ; \\ & J_n = 2J_\frac{n-1}{2} + 1 , n > 1 , n 取奇数 . \\ \end{aligned}

自然，我们要尽己所能将它化成一般式，但现在这个式子比之前的

\begin{aligned} & T_0 = 0 ; \\ & T_n = 2T_{n-1} +1 , n > 0 . \end{aligned}

还有

\begin{aligned} & L_0 = 1 ; \\ & L_n = L_{n-1} + n , n > 0 . \end{aligned}

都复杂了不少，似乎并不能简单的展开得到答案。

所以我们这里再介绍一种方法：数学归纳法。

数学归纳法，它的过程可以简单的分为三步：

  1. 列举小数据，得出规律；
  2. 归纳总结，得出猜想；
  3. 证明猜想，得出结论。

我们就用数学归纳法探究约瑟夫问题的封闭形式。

列举小数据，得出规律

我们可以先列举一下小数据，观察一下它们的规律

n 1 2 3 4 5 6 7 8
J_n 1 1 3 1 3 5 7 1
n 9 10 11 12 13 14 15 16
J_n 3 5 7 9 11 13 15 1

归纳总结，得出猜想

从表中数据观察可以发现， J_n 的值按 1 , 3 , 5 , \cdots 排列，且在 2 的整次幂时重置，所以我们可以大胆猜想，我们可能可以这样表示

J_{2^p+q} = 2 q+ 1 , p \ge 0 , 0 \le q < 2^p .

证明猜想，得出结论

因为递归式是

\begin{aligned} & J_1 = 1 ; \\ & J_n = 2J_\frac{n}{2} - 1 , n 取偶数 ; \\ & J_n = 2J_\frac{n-1}{2} + 1 , n > 1 , n 取奇数 . \\ \end{aligned}

也就是说，我们要依靠递归式，证明出我们的结论。

首先，通过 n 取偶数时的递归式，当 n 是 2 的整次幂时

\begin{aligned} J_n & = 2J_\frac{n}{2} - 1 \\ & = 2( 2J_\frac{n}{4} -1 ) - 1 \\ & = 2( 2( 2( \cdots ( 2( 2J_1 - 1 ) - 1 ) \cdots ) - 1 ) - 1 ) - 1 \\ & = 2( 2( 2( \cdots ( 2( 2 \times 1 - 1 ) - 1 ) \cdots ) - 1 ) - 1 ) - 1 \\ & = 2( 2( 2( \cdots ( 2( 2 - 1 ) - 1 ) \cdots ) - 1 ) - 1 ) - 1 \\ & = 1 \end{aligned}

得出，当 n 是 2 的整次幂时，最后留下的数一定是 1 。

以此为基础，我们就可以证明 n 为其他数时的情况。

当 n = 2^p + q 时，先删掉 2 , 4 , 6 , \cdots , 2(q-1) , 2q ，留下的情况是 n = 2^p 的情况，也就是说第一个数会留到最后，所以

J_{2^p+q} = 2q + 1 , p \ge 0 , 0 \le q < 2^p .

如果换成 J_n 的形式，因为当 n = 2^p + q ( p \ge 0 , 0 \le q < 2^p ) 时， p \le \log n < p+1 ，所以 \lfloor \log n \rfloor = p ，则 n - 2^{\lfloor\log n\rfloor} = q ，得

J_n = 2( n - 2^{\lfloor\log n\rfloor} ) + 1 , n \ge 1 .

证毕。

《具体数学》电子版 ：
链接: https://pan.baidu.com/s/1XBLLyhafWz1iYdcPmpneaw
提取码: yuja
备用图片
链接：https://pan.baidu.com/s/1w9gvvH2p8TOarXgyKLdq2w
提取码：7mhk
我的邮箱：[email protected]