书城科普读物数理化之谜
4412800000006

第6章 约瑟夫斯问题

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

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

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

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

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

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

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

比如,原来有100人,由于100=64+36=26+36,所以最后剩下的是2×36=72号;又比如,原来有111人,由于111=64+47=26+47,所以最后剩下的是2×47=94号。

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

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

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