具体数学-约瑟夫问题

引子

最近在读计算机经典教科书《具体数学》，作为一个非科班的计算机从业者，仿佛打开了新的天地，原来我刷题遇到的算法问题很多都可以用数学方法解决，原来数学不光是高数、线代和微积分三座大山，离散数学在计算机上是绝配。为记录学习过程中的心得并分享，故展开具体数学系列博客，望与有缘人分享这份知识的喜悦。

和《具体数学》的章节安排一样，本博客作为系列第一篇，主要讨论递归算法，从难易程度分成三个部分：河内塔、平面上的直线、约瑟夫问题。它们有两个共同的特征：一是都曾被数学家反复研究过；二是它们的解都用了 递归 的思想。

河内塔 THE TOWER OF HANOI

学习过递归算法的同学应该都知道知道河内塔，我当时就是通过河内塔入门了递归算法的。河内塔是由法国数学家爱德华·卢卡斯于1883 年发明的。给定一个由8个圆盘组成的塔，这些圆盘按照大小递减的的方式套在三根桩柱中的一根上。

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

现在问题来了：我们能做到的最好的解法是什么？也就是说，要完成这项任务移动多少次才是必须且足够的？

研究这样的问题的最好的方法是对它稍加推广，如果有n个圆盘将会怎么样？

事实上，研究递归问题，我们将会看到先研究小的情形是有益的。通过少量尝试就能看出如何移动3个圆盘的塔。

要用数学语言解决这个问题，我们自然需要引入适当的记号：命令并求解。我们称 $T_n$ 是根据卢卡斯的规则将圆盘从一根柱移动到另一根柱所需要的最少移动次数。那么，$T_1$ 显然是1，$T_2=3$ ，另外定义 $T_0=0$。

我们从宏观的角度来分析这个问题，如何将n个圆盘移动到柱子B。首先移动上面n-1个圆盘到柱子C，然后移动最大的圆盘到柱子B，最后将n-1个圆盘移动到柱子B。就像如何将大象放入冰箱一样，只要分三步。我们将这三步用数学语言进行表示：

$$ T_n \leq 2T_{n-1}+1 $$

之所以用了 $\leq$ ，没用 = ，是因为我们的构造仅证明了 $2T_{n-1}+1$ 次移动足够完成任务，但是没有证明必须要这么多次才能完成任务。

这里我没法用公式说明为什么，只能做一个思想游戏：假如我要把所有圆盘从A移动到B，必须把最大的圆盘先放到B，这个时候上面的n-1个圆盘必然在另一个柱子上，也就是说完成这一步必须要 $T_{n-1}+1$ 步，大圆盘放到B后，必须把n-1个圆盘也移动到B上，最少需要 $T_{n-1}$ 步，也就是说：

$$ T_n \geq 2T_{n-1}+1 $$

综合两个不等式，我们可以得出当我们以完全正确的步骤移动河内塔时需要的移动次数：

$$ \begin{aligned} & T_0 = 0; \\ & T_n = 2T_{n-1}+1. \end{aligned} \tag{1.1} $$

像（1.1）这样的一组等式我们称为递归式（recurrence），它给出一个边界值，以及一个递推关系的方程。有时我们也把单独的一般性方程称为递归式，尽管技术上还需要一个边界值来补足。

假如用代码实现，上述的递推关系已经可以完成变成了，我们可以使用递归调用简洁的实现河内塔计算。但是当n很大时，计算太耗时了。

递归的解 很美妙，也很容易理解，但是并不容易直接计算，在实际使用中，我们希望简化获得一个即漂亮又简洁的“封闭形式”。也就是 $T_n$ 的计算应该与上一个值 $T_{n-1}$ 无关, 只和n相关。

我们通过观察，很容易想到 $T_n$ 和 2 的幂相关，在通过初始几个数字的尝试，我们可以确定：

$$ T_n = 2^n - 1, n \geq 0 \tag {1.2} $$

至少在我们尝试 $n \leq 6$ 时是成立的。再通过数学归纳法，很容易证明该公式对于 $n \geq 0$ 都成立。

《具体数学》将解决这类问题分为了三个步骤：

1. 研究小的情形。这有助于我们洞察该问题
2. 对有意义的量求出数学表达式并给出证明。对于河内塔，就是递归式（1.1）。
3. 对数学表达式求出封闭形式并证明，对于河内塔，就是递归解（1.2）

平面上的直线 LINES IN THE PLANE

第二个问题平面上的直线相信大家也都遇到过：一个蛋糕，切4到最多能分成几块（这里限定是一个平面上切）。我们把问题用数学语言重新翻译下并进行宽展：平面上n条直线所界定的的区域的最大个数 $L_n$ 是多少？这个问题于1826年被以为瑞士数学家坦纳首先解决。

我们再从最小情形开始研究。

$L_0 = 1$, $L_1 = 2$, $L_2 = 4$, $L_3 = 7$ 。

思考后，我们可以得出递推关系：

第n（n>0）条直线使得区域增加k个，当且仅当它对k个已有区域进行了分裂； 而它对k个已有区域进行分裂，当且仅当它在k-1个不同的地方与之前的直线相交； 两条直线至多相交与一点，之前已有n-1条直线，因而这条新的直线与n-1条直线至多相交于n-1个不同的点，故必定有 $k \leq n-1$，我们证明了上界

$$ L_n \leq L_{n-1} + n, \quad n \gt 0. $$

已知当 $n \lt 4$ 时可以取到 =，我们采用数学归纳法来证明对于所有n都可以取到上界。

证明：已知 $n \lt 4$ 时公式成立；假设当 n=k 时满足 $L_n = L_{n-1} + n$ 。需要证明当 n = k + 1 时公式仍然成立。

我们径直来放第k+1条直线，该直线不与之前任何一条直线平行，因此它与之前的k条直线相交，分隔出k+1个空间，即$L_{k+1} = L_k + k+1$，所以递归式为：

$$ \begin{aligned} & L_0 = 1; \\ & L_n = L_{n-1} + n, \quad n \gt 0. \end{aligned} \tag {2.1} $$

证明结束。

现在我们需要一个封闭形式的解，我们先观察 $L_n$ 的形式，发现递归形式很像是在求 $\sum_{i=1}^ni$，高斯告诉我们，这个求和公式的值是

$$ S_n = \frac {(n+1)n}{2}, \quad n \geq 0 $$

对比 $L_n$ 的值，我们调整下式子。

$$ L_n = \frac {(n+1)n}{2} + 1, \quad n \geq 0 $$

再使用数学归纳法，可以证明这就是正确的解。

我们多次提到封闭形式，《具体数学》中有粗略定义：如果可以利用至多固定次数（其次数与n无关）的标准运算来计算量的 $f(n)$ 表达式，那么这个表达式是封闭的。当然有一些例外情况，例如，$n!$ 被证明是如此重要，故而我们都把它视为是一种基本运算，于是公式 $n!$ 就是封闭形式。

平面上的折线

现在我们把问题做一个变形：假设我们用折线代替直线，每一条折线包含一个“锯齿”。平面上由n条这样的折线所界定的区域的最大个数 $Z_n$ 是多少？

或许我们期待 $Z_n$ 是 $L_n$ 的两倍或者三倍。通过几个简单情况的观察。

我们发现折线的情况和直线类似，只是折线在“锯齿”处缺少了一处切割，少了两个区域。

也就是说放一条折线相当与放两条直线，但是需要减去两个区域。

$$ \begin{aligned} Z_0 &= 1 \newline Z_n &= Z_{n-1} + (2n - 1 + 2n) - 2 \newline &= Z_{n-1} + 4n - 3, \quad n \gt 0 \end{aligned} $$

我们将公式进行变形。

$$ Z_n - Z_{n-1} = 4n - 3 $$

如果学习过微积分就能发现，这个形式很像微分的定义，在离散数学中，这种形式称为差分，这里不直接使用差分的性质，而是先自行推导 $Z_n$ 的计算。

$$ \begin{aligned} Z_n &= Z_0 + \sum_{k=1}^{n}4n-3 \\ &= 2n^2 - n + 1 \\ \end{aligned} \tag{2.2} $$

方程（2.2）使用了求和累加，从 $Z_0$ 累加前后项差分值计算出 $Z_n$。《具体数学》中使用了 $L_n$ 来对 $Z_n$ 求值。

$$ Z_n = L_{2n} - 2n = 2n^2 - n + 1, n \geq 0 $$

比较 $L_n$ 和 $Z_n$， 我们发现对于大的n有

$$ \begin{aligned} L_n &\sim \frac {1}{2}n^2, \\ Z_n &\sim 2n^2; \end{aligned} $$

所以用折线所能得到的区域是用直线所能得到区域的大约4倍，也符合我们开始的直觉。

约瑟夫问题 THE JOSEPHUS PROBLEM

终于到了本文的核心问题，也是《具体数学》中第一章的点睛之笔——约瑟夫问题。在这里我们将学习到如何一般化处理这类递归问题，不再依靠解体时的灵光乍现。

传说在犹太罗马战争期间，约瑟夫与其他他40名犹太反抗者困在了罗马人包围的洞穴中，这些反抗者宁愿自杀也不愿被活捉，于是决定围成一个圆圈，并沿着圆圈每个两个人杀死一个人，直到剩下两个人为止。但是约瑟夫和一个未被告发的同谋者不希望无谓的自杀，于是他迅速计算出他和朋友在这险恶的圆圈中应该站的位置。

我们对问题进行一些改动和简化：从围成标有记号1到n的圆圈的n个人开始，每隔一个人删去一个人，直到有一个人幸存下来，例如 $n=10$ 的起始图形：

消去的顺序是2，4，6，8，10，3，7，1，9，于是5幸存下来。问题：确定幸存者的号码，我们表示为 $J(n)$.

第一步，观察基本情形。

似乎幸存者都是奇数，事实上，第一轮结束后，所有偶数都被消灭了，第二轮开始剩下的都是偶数。等等，我们似乎发现了一个递推关系：第一轮，第二轮，第三轮，···。直到某一轮只有一个人 $J(1)$， 那个人就是最终的幸存者。但是这个递推关系中还有一个问题，就是每一轮我们需要将幸存者重新编号，找到幸存者后，我们需要恢复幸存者的真实编号。这难不倒我们，我们可以将编号的关系带入到递归公式中。

当第一轮是偶数是：

当第一轮是奇数时：

当第一轮是奇数时，需要把1号删除才能结束该轮，否则第二轮开始1号会存活，违反了游戏规则。

$$ \begin{aligned} J(1) &= 1; \\ J(2n) &= 2J(n) - 1, \quad n \geq 1; \\ J(2n+1) &= 2J(n) + 1, \quad n \geq 1. \end{aligned} $$

注意到我们用了 $2n$, $2n+1$ 的形式来书写公式，没有选择 $n/2$ 的形式，避免了增加n是偶数还是奇数的条件。

《具体数学》中对 $J(n)$ 的前几项展开进行了观察，发现结果和 n 与 2 的幂次相关，并使用数学归纳法获得封闭形式。

$$ J(2^m+l) = 2l + 1, \quad m \geq 0, \quad 0 \leq l \lt 2 ^m \tag{3.1} $$

书中详细介绍了求解过程，这里我们不再是赘述。

到了这里，我们已经解决最后幸存的问题，但是相对于约瑟夫问题，我们还没完全解决，因为问题中要求计算最后两个幸存者。那么倒数第二的幸存者是谁呢。

我们使用类似的方法，定义倒数第二幸存者为 $I(n)$，可以得到一个递归公式。

$$ \begin{aligned} I(2) &= 2; \\ I(3) &= 1; \\ I(2n) &= 2I(n) - 1, \quad n \geq 2; \\ I(2n+1) &= 2I(n) + 1, \quad n \geq 2; \end{aligned} $$

看起来这个递归式不好简化，这里先放一边，我在文章末尾进行解答。

问题推广

这一节是递归问题求解的精华部分，如果你没有仔细阅读前面的部分，这一部分可不能再错过。

我们对 (3.1) 的公式进行变形，将n进行二进制展开。

$$ \begin{aligned} n &= (b_{m} b_{m-1} \ldots b_1 b_0)2 \\ n &= b{m}2^m + b_{m-1}2^{m-1} + \cdots + b_{1}2^1 + b_{0}2^0 \end{aligned} $$

其中 $b_i$ 为0或1，而首位数字 $b_m$ 必定为 1。同时有 $n=2^m+l$ ，所以我们依次次有

$$ \begin{aligned} n &= (1b_{m-1}b_{m-2} \cdots b_{1} b_{0})2, \\ l &= (0b{m-1}b_{m-2} \cdots b_{1} b_{0})2, \\ 2l &= (b{m-1}b_{m-2} \cdots b_{1} b_{0} 0)2, \\ 2l + 1 &= (b{m-1}b_{m-2} \cdots b_{1} b_{0} 1)2, \\ J(n) &= (b{m-1}b_{m-2} \cdots b_{1} b_{0} b_{m})_2. \end{aligned} $$

所以我们就证明了

$$ J((b_{m}b_{m-1}b_{m-2} \cdots b_{1} b_{0})2) = (b{m-1}b_{m-2} \cdots b_{1} b_{0} b_{m})_2 $$

在计算机代码中，这个操作就是 $n$ 向左循环移动一位，我们就可以计算出 $J(n)$ !

让我更加一般化这个结果，引入常数 $\alpha$ 、$\beta$ 、 $\gamma$ ，力图对更加一般的递归式 (3.2) 求出一个封闭形式，以此来研究这个问题。

$$ \begin{aligned} f(1) &= \alpha ; \\ f(2n) &= 2f(n) + \beta, \quad n \geq 1; \\ f(2n+1) &= 2f(n) + \gamma, \quad n \geq 1. \end{aligned} \tag{3.2} $$

这里我们先尝试几个数字判断 $f(n)$ 和常数之间的关系，然后可以合理猜测，$f(n)$ 与 $\alpha$ 、$\beta$ 、$\gamma$ 的一次项存在某个依存关系，我们将它表示成形式

$$ f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma \tag{3.3} $$

我们要求形式中的$A(n),B(n),C(n)$对于任意常数成立,也就是与常数不相关。我们可以使用取特殊值的方式求解该方程

$取 \alpha = 1, \beta = \gamma = 0$

$$ \begin{aligned} f(1) &= A(1) = 1; \\ f(2n) &= A(2n) = 2f(n) = 2A(n), \quad n \geq 1; \\ f(2n+1) &= A(2n+1) = 2f(n) = 2A(n), \quad n \geq 1. \end{aligned} $$

看起来有 $A(n)=2^m$。

我们再取特殊值，但是我们不再直接取值并使用递归式，因为解递归式比较麻烦，我们发现除了递归式，我们还有一个已知等式 $f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$，使用这个等式可以比较容易计算 $B(n)$ 和 $C(n)$ 的值。

我们取常数函数 $f(n)=1$，研究是否有任何常数 $(\alpha, \beta, \gamma)$ 能定义它。将它带入递归式(3.2)，可以求得 $(\alpha, \beta, \gamma) = (1,-1,-1)$, 带入式子 (3.3) 可以获得 $A(n)-B(n)-C(n)=f(n)=1$，同样的方式，带入 $f(n)=n$，我们可以获得 $(\alpha,\beta,\gamma)=(1,0,1)$ ， $A(n)+C(n)=f(n)=n$。联立方程：

$$ \begin{aligned} A(n) &= 2^m, \quad 其中 n = 2^m + 1 且 0 \leq l \lt 2^m; \\ A(n) - B(n) - C(n) &=1; \\ A(n) + C(n) &= n. \end{aligned} $$

得到解：

$$ \begin{aligned} A(n) &= 2^m \\ C(n) &= n - A(n) = l \\ B(n) &= A(n) - C(n) - 1 = 2^m - 1 - l \end{aligned} $$

上述求解过程描述了一套求解递归式的成套方法(repertoire method)。首先我们来寻求一组已知解的通用参数，这会给我们一整套可以求解的特殊情形。然后将特殊情形组合起来得到一般的情况。

这一方法运用于“线性的”递归式时最为成功，这里线性的含义就是它的解可以表示成任意参数与n的函数的乘积之和，比如式子（3.3）

我们再对约瑟夫递归式进行推广，令 $\beta_0=\beta, \beta_1=\gamma$，那么我们可以把递归式(3.2)改写成

$$ \begin{aligned} f(1) &= \alpha; \\ f(2n+j) &= 2f(n) + \beta_j, \quad j=0,1, \quad n \geq 1. \end{aligned} \tag{3.4} $$

将递归式按照二进制展开，$b_m=1$

$$ \begin{aligned} f((b_{m}b_{m-1} \cdots b_1 b_0)2) &= 2f((b{m}b_{m-1} \cdots b_1)2) + \beta{b_0} \\ &= 4f((b_{m}b{m-1} \cdots b_2)2) + 2\beta{b_1} + \beta_{b_0)} \\ &= 2^mf((b_m)2) + 2^{m-1}\beta{b_{m-1}} + \cdots + 2\beta_{b_{1}} + \beta_{b_0} \\ &= 2^m\alpha + 2^{m-1}\beta_{b_{m-1}} + \cdots + 2\beta_{b_{1}} + \beta_{b_0} \\ &= (\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_1 \beta_0)_2 \end{aligned} \tag{3.5} $$

利用这个公式，我们再来计算约瑟夫问题，其中 $\alpha=1,\beta_0=-1,\beta_1=1$

当 $n = 100 = (1100100)_2$时

改变表示法使我们对于一般的递归式(3.4)给出了紧凑解(3.5)，我们还可以更加一般化(3.4)

$$ \begin{aligned} f(j) &= \alpha_j, \quad 1 \leq j \lt d; \\ f(dn+j) &= cf(n) + \beta_j, \quad 0 \leq j \lt d, n \geq 1. \end{aligned} \tag{3.6} $$

与上一个递归式是相同的，除了这里是从基数为d的数着手，而产生的值是用基数c表示之外，这就是说，它有变动基数的解

$$ f((b_{m}b_{m-1} \cdots b_1 b_0)d) = (\alpha{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_{b_1} \beta_{b_0})_c \tag{3.7} $$

这个公式十分便利，如果你没有看完前面的证明，那这个公式一定要学会使用。我们用它来解决一个递归式。

$$ \begin{aligned} f(1) &= 34; \\ f(2) &= 5; \\ f(3n) &= 10f(n) + 76, \quad n \geq 1; \\ f(3n+1) &= 10f(n) - 2, \quad n \geq 1; \\ f(3n+2) &= 10f(n) + 8, \quad n\geq 1; \end{aligned} $$

假设我们计算 $f(19)$，现在有 $19=(201)_3$

$$ f(19) = f((201)3) = (5 \quad 76 \quad -2){10} = 1258 $$

最后的问题

现在我们可以讨论上面那个倒数第二幸存者的问题了，先把前文求得的递归公式再写一遍：

$$ \begin{aligned} I(2) &= 2; \\ I(3) &= 1; \\ I(2n) &= 2I(n) - 1, \quad n \geq 2; \\ I(2n+1) &= 2I(n) + 1, \quad n \geq 2; \end{aligned} $$

我们想要使用最终获得的通用公式(3.7)来求解，但是有一个问题：我们没有 $\alpha_1$ 的定义，而且 $n=1$ 时没有定义。但是这难不到我们，回想下通用公式的推导过程

$$ \begin{aligned} f((b_{m}b_{m-1} \cdots b_1 b_0)d) &= df(b{m}b_{m-1} \cdots b_1) + \beta_{b_0} \\ &= c^{m-1}f((b_{m}b_{m-1})) + c^{m-1}\beta_{b_{m-2}} + \cdots + c\beta_{b_1} + \beta_{b_0} \end{aligned} $$

由于 n 在 1 时没有意义，所以我们最后不再展开 $b_{b}b_{m-1}$，而是整体进行处理，所以有

$$ f((b_{m}b_{m-1} \cdots b_1 b_0)d) = (\alpha{b_{m}b_{m-1}} \beta_{b_{m-2} \beta_{b_{m-2}}} \cdots \beta_{b_1} \beta_{b_0})_c $$

这个变形后的公式正好满足我们要求，我们现在用它来计算 $I(5)$, $I(41)$

$$ \begin{aligned} I(5) &= I((101)_2) = (2 \quad 1)_2 = 5 \\ I(41) &= I((101001)_2) = (2 \quad 1 \quad -1 \quad -1 \quad 1)_2 \\ &= 2 * 16 + 8 - 4 - 2 + 1 = 35 \end{aligned} $$

所以约瑟夫的朋友应该在 35 号位。

再进一步推广，倒数第 k 个幸存者是几号？从上面的结论不难发现，不论是倒是第几个幸存者，递推公式是不变的，变化的只是初始值以及取值范围，所以倒数第 k 个幸存者可以表示成 $J_k(n)$：

$$ \begin{aligned} J_k(n) &= J_k((b_{m}b_{m-1} \cdots b_1 b_0)2) \\ &= (\alpha{b_{m}b_{m-1} \cdots b_{m - \log_2 k}} \beta_{b_{m - \log_2 k - 1}} \cdots \beta_{b_1} \beta_{b_0})_2 \end{aligned} \tag{3.8} $$

写到这里，约瑟夫类似的递归问题应该已经难不倒大家了，只要能写出递归式，就能转换成封闭形式，直接求解，这就是数学神奇的地方。

参考资料

• Ronald L.Graham,Donald E.Knuth,Oren Patashnik ．具体数学计算机基础（第2版） ：人民邮电出版社，2013：7