圆圈问题的解

上篇日志里的题目是这样的:假设$latex n$个人站成一圈编号依次是$latex \left(a_0…a_{n-1}\right)$,现在开始从$latex a_0$开始报数$latex \left(0, 1, 2…\right)$,每报到$latex m$的人站出,然后站出的后一个人继续报数,最后只剩下一个人。试以$latex n$和$latex m$表示最后剩下人的编号。

我觉得这个问题如果能用抽象代数的循环群、商环概念应该会清晰很多,可惜我没学过抽象代数,所以请允许我在这里用比较低等的数学思想解决这道问题。

这道题摆上来,很容易想到用余数来做,但是在做的过程中可能会碰到这样的问题。比如:

设$latex p_k$是进行$latex k$轮后的启始人,那么不难列出以下算式:

$latex p_0=0\\
p_k=(p_{k-1}+m) \mod{(n-k)}$

但是,这个式子的问题是,每轮下来得到的$latex p_k$都是经过重新编号的序号,最后的$latex p_{n-1}$必然是0,然而我们并不需要这样的答案。

在我看来,如果用低等的数学思想解决这道题,必须用一种递归思路从结果反推。我们应该把每一种$latex n$的解建立在它的子集$latex n-1$的解的基础上。

假设现在圆圈(集合)里只有一个元素既$latex a_0$,那么无论$latex m$是多少,这个集合最后剩下的元素必然是$latex a_0$。用数学语言说,
定义$latex f_n\left(m\right)$是循环群$latex \mathbb{Z}/n\mathbb{Z}$上的一个函数,$latex f_n\left(m\right)$为$latex \mathbb{Z}/n\mathbb{Z}$筛选至最后一个元素的编号,
那么我们可以给出:$latex f_1\left(m\right)=0$。

接下来,假设在刚才的零集合上加一个元素$latex a_1$,并对现有集合重新编号$latex \left(b_0,b_1\right)$,
使得这一轮开始报数的元素记为$latex b_0$,
且使得保留的是原先的$latex b_j=f_2 \left(m\right)=\left( a_0+m+1 \right) \mod{2}$。
注意,$latex a_0$既是被唯一保留下来的元素也是被删除元素的后继元素,$latex m \mod{n}$是下一个删除元素,保留的则是$latex (m+1) \mod{n}$。

假设在刚才的$latex \mathbb{Z}/2\mathbb{Z}$上再加一个元素$latex b_2$,
与上一步一样再次重新编号$latex \left(c_0,c_1,c_2\right)$,使得这一轮开始报数的元素记为$latex c_0$,
且使得下一轮开始是删除元素的后继元素,
即$latex c_{0}=\left(b_{0}+m+1\right) \mod{3}$,
由于删除元素是开始元素的前一个,那么删除该元素后,开始元素与目标元素的距离不变,
所以可以在等式两边进行位移,
即$latex c_{q}=\left(b_{j}+m+1\right) \mod{3}$,($latex c_{q}$是目标元素)
由上一步等式可以推出,
$latex f_3\left(m\right)=c_q=\left(b_j+m+1\right) \mod{3}\\=\left(\left(\left(a_0+m+1\right) \mod{2}\right)+m+1\right) \mod{3}=\left(f_2\left(m\right)+m+1\right) \mod{3}$。

最后,概括地说,
定义$latex P=\{a_0…a_{n-2}\ |\ a_i\in\mathbb{Z}/\left(n-1\right)\mathbb{Z}\}$使得$latex a_x=f_{n-1}\left(m\right)$,
现在$latex P$上再加一个元素$latex a_{n-1}$,并定义集合$latex P^{‘}=\{a^{‘}_0…a^{‘}_{n-1}\ |\ a^{‘}_i\in\mathbb{Z}/n\mathbb{Z}\}$与$latex P$同构,
且使得
$latex \begin{cases}a^{‘}_{0}=\left(a_{0}+m+1\right)\mod{n}\\a^{‘}_{q}=\left(a_{x}+m+1\right)\mod{n}\end{cases}$,
那么,$latex f_n\left(m\right)=a^{‘}_q=\left(a_{x}+m+1\right)\mod{n}=\left(f_{n-1}\left(m\right)+m+1\right)\mod{n}$。

所以,f可以写成如下形式:
$latex \begin{cases}f_1\left(m\right)=0\\
f_n\left(m\right)=\left(f_{n-1}\left(m\right)+m+1\right) \mod{n} \end{cases}$