当前位置：首页 > news >正文

2的幂在约瑟夫环问题的应用

news 来源：原创 2024/4/29 17:55:58

纽约时代Pradeep Mutalik的博客最近登了一个关于约瑟夫环的谜题。这个问题容易描述，说：有n个人站成一个环，你是其中一员。有个人站在圈外顺时针移动，并且不断每隔一人消灭圈中一人，直到最后一个人-胜利者-为止。你应该站在哪里才能胜出？

下面是13个参与者的例子：

Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)

13个人轮番消灭，消灭顺序

见红字（胜出者是11号）

如同Pradeep和他的读者指出的那样，无需画出消灭顺序-本文提供一个简便公式。此公式，不必奇怪，跟2的幂和二进制数字有关。我将讨论我喜欢的方案，基于2的幂的方案。

当参与人数是2的幂

隔位消灭意味着每两人就消灭一人。这是二等分，暗示会用到2的幂。我们先研究参与人数是2的幂的特殊情况，因为2的幂减半后还是2的幂。

下面是8人一圈的例子：

隔位消灭（8人）

消灭过程是：顺时针先隔过1号, 每次到达1号都会隔过去。被消灭的人会被划掉，并标上被消灭的次序。被消灭的人在图解中被删掉。

找出胜者需要三步：

步骤1 消灭4人: 2, 4, 6, 8.
步骤2 消灭2人: 3, 7.
步骤3 消灭1人: 5.

剩下1号胜出。

每一步被消灭人的编号（等价的，留下的人）遵从相同的模式，参赛人数为2的幂的单淘汰赛。

分析

不理会参赛人数n，1号在第一轮中幸存。因为n是偶数，如同每一个2的正幂，1号在第二轮中幸存。在第一轮，流程像是：1号跳过，2号消灭，3号跳过，4号消灭，...，n-1号跳过，n号消灭。第二轮始于跳过1号。

只要参赛人数是偶数，它将起始于2的幂，将遵从下面的模式：1号每次都会跳过。因此，任何2的幂，1号永远会胜出。

归纳法证明

你可以用归纳法证明1号是胜出者（详见Miguel Lerma’s proof of the Josephus problem). 相较上面的观点，归纳法作用于相反的方向；它从简单问题建立了一个复杂问题。

当有 n = 2¹ = 2 参赛者，显然，1会是胜出者。根据归纳法的假设，若1号是当 n = 2^m 是的胜者。则1号是2^m+1的胜者。

当 n = 2^m+1, 2^m 个人 — 都是偶数号 — 在第一轮被消灭, 留下 2^m 个人 — 都是奇数号 — 留下了。根据归纳假设，1号是剩下 n = 2^m 人里的胜出者，同样也是全部 n = 2^m+1 人中的胜出者。因此，任何2的幂，1号都是胜者。

参数人数不是2的幂

当参数人数不是2的幂，我们知道：1号不会是胜出者。这是因为至少有一轮下来剩下的参赛者是奇数。只要首次奇数轮结束，下一轮中1号将被第一个消灭。

那么有没有简便办法判断谁是胜出者？我们回过头来仔细再看13人的例子：

隔位消灭（13人）

4步才可知道胜者是谁：

步骤1 消灭6人: 2, 4, 6, 8, 10, 12.
步骤2 消灭4人: 1, 5, 9, 13.
步骤3 消灭1人: 7.
步骤4 消灭1人: 3.

剩下11号为胜出者。

分析

2的幂在这里同样起作用，只是你需要变换你的视角。它们不再发生在起始边界处-而是跨过。在有些点，跨越1号，剩下的参赛者为2的幂。在本例中，这发生在13人中的5人被消灭时，剩下8人： 11, 12, 13, 1, 3, 5, 7, 9. 这意味着11号，会在新的2的幂的圈中，胜出。

下面仍是13人的例子，和2的幂8人圈的详细图解：

8-Person Power of 2 Subset of 13-Person Problem

13人的8人子集图解

(这让我想起隔位消灭的过程就是检查一个数是否2的正幂的间接方式。一个数是2的正幂当且仅当，不停减半，最终得1）

方程

我们可以解决两种情况-或者说，对任意数量参数者-使用一点数学。

将n写作 n = 2^m + k, 2^m 是小于等于n的最大2的幂。需要消灭k个人来让问题变成2的幂，意味着要经过2k个人。圈中下一个人，2k+1号，将是胜出者。换句话说，胜出者w是 w = 2k + 1.

举几个方程的应用实例：

n = 8: 方程仍有效，尽管没必要用方程：n = 8 + 0, 所以 k = 0 得 w = 0 + 1 = 1.
n = 13: n = 8 + 5, 所以 k = 5 得 w = 2*5 + 1 = 11.
n = 1000: 这是纽约时代上的例子： n = 1000 = 512 + 488, 所以 k = 488 得 w = 2*488 + 1 = 977.

公式

我们可以合并公式 n = 2^m + k 和 w = 2k + 1 得到一个关于w的单独公式：

重整 n = 2^m + k 得: k = n – 2^m.
将上式代入w = 2k + 1:
w = 2(n – 2^m) + 1

公式作为单参数函数

公式是有两个参数的函数，n和m。这没问题，但是最好是只有一个参数-n。这意味着我们必须去掉m，或更准确，让m本身是n的函数。

我们把2^m 宽松地描述为 “小于等于n的最大的2的幂,” 但这是算法描述。数学描述是， m是以2为底的对数n的整数部分；为，m = floor(log₂(n)), or $\mbox{\footnotesize{\displaystyle{\lfloor log_2(n) \rfloor}}}$ .