递归问题:约瑟夫问题

目录

1 问题描述

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

josephus-10.jpg

Figure 1: n=10的约瑟夫问题

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

2 约瑟夫问题递归式

因为有 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所示:

cat/spider image

Figure 2: n为偶数时的约瑟夫问题

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

J(2n)=2J(n)1,n1

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

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

cat/spider image

Figure 3: n为奇数时的约瑟夫问题

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

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

综上,约瑟夫问题递归式可以总结为:

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

3 约瑟夫递归式的解

从约瑟夫递归式可以看出,不同于汉诺塔和披萨饼问题,约瑟夫问题递归式给出的不是 J(n)J(n1) 之间的递归关系,而是 J(2n) 或者 J(2n1)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,m0l<2m. 其中 2m是不超过 n2的最大幂,而 l=n2m。事实上,可以对 m 使用数学归纳法证明:

J(n)=J(2m+l)=2l+1,m0l<2m

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

4 拓展1:二进制与约瑟夫问题

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

n=(bmbm1b1b0)2

即, n=bm2m+bm12m1+b12+b0,其中 bi,i=0,1,,m10 或者 1bm=1,注意 n=2m+l,所以:

n=(1bm1b1b0)2l=(0bm1b1b0)22l=(bm1b1b00)22l+1=(bm1b1b01)2J(n)=(bm1b1b0bm)2

即,我们得到了:

J((bmbm1b1b0)2)=(bm1bm2b1b0bm)2

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

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

5 拓展2:更一般的约瑟夫递归式

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

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)=2m1lC(n)=l

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

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

J((bmbm1b1b0)2)=(bm1bm2b1b0bm)2

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

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

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

f((bmbm1b1b0)2)=2f((bmbm1b2b1)2)+βb0=4f((bmbm1b3b2)2)+2βb1+βb0=8f((bmbm1b4b3)2)+4βb2+2βb1+βb0=2mf((bm)2)+2m1βbm1++2βb1+βb0=2mα+2m1βbm1++2βb1+βb0

最后,可得:

f((bmbm1b1b0)2)=(αβbm1βbm2β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, 其解为:

(αβbm1βbm2β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=(1111111)2=73

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

6 推广3:不同基底的约瑟夫递归式

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

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

式21有变动基数的解:

f((bmbm1b1b0)d)=(αbmβbm1βbm2βb1βb0)c

7 推广4:倒数第二个位置

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

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

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

此时有: 2l+1=n1n=2l+2 ,满足此式的 n 总是倒数第二个位置上的人获救。