的来源是这样的:在犹太罗马战争期间,41名犹太反抗者困在了罗马人包围的洞穴中。这些反抗者宁愿自杀也不愿被活捉,于是决定围成一个圈,并沿着圆圈每隔两人杀死一人,直到剩下最后两人为止。但是约瑟夫和一个未被告发的同谋者不希望无谓地自杀,于是他迅速计算出他和其朋友在这个圆圈中应该站的位置。
现在我们把问题抽象一下:从围成标有几号 1 到 n 的圆圈的 n 个数开始,每隔一个数就删去一个数,直到剩下最后一个数,要求解剩余数的一般表达式 J(n)。
而 3 是下一个要被删除的数。除每个数加倍然后减 1 以外,这正像是对应 n 个人开始时的情况。也就是说:
很容易注意到,可以按照 2 的幂将表中的数据分组,在每一组的开始 J(n) 都为 1,且组内数据每次递增 2。因此,递归式地解似乎可以写成这样:
对于上式的证明,可以使用数学归纳法:当 m 为 0 时必然有 l = 0,于是 J(1)=1;下一步证明需要分奇偶分别讨论.
问题的每一个解都可以加以推广,使得它能运用于更加一般的问题,这是一件很有启发意义的事情。接下来,我们将对上诉递归式以及递归式地解进行推广,揭示所有这类问题背后所隐藏的结构。
在求解过程中,我们注意到 2 的幂起到了重要作用。一个很自然的想法就是研究 n 和 J(n) 的以 2 为基数的表示。假设 n 的二进制表示为:
另一个值得注意的现象是,如果重复进行循环左移,即重复运用 J 函数,会出现首位数字为 0 的情况,这种情况下数的位数将会减少,即首位 0 将会被丢弃。重复运用 J 会得到一列递减的值,它们最终会到达一个不动点。利用循环左移的性质不难发现,最后的不动点全由 1 组成,它的值为,其中 v(n) 是二进制表示中 1 的个数。
下一步我们要推广的递归式 J,看看在一般情况下形如递归式 J 的函数该如何求出一个封闭形式的解。
用归纳法证明上述猜想并不困难,但是计算起来比较复杂,这里介绍一个更好的方法,通过取特殊值,然后将它们组合起来。
接下来,反过来使用一般递归式以及其一般解,从一个简单的函数 f(n)出发,研究是否有任何常数(α,β,γ)能定义它。
现在,我们证明了在一般情况解该一般递归式时,所得到的解中函数 A(n)、B(n)、C(n)满足方程:
这一解题方法称为成套方法。成套方法的一般步骤是:寻求一组已知其解的通用参数,然后将特殊情况组合起来得到一般的情形,有多少个独立的参数就需要多少个独立的特解。
上文以及证明了对于约瑟夫问题,可以用二进制表示巧妙的解决,那么对于推广的约瑟夫问题是否也存在相应的奇妙解法呢?
① 改变进制看问题有时候会收获奇效。我们总是习惯于十进制,而现实中很多问题在十进制下很难看出规律,这个时候不妨转换一下进制,说不定规律会脱颖而出。
② 从一个普通的问题到一类问题,这是问题的抽象。对于解决抽象问题,它涉及到的方法一般都源于它的某一个具体问题。而从具体问题上升到抽象问题,然后寻找这类问题的通解,这往往能够揭示问题的本源。