约瑟夫问题递推解以及非递推解推导

约瑟夫问题

约瑟夫斯置换是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又被称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，处刑下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

—— 来自Wikipedia

问题假设

为了方便研究，我们设最开始的总人数为n，每次跳过的人数为k，并且人的编号从0开始。

对于递推公式的证明，本文推广到了跳过人数k为任意值的情况；对于非递推公式，由于过于复杂，所以只能证明到k=2的情况。

递推公式证明

假设编号从0开始，现证明约瑟夫问题的递推公式为：

$$J(n) = \begin{cases} 0, \ n=1\\ (J(n-1)+2) \mod n \end{cases}$$

考虑有n个人的情况，则这些人编号为$0,1,2,\cdots,n-1$。则当报数为2的人，即1号被杀掉时，这些人编号依次为$0,2,3,\cdots,n-1$，则可以把问题从n的规模减少到n-1。此时还需继续报数，由于约瑟夫问题是按环报数的，所以我们可以把之前报过数的人重新安排到序列的末尾，则现在的编号依次为：$2,3,4,\cdots,n-1,0$。

如果我们将这些人序号限制在大小为n的群上，则被重新排列到末尾的人$i$也可以被编号为$i+n$。那么此时的编号即为$2,3,4,\cdots,n-1,n$。依此类推，可以把规模为n的情况转化为规模为1的情况，但是需要推理编号的关系。

原n-1情况下编号为$0,1,2,\cdots,n-1$，由n情况下递推回去的编号为$2,3,4,\cdots,n-1,n$，则可以推出一般情况下的递推公式为$(J(n-1)+2) \mod n$。

不失一般性，但约瑟夫问题报数的轮次为$k$时，可以用同样的证法证明，递推公式为：

$$J(n) = \begin{cases} 0, \ n=1\\ (J(n-1)+k) \mod n \end{cases}$$

非递推公式证明

当$k=2$时，约瑟夫问题的非递推公式为

$$\large J(n) = 2(n - 2^{\lfloor\log_2n\rfloor})$$

证明如下：

使用数学归纳法，当$n=1$时，有$J(1)=0$，$n=2$时，有$J(2)=0$，显然成立。

假设上述公式对于$n=i, \ i\ge1$成立，即：

$$\large J(i) = 2(i - 2^{\lfloor\log_2i\rfloor})$$

则当$n=i+1$时：

若$i+1=2^k,\ k \in \N$，此时$\lfloor\log_2i\rfloor=k-1, \lfloor\log_2{i+1}\rfloor=k$，根据递推公式：

$$\begin{aligned} J(i+1) &= (J(i)+2) \ &\mod{i+1}\\ &=2(i-2^{\lfloor\log_2i\rfloor})+2 &\mod{i+1}\\ &=2(2^k-1-2^{k-1})+2 &\mod{i+1} \\ &=2^k &\mod{k^k} &\\ &= 0 \\ &= 2(i+1-2^{\lfloor\log_2{i+1}\rfloor}) \end{aligned}$$

若$i+1\neq2^k, k\in\N$，我们可以假设$2^{k-1}\le i\lt2^k$，则$\lfloor\log_2i\rfloor=k-1,\lfloor\log_2{i+1}\rfloor=k-1$，根据递推公式：

$$\begin{aligned} J(i+1) &= J(i)+2 &\mod{i+1}\\ &=2(i-2^{\lfloor\log_2i\rfloor})+2 &\mod{i+1}\\ &=2(i-2^{k-1})+2 &\mod{i+1}\\ &=2(i+1-2^{\lfloor\log_2{i+1}\rfloor}) &\mod{i+1}\\ &= 2(i+1-2^{\lfloor\log_2{i+1}\rfloor}) \end{aligned}$$

所以综上所述，若当$n=i$时非递推公式成立，则$n=i+1$时非递推式也成立。

证毕。