《CM》1.3 The Josephus Problem

1.3 The Josephus Problem 约瑟夫问题

约瑟夫问题:编号从1开始的n个人顺序围成一圈,从1号开始,每2个人就把他杀掉,如前几个被杀序列为:2,4,...求最后的幸存者编号,用J(n)表示。显然J(1) = 1, J(2) = 1, ...

考虑人数为偶数的情况,假设为2n。再依次杀掉编号为2, 4, ..., 2n - 2, 2n这n个人之后,剩下的n个人编号为1, 3, ..., 2n - 1,并且再次从1号开始,每2人把他杀掉,而这就是n个人的约瑟夫问题。如果我们把这剩下的n个人重新编号成1, 2, ..., n,我们知道幸存者编号为J(n),对应于原来的编号即为2J(n)-1。于是我们知道

J(2n) = 2J(n) - 1, for n≥1。

同理可得

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

于是我们得到递归式

J(1) = 1,
J(2n) = 2J(n) - 1, for n≥1,
J(2n + 1) = 2J(n) + 1, for n≥1.

打表找规律可以发现递归式的解为:

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

同样的,数学归纳法可以很容易证明上式的正确性。

考虑把n写成2进制形式:

n = (bmbm-1...b1b0)2
= bm2m + bm-12m-1 + ... + b12 + b0,

其中bm等于1,bi等于1或0,于是当n = 2m + l时,

n = (1bm-1...b1b0)2
l = (0bm-1...b1b0)2
2l + 1 = (bm-1...b1b01)2
J(n) = 2l + 1 = (bm-1...b1b0bm)2.

所以有:

J((bmbm-1...b1b0)2) = (bm-1...b1b0bm)2.

这就是说,只要我们把n写成没有前导0的2进制形式,然后循环左移一位就得到了J(n)!这个结果是非常美妙的!比如这告诉我们,如果对一个数连续应用若干次J操作,即J(J(...J(n)...)),最后结果会停留在某个数2v(n) - 1上,其中v(n)是n的2进制形式中1的个数。

现在,尝试对上述递归式进行扩展,考虑如下递归式:

f(1) = α,
f(2n) = 2f(n) + β, n≥1,
f(2n+1) = 2f(n) + γ, n≥1.

打个表发现,似乎f(n)可写成如下形式:

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

其中A(n),B(n),C(n)是只和n有关的函数,并且可以发现

A(n) = 2m,
B(n) = 2m - l - 1,
C(n) = 1.

其中n = 2m + l and 0≤l<2m, for n>=1。

用数学归纳法可以证明上述的解是正确的,然而,当我们发现f(n)可写成类似(1)那种形式时,有一种不用猜想也可以方便的求出A(n),B(n),C(n)的方法,这种方法叫做"repertoire method"。(当然前提你要证明f(n)确实能够表示成一些和参数无关的函数与对应参数的线性组合,即(1)那种形式,可用数学归纳法

不好用语言来描述这个方法,大概就是对一些特定的参数,可快速求出f(n)。或者是对一些特定的f(n),可以快速求出对应参数。总之,以当前的例子来说,就是需要一些这样的序对(f(n), α, β, γ)。有多少个参数就需要多少个这样的线性无关的序对,这样就有对应多个方程,即可解出各参数的系数A(n), B(n), ...等。

如令f(n) = 1,代入递归式可解得α = 1,β = -1,γ = -1,于是得到一个序对(1, 1, -1, -1)

令α = 1,β = γ = 0,可求得f(n) = 2m,其中n = 2m + l, 0≤l<2m。于是得到另一个序对(2m, 1, 0, 0)

再令f(n) = n,代入递归式可得到α = 1,β = 0,γ = 1,于是得到最后一个序对(n, 1, 0, 1)

有了这3个序对,实际上我们就有3个方程:

1 = A(n) - B(n) - C(n),
2m = A(n),
n = A(n) + C(n).

求出这个方程组的解,即可得到A(n),B(n),C(n),和上述找规律看出的解是一致的。

关于"repertoire method"方法的正确性很显然,由线性方程组的解结构可知,当系数矩阵为列满秩矩阵,特别的,如果方程数和未知数个数相同时,行列式值不为0,方程组有唯一的解。

如果把上述f(n)的递归式写成这样:

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

其中β0 = β,β= γ。

同样把n写成2进制形式,可以得到

f((bmbm-1...b1b0)2) = 2f((bmbm-1...b1)2) + βb0
= 4f((bmbm-1...b2)2) + 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(j) = αj, 1≤j<d,
f(dn + j) = cf(n) + βj, 0≤j<d, n≥1.

其解为:

f((bmbm-1...b1b0)d) = (αβbm-1βbm-2...βb1βb0)c.

相当beautiful!!



2 thoughts on “《CM》1.3 The Josephus Problem

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*