递归问题：约瑟夫问题

这是一个生死攸关的问题！至于如何生死攸关参见《具体数学》1.3节 The Josephus Problem（那里详细的介绍了这个生死攸关的问题之来历）。现在把这个问题做如下数学上的抽象：假设有 n 个人站成一圈，现在要每隔一个删除一个人，直到只有一个人幸存下来。例如 n=10 的情形如图1所示：

消去的顺序是：2,4 6,8,10,3,7,1,9，于是5幸存下来。问题：确定幸存者的号码 J(n)？

因为有 J(10)=5，所以我们猜测有 J(n)=n2，但是一些简单的如同表1的例子否定了这个猜测。

Table 1: 猜测

n	1	2	3	4	5	6
Jn	1	1	3	1	3	5

不过我们可以大胆猜测， J(n)一定是奇数，因为绕圈走一圈就消去了全部的偶数。如果 n 是偶数，则走一圈后除了仅剩下一半人口并且他们的号码有变化外，我们面临的情形是与刚开始相同的情形，如图2所示：

如此，规模为 2n 问题就变成了规模为 n 的问题。这个规模为 n 的问题与原来相比只是在人员的序号上有所不同，具体说来就是除了每个人的号码加倍并减去1外， J(2n) 问题和 2J(n)−1问题没有什么区别。即

J(2n)=2J(n)−1,n≥1

由上文我们知道 J(10)=5，几乎瞬间我们就会知道 J(20)=2J(10)−1=2∗5−1=9。如此可以瞬间解决所有的 J(5∗2m),m≥1问题， J(5∗2m)=2J(5∗2m−1)+1=2∗2m+1=2m+1+1，这一步隐含了数学归纳法的证明过程。

假设 n 是奇数，与偶数不同的情形在于，转第一圈后就把编号为1的人给杀掉了，第二圈开始是从编号为3的人开始的，第二圈开始后第一个要杀掉的人是5。

如此， J(2n+1)问题就简化为 2J(n)+1问题，即：

J(2n+1)=2J(n)+1,n≥1

综上，约瑟夫问题递归式可以总结为：

J(1)=1J(2n)=2J(n)−1J(2n+1)=2J(n)+1

从约瑟夫递归式可以看出，不同于汉诺塔和披萨饼问题，约瑟夫问题递归式给出的不是 J(n) 和 J(n−1) 之间的递归关系，而是 J(2n) 或者 J(2n−1) 与 J(n) 之间的关系。

有了递归式，我们计算一些较小的值，如表2所示。

Table 2: 递归式得出的一些解

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

显然，从表2可以看出，将 n 按照 2的幂次进行分组或许会出现一些转机。每一组开始的 J(n) 总是等于1。仔细观察上表，如果将 n 写作 2m+l，则 J(n)=J(2m+l)=2l+1,m≥0≤l<2m. 其中 2m是不超过 n 的 2的最大幂，而 l=n−2m。事实上，可以对 m 使用数学归纳法证明：

J(n)=J(2m+l)=2l+1,m≥0≤l<2m

如此，我们得出了约瑟夫问题的闭式解。对于 J(100) 因为 100=26+36，所以 J(100)=2∗36+1=73

接下来我们针对约瑟夫问题做一些深入的挖掘。在求解约瑟夫问题递归式闭式解的过程中， n 和 J(n) 的以2为基的表示发挥着重要的作用，我们自然要研究以2为基的表示与约瑟夫问题之间的关系。假设 n 的二进制表示为：

n=(bmbm−1…b1b0)2

即， n=bm2m+bm−12m−1+b12+b0，其中 bi,i=0,1,…,m−1 为 0 或者 1。 bm=1，注意 n=2m+l，所以：

n=(1bm−1…b1b0)2l=(0bm−1…b1b0)22l=(bm−1…b1b00)22l+1=(bm−1…b1b01)2J(n)=(bm−1…b1b0bm)2

即，我们得到了：

J((bmbm−1…b1b0)2)=(bm−1bm−2…b1b0bm)2

在计算机程序设计过程中，只需要对 n 的二进制表示循环左移1位即可得到 J(n)!!!这是多么的令人激动啊！在刚开始的时候，我们看约瑟夫问题显得好困难，但是，此刻我们只需要对n 的二进制表示循环左移1位即可得到 J(n)!!! 对一个问题深入分析竟然可以得到如此精妙而简洁的答案！高老头不愧是高老头！

还以 J(100) 为例， 因为 100=(1100100)2，所以 J((1100100)2)=(1001001)2=73 !!!

接下来跟进一步深入挖掘该问题，对约瑟夫递归式做更进一步的推广。如下：

f(1)=αf(2n)=2f(n)+βf(2n+1)=2f(n)+γ

可以看出在约瑟夫问题中， α=1,β=−1,γ=1。接下来，我们依然从小入手，得出表3。

Table 3: 约瑟夫推广的解

n	f(n)
1	α
2	2α+β
3	2α+ +γ
4	4α+3β
5	4α+2β+γ
6	4α+β+2γ
7	4α+ +3γ
8	8α+7β
9	8α+6β+γ

从上表我们可以看出， α 的系数是2的幂，且不超过n。 β 的系数则从2的幂减一递减到0，γ 的系数则从0开始递增直到2的幂减一。于是式(1)的解可以表示为：

f(n)=A(n)α+B(n)β+C(n)γ

则， A(n),B(n),C(n)可以分别表示为：

A(n)=2mB(n)=2m−1−lC(n)=l

其中， n=2m+l,0≤l<2m,n≥1. 对式(13)用数学归纳法可以证明。

联想到之前采用二进制表示约瑟夫问题的解：

J((bmbm−1…b1b0)2)=(bm−1bm−2…b1b0bm)2

n 的循环左移即是 J(n) 的解。那么对于式(15) 这个更一般的推广，有没有二进制表示呢？ 当然有！ 首先式（15） 可以改写为：

f(1)=αf(2n+j)=2f(n)+βj,j=0,1

则式(???)可以改写为：

f((bmbm−1…b1b0)2)=2f((bmbm−1…b2b1)2)+βb0=4f((bmbm−1…b3b2)2)+2βb1+βb0=8f((bmbm−1…b4b3)2)+4βb2+2βb1+βb0⋮=2mf((bm)2)+2m−1βbm−1+…+2βb1+βb0=2mα+2m−1βbm−1+…+2βb1+βb0

最后，可得：

f((bmbm−1…b1b0)2)=(αβbm−1βbm−2…βb1βb0)2

事实上我们对 f(n)的前几个解稍加整理即可看出式 (18) 的精妙。

n	f(n)
1	α
2	2α +β
3	2α +γ
4	4α + 2β + β
5	4α + 2β + γ
6	4α + 2γ+β
7	4α + 2γ+γ

在此， 我们有 β0=β,β1=γ. 仍然以 J(100) 为例，因为 100=(1100100)2， 其解为：

(αβbm−1βbm−2…βb1βb0)2=(1β1β0β0β1β0β0)2

因为 α=1,β0=β=−1,β1=γ=1 ，所以 式(19)可以重写为：

(1β1β0β0β1β0β0)2=(11−1−11−1−1)2=73

注意在此，我们突破了二进制只有0和1的限制，不过这一突破使得约瑟夫的解更加的精炼。

可以沿着推广2的思路走的更远，我们对式12做更进一步修改：

f(j)=αj,1≤j<df(dn+j)=cf(n)+βj,0≤j<d

式21有变动基数的解：

f((bmbm−1…b1b0)d)=(αbmβbm−1βbm−2…βb1βb0)c

约瑟夫有一个朋友，他站在倒数第二个位置上因而获救。当每隔一个人就有一个人被处死时，倒数第二个幸存者 I(n) 的号码是多少？

每隔一个人就有一个人被处死的约瑟夫问题解为：

J(n)=J(2m+l)=2l+1

此时有： 2l+1=n−1→n=2l+2 ，满足此式的 n 总是倒数第二个位置上的人获救。