UTF8gbsn

Intro

这个约瑟夫问题稍微有些复杂。是一群人排成一个圈，已一个人为1号然后编号。然后隔一个人杀掉一个。知道最后剩下一人。问题是问剩下的一个人的编号是多少？我们还是按照三步走的策略来看这个问题。

Step1

从简单特例出发，假如$1,2,3,4,5,6,7,8,9,10$1,2,3,4,5,6,7,8,9,10排成一个圈。那么被杀掉的人的顺序是2,
4, 6, 8, 10, 3, 7, 1, 9。最后幸存者是5号。

Step2

我们很自然的从奇数，偶数的方向上来考虑这个问题。当n是偶数的时候。第一轮杀人之后剩下的全是奇数。比如$n=2k$n=2k,那么第一轮剩下的人为

even

$1,3,5,...,2k-1 \rightarrow 1,2,3,...,k$1,3,5,...,2k−1→1,2,3,...,k

从这个映射表可以看书。k个人参与游戏的结果$j(k)$j(k)和2k个人参与游戏的结果之间有着一定的关系

$j(2k)=2j(k)-1, k\geqslant 1$j(2k)=2j(k)−1,k⩾1

odd

对于$n=2k+1$n=2k+1的情况来看。这个时候我们可以发现杀掉一轮之后剩下的人为$3,5,...,2k+1$3,5,...,2k+1。那么我们来看看对应关系

$3,5,...,2k+1 \rightarrow 1,2,3,...,k$3,5,...,2k+1→1,2,3,...,k

所以，我们可以从上面的映射中得出

$j(2k+1)=2j(k)+1,k\geqslant 1$j(2k+1)=2j(k)+1,k⩾1

conclusion

$\begin{aligned} J(1) &=1 & & \\ J(2 n) &=2 J(n)-1 & & \text { for } n \geqslant 1 \\ J(2 n+1) &=2 J(n)+1 & & \text { for } n \geqslant 1 \end{aligned}$J(1)J(2n)J(2n+1)​=1=2J(n)−1=2J(n)+1​​ for n⩾1 for n⩾1​

Step3

在我们得出递推公式之后，我们不妨列举几个简单的例子。

通过观察这个数列。我们可以得出如下公式

$\mathrm{J}\left(2^{\mathrm{m}}+h\right)=2 \mathrm{h}+1, \quad \text { for } \mathrm{m} \geqslant 0 \text { and } 0 \leqslant h<2^{\mathrm{m}}$J(2m+h)=2h+1, for m⩾0 and 0⩽h<2m

这里出现了二进制形式。我们自然想到利用二进制来解决上面的公式。

$\mathrm{n}=\mathrm{b}_{\mathrm{m}} 2^{\mathrm{m}}+\mathrm{b}_{\mathrm{m}-1} 2^{\mathrm{m}-1}+\cdots+\mathrm{b}_{1} 2+\mathrm{b}_{0}$n=bm​2m+bm−1​2m−1+⋯+b1​2+b0​

推理过程如下

$\begin{aligned} \mathrm{n} &=\left(1 \mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0}\right)_{2} \\ \mathrm{h} &=\left(0 \mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0}\right)_{2} \\ 2h &=\left(\mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0} \mathrm{0}\right)_{2} \\ 2 \mathrm{h}+1 &=\left(\mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0} 1\right)_{2} \\ \mathrm{J}(\mathrm{n}) &=\left(\mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0} \mathrm{b}_{\mathrm{m}}\right)_{2} \end{aligned}$nh2h2h+1J(n)​=(1bm−1​bm−2​…b1​b0​)2​=(0bm−1​bm−2​…b1​b0​)2​=(bm−1​bm−2​…b1​b0​0)2​=(bm−1​bm−2​…b1​b0​1)2​=(bm−1​bm−2​…b1​b0​bm​)2​​

结论是

$\mathrm{J}\left(\left(\mathrm{b}_{\mathrm{m}} \mathrm{b}_{\mathrm{m}-1} \ldots \mathrm{b}_{1} \mathrm{b}_{0}\right)_{2}\right)=\left(\mathrm{b}_{\mathrm{m}-1} \ldots \mathrm{b}_{1} \mathrm{b}_{0} \mathrm{b}_{\mathrm{m}}\right)_{2}$J((bm​bm−1​…b1​b0​)2​)=(bm−1​…b1​b0​bm​)2​

上面的公式就是我们最终的解。这个解，是非常容易用程序实现的。接下来我们来看看两个特殊的解。

1. $J(n)=n$J(n)=n,那么n是多少的时候$J(n)=n$J(n)=n?我们不妨来看看迭代J会怎么样。比如
   $J(J(J(...J(101010110_2))))$J(J(J(...J(1010101102​))))
   假如我们迭代无限次。最终上面式子会变成多少？聪明的读者已经看出来了。因为J实际上是一个把第一位非0拿到尾部的一个操作。
   $J(101010110_2)=10101101_2 \Rightarrow J(10101101_2)=1011011_2 \Rightarrow J(1011011_2)=110111_2 ...$J(1010101102​)=101011012​⇒J(101011012​)=10110112​⇒J(10110112​)=1101112​...

   $J(J(J(...J(101010110_2))))=11111_2$J(J(J(...J(1010101102​))))=111112​
   这个$11111_2$111112​是一个不动点。也就是说J(11111)=11111.由此可见只要n的二进制表示形式为全1，那么n就是一个不动点。而$J(n)=n$J(n)=n

2. $J(n)=n/2$J(n)=n/2,我们根据递通项公式来看看如何，找满足条件$J(n)=n/2$J(n)=n/2的所有n.我们不难发现
   $\left. \begin{aligned} J(n)&=n/2\\ 2h+1=(2^m+h)/2\\ h=\frac{1}{3}(2^m-2) \end{aligned} \right.$J(n)2h+1=(2m+h)/2h=31​(2m−2)​=n/2

   由此可见只要$2^m-2$2m−2能被3整除。那么$2^m+\frac{1}{3}(2^m-2)=2^m+h=n$2m+31​(2m−2)=2m+h=n就是满足$J(n)=n/2$J(n)=n/2的解。而我们来看$2^m-2$2m−2这样的数在什么情况下能被3整除？我们这里不给出证明，以后会讲到这一部分内容。现在只是给出结论。也就是当m为奇数的时候$2^m-2$2m−2就能被3整除。所以，我们可以得出下表。

   

   由此可见只要确定m为奇数所有的$J(n)=n/2$J(n)=n/2的n，都可以确定出来。也可以通过二进制形式弄出来。注意这里的逻辑是，根据奇数的m计算出$h=\frac{1}{3}(2^m-2)$h=31​(2m−2)，然后就确定出了$n=2^m+h$n=2m+h

extend

clairvoyant

扩展问题，我们的递推公式为。
$\begin{aligned} J(1) &=1 & & \\ J(2 n) &=2 J(n)-1 & & \text { for } n \geqslant 1 \\ J(2 n+1) &=2 J(n)+1 & & \text { for } n \geqslant 1 \end{aligned}$J(1)J(2n)J(2n+1)​=1=2J(n)−1=2J(n)+1​​ for n⩾1 for n⩾1​

这是一大类问题的特例。下面这种是这一大类问题的一般形式。

$\begin{aligned} f(1) &=\alpha & & \\ f(2 n) &=2 f(n)+\beta, & & \text { for } n \geqslant 1 \\ f(2 n+1) &=2 f(n)+\gamma, & & \text { for } n \geqslant 1 \end{aligned}$f(1)f(2n)f(2n+1)​=α=2f(n)+β,=2f(n)+γ,​​ for n⩾1 for n⩾1​

还是按照三步走，这一步是先简单的特列写出来

我们很容易得出一个简单的公式

$\mathrm{f}(\mathrm{n})=\mathrm{A}(\mathrm{n}) \mathrm{a}+\mathrm{B}(\mathrm{n}) \beta+\mathrm{C}(\mathrm{n}) \gamma$f(n)=A(n)a+B(n)β+C(n)γ

其中
$\begin{array}{l}{\mathrm{A}(\mathrm{n})=2^{\mathrm{m}}} \\ {\mathrm{B}(\mathrm{n})=2^{\mathrm{m}}-1-h} \\ {\mathrm{C}(n)=h}\end{array}$A(n)=2mB(n)=2m−1−hC(n)=h​

method

证明上面的式子，只需要归纳法即可。但是如何要计算上面的式子，却不是那么直观。我们是根据简单的例子，靠直觉在构造形式，然后用归纳法证明。所以这种做法实际上需要一定的敏锐程度的人才能找到解决方案。但是如果不那么敏锐和聪明的人如何来解决这个问题呢？作者在这里提出了另一种方法步骤。首先让我们来回归一下这个一般化的问题。

$\begin{aligned} f(1) &=\alpha & & \\ f(2 n) &=2 f(n)+\beta, & & \text { for } n \geqslant 1 \\ f(2 n+1) &=2 f(n)+\gamma, & & \text { for } n \geqslant 1 \end{aligned}$f(1)f(2n)f(2n+1)​=α=2f(n)+β,=2f(n)+γ,​​ for n⩾1 for n⩾1​

我们对于上面的公式有三个参数。$\alpha,\beta,\gamma$α,β,γ,我们自然可以设通项公式为
$f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma$f(n)=A(n)α+B(n)β+C(n)γ

我们如何来求解三个参数呢？注意首先要确定上面的等式的参数是啥？$A(n),B(n),C(n)$A(n),B(n),C(n)是目标参数。为了求出这三个参数，我们可以靠特殊的$\alpha,\beta,\gamma$α,β,γ来求出$A(n),B(n),C(n)$A(n),B(n),C(n)

1. 先把$B(n),C(n)$B(n),C(n)消除，来求参数$A(n)$A(n).我们可以设$\alpha=1,\beta=\gamma=0$α=1,β=γ=0.这样我们就可以得到
   $f(n)=\alpha A(n)$f(n)=αA(n)

   $\begin{aligned} \mathrm{A}(1) &=& 1 \\ \mathrm{A}(2 \mathrm{n}) &=2 \mathrm{A}(\mathrm{n}), & & \text { for } \mathrm{n} \geqslant 1 \\ \mathrm{A}(2 \mathrm{n}+1) &=2 \mathrm{A}(\mathrm{n}), & & \text { for } \mathrm{n} \geqslant 1 \end{aligned}$A(1)A(2n)A(2n+1)​==2A(n),=2A(n),​1​ for n⩾1 for n⩾1​

   从上面的公式来看。我们按照前面的方法。列举17来个特例，就能提出结论。
   $A(n)=A(2^m+h)=2^m$A(n)=A(2m+h)=2m

2. 下面我们看看特殊的$f(n)$f(n),加入$f(n)=1$f(n)=1
   $\begin{aligned} \mathbf{1} &=\alpha \\ \mathbf{1} &=2 \cdot 1+\beta \\ \mathbf{1} &=2 \cdot 1+\gamma \end{aligned}$111​=α=2⋅1+β=2⋅1+γ​

   我们得出结论

   $A(n)-B(n)-C(n)=f(n)=1$A(n)−B(n)−C(n)=f(n)=1

3. 再看我们看看特殊的$f(n)$f(n),加入$f(n)=n$f(n)=n

   $\begin{aligned} 1 &=\alpha \\ 2 \mathrm{n} &=2 \cdot \mathrm{n}+\beta \\ 2 \mathrm{n}+1 &=2 \cdot \mathrm{n}+\gamma \end{aligned}$12n2n+1​=α=2⋅n+β=2⋅n+γ​

   通过上面的式子我们，可以得到如下等式
   $\mathrm{A}(\mathrm{n})+\mathrm{C}(\mathrm{n})=\mathrm{n}$A(n)+C(n)=n

最后，我们总结结论。

$\begin{aligned} A(n) &=2^{m} \\ A(n)-B(n)-C(n) &=1 \\ A(n)+C(n) &=n \end{aligned}$A(n)A(n)−B(n)−C(n)A(n)+C(n)​=2m=1=n​

这就是前面的我们使用观察法弄出来的公式。而在这里我们是用的一种方法论的东西。我们用特殊$\alpha,\beta,\gamma$α,β,γ来求出参数$A(n),B(n),C(n)$A(n),B(n),C(n).这种方法，对于解是线性参数的线性组合的方式更有效$f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma$f(n)=A(n)α+B(n)β+C(n)γ。

binary solution

那么对于一般的形式我们可不可以有类似二进制的解？答案是肯定的。我们可以这么来变换形式

$\begin{aligned} f(1) &=\alpha \\ f(2 n+j) &=2 f(n)+\beta_{j}, \quad \text { for } j=0,1 \text { and } \quad n \geqslant 1 \end{aligned}$f(1)f(2n+j)​=α=2f(n)+βj​, for j=0,1 and n⩾1​

其中，$\beta_0=\beta,\beta_1=\gamma$β0​=β,β1​=γ.

$\begin{aligned} f\left(\left(b_{m} b_{m-1}, \ldots b_{1} b_{0}\right)_{2}\right) &=2 f\left(\left(b_{m} b_{m-1} \ldots b_{1}\right)_{2}\right)+\beta_{b_{0}} \\ &=4 f\left(\left(b_{m} b_{m-1} \cdot \cdot b_{2}\right)_{2}\right)+2 \beta_{b_{1}}+\beta_{b_{0}} \\ &=2^{m} f\left(\left(b_{m}\right)_{2}\right)+2^{m-1} \beta_{b_{m-1}}+\cdots+2 \beta_{b_{1}}+\beta_{b_{0}} \\ &=2^{m} \alpha+2^{m-1} \beta_{b_{m-1}}+\cdots+2 \beta_{b_{1}}+\beta_{b_{0}} \end{aligned}$f((bm​bm−1​,…b1​b0​)2​)​=2f((bm​bm−1​…b1​)2​)+βb0​​=4f((bm​bm−1​⋅⋅b2​)2​)+2βb1​​+βb0​​=2mf((bm​)2​)+2m−1βbm−1​​+⋯+2βb1​​+βb0​​=2mα+2m−1βbm−1​​+⋯+2βb1​​+βb0​​​

注意当是二进制的时候，我们的$\alpha,\beta_i$α,βi​都需要是0或1。如果我们允许$\alpha,\beta_i$α,βi​
超越0,1我们就可以写成以下形式

$f\left(\left(b_{m} b_{m-1}... b_{1} b_{0}\right)_{2}\right)=\left(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{2}$f((bm​bm−1​...b1​b0​)2​)=(αβbm−1​​βbm−2​​…βb1​​βb0​​)2​

extend the previous extension

我们现在来看更为一般的扩展

$\begin{aligned} f(j)=\alpha_{j}, & \text { for } 1 \leqslant j<d \\ f(d n+j)=c f(n)+\beta_{j}, & \text { for } 0 \leqslant j<d \text { and } n \geqslant 1 \end{aligned}$f(j)=αj​,f(dn+j)=cf(n)+βj​,​ for 1⩽j<d for 0⩽j<d and n⩾1​

按照相同的逻辑，我麽可以推出。

$f\left(\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{d}\right)=\left(\alpha_{b_{m}} \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{c}$f((bm​bm−1​…b1​b0​)d​)=(αbm​​βbm−1​​βbm−2​​…βb1​​βb0​​)c​

这是最后我们得到的结论。可见从最初的问题，我们一层一层的扩展。最终得出上面这个等式。这是非常有趣的结果。

The End

现在，我们最终得到公式是具有非常一般性的结论。大家有兴趣的可以反复读读具体数学[1]这个部分的内容。非常精彩。

References

[1] Ronald L. Graham, Donald E. Knuth, O. P. (n.d.). Concrete
mathematics. In Concrete. page(8-16)