约瑟夫斯问题

这是一个古老的传说：有64名战士被敌人俘虏了，敌人命令他们排成一个圆圈，编上号码1，2，3，…，64，敌人把1号杀了，又把3号杀了，他们是隔一个杀一个这样转着圈杀，最后剩下一个人，这个人就是约瑟夫斯，请问约瑟夫斯是多少号？这就是“约瑟夫斯问题”。

这个问题是比较容易解答的：敌人从1号开始，隔一个杀一个，第一圈把奇数号码的战士全杀死了。剩下的32名战士需要重新编号，而敌人在第二圈杀死的是重新编排的奇数号码。

由于第一圈剩下的全部是偶数号2，4，6，8，…，64。把它们全部用2除，得1，2，3，4，…，32，这是第二圈重新编的号码，第二圈杀过之后，又把奇数号码都杀掉了，还剩下16个人，如此下去，可以想到最后剩下的必然是64号。

64＝2 ⁶ ，它可以连续被2整除6次，是从1到64中能被2整除次数最多的数，因此，最后必然把64号剩下，从64＝2 ⁶ 还可以看到，是转这6圈之后，把约瑟夫斯剩下来的。

如果有65名战士被俘，敌人还是按上述方法残杀战士，最后剩下的还是64号约瑟夫斯吗？

不是了，因为第一个人被杀后，也就是1号被杀后，第二个被杀的必然是3号，如果把1号排除在外，那么剩下的仍是64个人，对于剩下这64个人，新1号就应该是原来的3号，这样原来的2号就变成新的64号了，所以剩下的必然是原来的2号。

对于一般情况来说，如果原来有2 ^k 个人，最后剩下的必然是2 ^k 号；如果原来有2 ^k ＋1个人，最后剩下的是2号；如果原来有2 ^k ＋2个人，最后剩下的是4号……如果原来有2 ^k ＋m个人，最后剩下的是2m号。

比如，原来有100人，由于100＝64＋36＝2 ⁶ ＋36，所以最后剩下的是2×36＝72号；又比如，原来有111人，由于111＝64＋47＝2 ⁶ ＋47，所以最后剩下的是2×47＝94号。

下面把问题改一下：不让被俘的战士站成圆圈，而排成一条直线，然后编上号码，从1号开始，隔一个杀一个，杀过一遍之后，然后再重新编号，从新1号开始，再隔一个杀一个，问最后还是约瑟夫斯吗！

答案是肯定的，最后剩下的仍然是约瑟夫斯。

如果战俘人数是65人呢？剩下的还是约瑟夫斯，只要人数不超过128人，也就是人数小于2 ⁷ ，那么最后剩下的总是约瑟夫斯，因为从1到128中间，能被2整除次数最多的就是64，而敌人每次都是杀奇数号留偶数号，所以64号总是最后被留下的人。