The Josephus Problem

简介

约瑟夫问题:

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

现在我们将问题一般化,即问题为:

n个人围成一圈,从围成标记号为1到n的圆圈的n个人开始,每隔一个删去一个人,直到只有一个人幸存下来。求确定幸存者的号码 $J(n)$

解法

递归

不妨从奇偶性开始考虑
当$n$为偶数时,我们考虑 $J(2n)$ 的情况。第一轮后,还剩下n个人。此时发现编号符合映射: $x \rightarrow y = 2x-1$,可得到 $J(2n) = 2J(n)-1$
同理,当 $n$ 为奇数时,我们考虑 $J(2n+1)$ 的情况,此时可得:$J(2n+1)=2J(n)+1$

故定义$J$的递归式为:

封闭形式

通过递归式,我们可以观察解从而将递归式转化为封闭形式的解。

$n$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
$J(n)$ 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

通过观察,如果我们将 $n$ 写成 $n=2^m+l$ ,则递归式解为:

约束条件为:

证明可用数学归纳法证明,此处略。

进制

通过求解封闭形式,我们发现2的幂起着重要作用。于是研究以2为基数的表示方法。
假设n的二进制展开式为 ${(b{_m}b_{m-1}b_{m-2}\cdots b_1b_0)}_2$ ,$b$ 取0或1,$b_m$=1.
我们依次可得:

二进制下即可数位循环移动得到最终解。

扩展

不动点

若对 $J(n)$ 不断迭代,则最后会达到一个不动点,在该点有 $J(n)=n$.
设 $J(n)$ 二进制中有k个1,则不断迭代后,$n=2^{k}-1$.

递归式通解

对n的前几项列出表格

$n$ 1 2 3 4 5 6
$J(n)$ $\alpha$ $2\alpha+\beta+0\gamma$ $2\alpha+0\beta+1\gamma$ $4\alpha+3\beta+0\gamma$ $4\alpha+2\beta+1\gamma$ $4\alpha+1\beta+2\gamma$

将 $f(n)$ 与 $\alpha,\beta,\gamma$ 的依存关系分离开来,表示为:

可通过归纳法证得:

其中有 $n=2^m+l$ 以及 $0\leq l<2^m$ $(n\geq 1)$

成套解法(repertoire method)

从 $f(n)$ 出发,并研究是否有任意常数 $(\alpha,\beta,\gamma)$ 能定义它。

当 $f(n)=1$,可得解 $(\alpha,\beta,\gamma)=(1,-1,-1)$ , $A(n)-B(n)-C(n)=f(n)=1$
同理当$ f(n)=n$ 时, $(\alpha,\beta,\gamma)=(1,0,1)$ 时对所有的n成立,故$ A(n)+C(n)=f(n)=n$

可得:

解同上.

进制通解

令 $\beta_0 = \beta$ 以及 $\beta_1 = \gamma$,则推广递归式改写成

递归式由上两式按二进制展开为:

求解结束。以下给出例子
$\alpha =1,\beta=-1,\gamma=1$,
此时 $n=(1100100)_2 = 100$
$f(n) = (1$ $ 1-1-1$ $1-1-1)_2 = +64 +32-16-8+4-2-1=73$