登陆注册
2120600000006

第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号总是最后被留下的人。

同类推荐
  • 中华青少年成长必读集萃:一分钟推理

    中华青少年成长必读集萃:一分钟推理

    本书作者精心选编了内容跌宕起伏、扣人心弦的古今中外精彩的推理故事奉献给小读者。作者想让小读者在书中体会大侦探的感觉,希望他们认真揣摩悬念丛生的案情,查找狡猾嫌犯的蛛丝马迹,巧妙地揭开一个个错综复杂的案件真相,成为福尔摩斯式的“侦探高手”。
  • 神秘的生物(探索宇宙奥秘系列丛书)

    神秘的生物(探索宇宙奥秘系列丛书)

    宇宙,是这个世界上谜团最多的地方,也是最吸引孩子好奇心的地方。宇宙包含着最神秘的未知和疑问,人类正在以高超的科学手段和不懈的努力不断深入探索宇宙的深处,希望了解人类自身的过去与未来。而地球是我们人类赖以生存的家园。在漫长的岁月中,人类一直在这个星球上繁衍生息。虽然它只是太阳系中一颗普通的行星,但它在许多方面却又是独一无二的:它是太阳系中唯一一颗表面大部分被水覆盖的行星,也是目前所知唯一一颗有生命存在的星球……《探索宇宙奥秘系列丛书》向孩子们展示这个既熟悉又神奇的世界。
  • 宇宙大探秘

    宇宙大探秘

    夜晚,我们遥望闪闪的星空,会使我们翩翩遐想,似乎有数不尽的奥秘蕴藏在天空中……我们对宇宙探索的步伐一直没有停止,但是仍未揭开其冰山一角……
  • 透视地球

    透视地球

    主要从各个方面介绍地球的起源、运动、构造和特征,海陆变迁、构造运动、山川地貌等各类地质地理现象,人类对地球研究的认识方法、过程和成果。中外主要地质学派的代表人物及观点。《透视地球》语言通俗易懂,可以让读者对地球的各方面有一个全面的了解。
  • 生活知识百科(第三册)

    生活知识百科(第三册)

    进入新世纪以来,人们的生活发生了巨大的变化,科学知识比以往任何时期都显著地改变着人们的生活,影响着人们的生活,人们开始注重自己的生活质量,提高自己的生活水准。时代在发展,生活在进步,家庭生活知识需要不断更新,因为更完善、更及时地向人们介绍生活知识已经成为大众的普遍需要。本书针对家庭生活知识的方方面面进行了科学的指导,是专门介绍家庭生活知识的百科式的工具书。其对于指导人们的日常生活,帮助人们提高其生活质量,有着其他图书不可替代的重要作用。
热门推荐
  • 喊山(中篇小说)

    喊山(中篇小说)

    太行大峡谷走到这里开始瘦了,瘦得只剩下一道细细的梁,从远处望去赤条条的青石头儿悬壁上下,绕着几丝儿云,像一头抽干了力气的骡子,瘦得肋骨一条条挂出来,挂了几户人家。这梁上的几户人家,平常说话面对不上面要喊,喊比走要快。一个在对面喊,一个在这边答,隔着一条几十米直陡上下的深沟声音倒传得很远。
  • 深宫谍影

    深宫谍影

    明朝嘉靖年间,万花楼头牌名妓颜如玉裸死在房中,身旁的地上散落着几朵白色的木槿花。是情杀抑或仇杀?锦衣卫沈莫离查案,发现颜如玉之死,牵涉到一个神秘的组织白槿教,与后宫也有着千丝万缕的联系。自幼被送往武当拜师的善柔公主朱湄兰奉命回宫,与锦衣卫联手探案。从此险象环生、步步惊心。英雄美人,情根深种。预示着死亡的木槿花接连出现,背后的组织掀起腥风血雨。嫔妃争宠,宫女起义,命案频发,是谁的幕后黑手,在暗中操纵着这一切?宫里宫外“间谍”频现,红颜闹宫闱,龙颜一怒血成河。那些为爱痴狂的女子,血泪汇聚了一段香艳的秘史。千娇百媚的后宫红颜,究竟谁才是那个隐藏最深的“间谍?”案中有案,迷中藏迷,在扑朔迷离的探案过程中,大明公主和锦衣卫演绎了一段轰轰烈烈的家国大爱。
  • 傲世剑仙途

    傲世剑仙途

    一人之力,力压群雄:一把傲剑,助取天下。英雄道途,伴随悲哀:打造利剑,尽失心血。一人一剑之力,傲视天下群雄!
  • 余爱绕梁

    余爱绕梁

    比时光还要强大的,是命运;比记忆还要深刻的,是爱情。霍音第一眼见到梁淮则时,有种连自己都不明白的心动,仿佛他是她上辈子就爱过的人。他有不能忘却的亡妻,有患有自闭症的儿子,他对她的另眼相待,不过是为了让她填补梁慕尧缺失的母爱。然而因着一纸婚约,朝夕相处间,沦陷其中的,又何止她一个人?当她失去的记忆被重新找回,原来一切的巧合都不是偶然。往昔的甜蜜与欺骗,如今的深情与谎言,她该如何面对依旧深爱着的梁淮则?
  • 陪伴孩子成长的创造发现故事

    陪伴孩子成长的创造发现故事

    每当雨点从天而降,我们用什么来遮风避雨呢?首先大家想到的就是雨伞。可是,大家知道雨伞是怎样发明的吗?其实伞在中国有着悠久的历史……
  • 父亲的王国

    父亲的王国

    八月天,河南省作家协会会员。发表小说《遥远的麦子》《黑神的别样人生》《低腰裤》《父亲的王国》等。现任某报社记者。
  • 绘宗十二忌

    绘宗十二忌

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。汇聚授权电子版权。
  • 魔法跳跳舞

    魔法跳跳舞

    多玛前世并不信仰神,偏偏这世的她来到了一个需要信仰神灵才能得到力量的魔法世界,父亲的家族显赫但与她无关,因为她是一个情人的孩子,如果她想被家族承认,冠上家族荣耀的姓氏就必须优秀,原本以她混日子的快意性格是没打算去讨好家族的高层,但却因为来自地下世界的莫名追杀不得不努力的学习自保,做到优秀,她抽丝剥茧的摸索到了被追杀的根源,却因此牵引出更多关于她自己的谜团,谁,在操纵着她的人生?是人们信仰的神吗?一念天堂,一念地狱,魔法的世界,看她悠然起舞。荣耀有没有,实力说话,男人有没有,实力说话,一切靠自己快意人生!请携带放大镜寻找你喜欢的腹黑,美色和萌点。PS:有了一个书友QQ群,群号17402885,敲门砖是女主名字。推荐票每满1000加更,粉红票每满15加更。
  • 七星彩

    七星彩

    她是富商之女纪澄,原本性格纯真,因经历了祝吉军的威胁强娶,并害得二哥被打断腿的事后,下定决心要嫁入高门。借沈府老太太六十大寿之际,纪澄住进了姑母家中。从此以后,纪澄从曾经受人百般宠爱的千金小姐,变成寄居在别人屋檐下、不得不低头的不受宠姑娘。纪澄小心翼翼地与府中姐妹和王家、苏家姐妹相处,却遭到他人排挤、羡慕、嫉妒,甚至暗算,但她不动声色地发挥自己的聪明才智,一次次化险为夷。她的聪颖、美丽,终是招来了一朵朵桃花——沈家各位公子,但这些公子个个矜持,不表露心迹。这让宣节校尉何诚占了先机,与纪澄定下亲事。原本皆大欢喜的事,却被纨绔二公子沈彻搅了局,他到底怀着怎样的心思?纪澄能寻得一门好姻缘吗?
  • 战气封天

    战气封天

    来战!斩天地不仁。来战!覆日月乾坤。来战!造玄天星辰。来战!封阴阳道轮。若敢来,来之必战!若敢战,战之必胜!