本题灵感来源于Numberphile。

公元67年，在第一次犹太罗马战役中，罗马军队包围了犹太人的一个小镇Yodfat。当时在镇上的历史学家Flavius Josephus，和在他身边的40名战士，陷入了罗马军队的包围圈，眼看就要被全部俘虏，他们决定在这之前自杀。他们约定了一个特别的自杀方式，41个人围成一个圈，随机选择一个人标记为1号，并按顺时针或者逆时针的方式依次给所有人标号，然后自杀：第1个人杀死第2个人，第3个人杀死第4个人，第5个人杀死第6个人，依次类推。最后，不知道是不是上帝的旨意，Josephus和另外一个士兵成为了最后活下来的两个人，他们最后也没有自杀，而是被俘虏了。

且不论Josephus和另一个士兵最后没有自杀的行为是否亵渎了和其他人的约定，假设你就是Josephus，而且你不想自杀，你是否能够算出“站在哪个位置，才能活到最后”？或者广义地说，给定一个人数为\(n\)的圈，求\(f(n)\)，使得站在位置\(f(n)\)的人是最后活下来的人。

当\(n=8\)的示意图，黄色代表当前杀手，红色代表活着，白色代表死亡：
Josephus Problem n=8

如果我们解出从1到8的 \(f(n)\)，我们可以发现一个明显的规律：

\(n\) \(f(n)\)
1 1
2 1
3 3
4 1
5 3
6 5
7 7
8 1

我们可以发现，第一，所有的\(f(n)\)都是奇数。第二，\(f(n)\)似乎在从1，3，5，7…这个序列里面重复。 最重要的观察应该是，当\(n=2^k\)，即n是2的k次方的时候，\(f(n)=1\)。这其实并非偶然。我们其实可以想象，当人数为n，且\(n=2^k\)时，每杀完整整一轮的时候，剩余人数就减半，于是下一轮的杀人过程和当人数为\(2^(k-1)\)的时候应该完全一样。以此类推，只要\(n=2^k\)，最后剩下的那个人应该和当n=2的时候剩下的那个人是同一个人。
当\(n=2\)时，谁会赢呢？第1个人杀死第2个人，是第1个人赢。

有了这个发现，剩下的情况就简单一些了。

剩下的情况就是当n不为2的次方数的时候，所以我们可以假设\(n=2^k+b\)，其中\(2^k< n\)且\(2^{(k+1)}>n\)，即k是以2为底，使得\(2^k\)不超过n的最大次数。或者可以写成\(k=\lfloor \log_2(n) \rfloor\)。这又导致另一个很重要的条件：\(b< n/2\)。所以接下来我们证明。如果\(b=n/2\),则\(n=2^k+n/2\),那么\(n/2=2^k, n=2^{(k+1)}\), 这与我们的假设矛盾。 如果\(b>n/2\),则\(2^k+n/2 < n\)，也就是\(2^k< n/2，2^{(k+1)}< n\)，因为我们假设了\(2^k\)是不超过n的最大的2的次方数，所以也矛盾。

有了这些条件，我们来观察会发生什么。

当b个人被杀的时候，因为\(b< n/2\)，所以一轮还没结束，圆圈中还剩下\(2^k\)个人，下一个杀人的人是第\(2b+1\)个人。于是乎，我们可以重新给大家编号，把第\(2b+1\)个人标为1号，第\(2b+2\)个人标为2号，等等。这下最终的赢家是谁？由于现在的情况和当n=2^k的情况一模一样，所以当然是那个重新被标注成第一号的人了。

于是乎我们得到答案，当\(n=2^k+b\)时，最终赢家是第\(2b+1\)个人。