什么是约瑟夫斯问题？

什么是约瑟夫斯问题？

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

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

由于第一圈剩下的全部是偶数号２，４，６，８，…，６４。把它们全部用２除，得１，２，３，４，…，３２，这是第二圈重新编的号码，第二圈杀过之后，又把奇数号码都杀掉了，还剩下１６个人，如此下去，可以想到最后剩下的必然是６４号。

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

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

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

对于一般情况来说，如果原来有２ｋ个人，最后剩下的必然是２ｋ号；如果原来有２ｋ＋１个人，最后剩下的是２号；如果原来有２ｋ＋２个人，最后剩下的是４号……如果原来有２ｋ＋ｍ个人，最后剩下的是２ｍ号。

比如，原来有１００人，由于１００＝６４＋３６＝２６＋３６，所以最后剩下的是２×３６＝７２号；又比如，原来有１１１人，由于１１１＝６４＋４７＝２６＋４７，所以最后剩下的是２×４７＝９４号。

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

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

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