kok电子竞技

机灵的小白鼠

与约瑟夫斯问题

大花猫Tom是捕鼠能手，每天要抓到不少老鼠。但它在吃老鼠以前，先要把老鼠排成一条直线，列队报数。从1号开始，吃一个隔一个，从排头吃到排尾，即第一批吃掉报单数的；剩下的老鼠从排头开始重新报数。第二批，仍吃掉报单数的；第三批也是如此……最后剩下的一只老鼠可以被保留，与第二天抓来的老鼠一起重新排队报数。1、Tom和Jerry的故事

大花猫Tom发现，一连好几天，最后被留下的总是一只机灵的小白鼠。这是一件极其有趣的事情。大花猫就问小白鼠：“你叫什么?想了什么办法，能每天都留下呢？”小白鼠说：“尊敬的大花猫先生，我叫Jerry,每天排队前我都先数一数你抓到了多少只老鼠，然后，我站在一个相应的位置，就可以留下来了。大花猫Tom听了小老鼠Jerry的详细回答，很感叹地说：“没想到，害人的老鼠里居然也有你这样聪明的小家伙呀！”一条直线

小老鼠Jerry行了一个礼，恭敬地说：“尊敬的大花猫先生，不瞒您说，我并不是害人的老鼠，我是从科学家的实验室里溜出来玩的，您放我回去，好吗？”大花猫高兴地放它回去，临别的时候，大花猫还感谢Jerry给它上了一节生动的数学课呢！你知道吗，小老鼠Jerry每天应站在什么位置才能不被花猫吃掉。一条直线为了方便，我们假设第一天共有二十只老鼠排队，第二天是四十只，你来试着排排吧。100只呢?【分析】大花猫第一批吃掉序数是单数的老鼠，留下序数是双数，也就是序数能被2整除的老鼠（如2、4,6,8、…,14,…等）。第一批吃完后，2、4、6、8、10……这些序数需要重新编号，把它们全部用2去除，得到1，2，3，……这是第二轮编的号码。第二批要被吃掉的老鼠是重新编号的奇数号码。剩下4、8、12……。所以，如果序数中有尽可能多的因数2，老鼠就安全了。聪明的小老鼠就专拣这样的位置站。

比如20只老鼠排队，站第16个（2×2×2×2=2^4）40只老鼠排队，站第32个（2×2×2×2×2=2^5）100只老鼠排队，站第64个（2^6）

一天大花猫Tom又抓了100只老鼠，很不幸这次小老鼠Jerry又被抓住了，这次Tom决定将老鼠排成一排，从1号开始，吃两个隔一个，这样吃下去，直到剩下的老鼠不足3个，那么这次小老鼠Jerry该站在哪里呢？拓展一下提示：3^k一个圆圈

又有一天，Tom又抓了64只老鼠，很不幸，Jerry又被抓住了。这一次，Tom决定把老鼠排成一个圆圈，从1到64号编了号，从1号开始吃，吃一个隔一个，一圈一圈的吃下去，直到只剩下最后一个的时候就放掉。那么这一次，Jerry该站到哪个位置，才能保证不被Tom吃掉呢？

如果有65只老鼠，大花猫还是按上述的方法吃，最后还会剩下Tom吗？66只呢？

分析：若64只老鼠，每次吃掉一半，剩下的始终是偶数，所以和排成一条直线是一样的，最后剩下的必然是64号。有65只老鼠时，因为第一个被吃后，也就是1号被吃后，第二个被吃的是必然3号。如果把1号排除在外，那么还剩下的仍是64只，新1号就是3号。这样原来的2号就变成了新的64号，所以剩下的是2号（即最后剩下的一个由原先的位置沿圆圈向前移动2个位置）。有66只老鼠时，因为第1、3号被吃后，剩下的仍是64只，新1号就是5号。这样原来的4号就变成了新的64号，所以剩下的是4号。（即最后剩下的一个由原先的位置沿圆圈向前移动4个位置）※进一步的分析

一般地，如果原来有2^k个，最后剩下的必然2^k号。设总数n满足2^k＜n≤2^(k+1).考虑最简单的情况n＝2^k+1，在1号被杀死后，总数就变成2^k了。接下来第一个被杀的当然是3号，将3号看成新1号，（最后一个2^k+1号就是新2^k-1），2号就是第2^k个，故最后留下的应当是2号。设总数是n-1时，最后留下的是X号，那总数是n时，最后留下的是x＋2号。每增加一个老鼠（或人），最后留下的老鼠（或人）的号数就增加2，2^k+1个人，最后留下2号；2^k+2个人，最后留下4号，依此类推，2^k＋m个人，最后留下的是2m号。※练习（1）把1～999这999个自然数按顺时针的方向依次排列在一个圆圈上（如图）．从1开始按顺时针的方向，保留1，擦去2；保留3，擦去4…这样每隔一个数擦去一个数，转圈擦下去．问：最后剩下一个数时，剩下的是哪个数？分析与解:

如果有2^n个数,那么每转一圈擦去一半,剩下的数始终是偶数个,起始数始终是1。转了n圈后,就剩下一个数是1.由于2^9=512，2^10=1024，2^9＜999＜2^10，999-512=487．即999=2^9+487这就是说，要剩2^9个数，需要先擦去487个数．按题意，每两个数擦去一个数，当擦第487个数时，最后擦去的数是：487×2=974．下一个起始数是975，即最后剩下的数应是975．（2）Tom抓了81只老鼠，这一次，Tom决定把老鼠排成一个圆，从1到81号编了号，从1号开始，隔一个吃两个，一圈一圈的吃下去，直到只剩下最后一个的时候就放掉。那么这一次，最后哪只老鼠是幸运儿呢？若是99只老鼠呢？分析：如果有3^n个数,那么转一圈去掉2/3，剩下1/3个数,起始数还是1；再转一圈去掉剩下的2/3,又剩下前面的1/3个数,起始数还是1……转了n圈后,就剩下一个数1.因为81=3^4,因此剩下1号。99=81+18,，要剩81个，必须吃掉18只时，（若一组3个数，一组吃2个，吃掉第18只时，越过9组），最后吃掉的是9×3=27号，下一个起始数为28，即最后剩下的应是28号。※拓展练习2、约瑟夫斯问题介绍

如前面我们研究的，对一个问题周期性计数的问题称为约瑟夫斯问题。2.1约瑟夫斯问题的起源约瑟夫斯是公元1世纪的犹太历史学家，他领导了反抗罗马人的武装起义，但是失败了。他和四十名犹太士兵被罗马人围困在一个山洞中。这四十个士兵宁死不屈，决定杀身成仁。但约瑟夫斯不是这样想，但又不便公开反对，于是提出一个方法，就是四十一个人站成一个圈，从某人开始数起，凡数到三的人就让大家成全他升天，这样下去直到剩下最后一个人，这个人就自杀。大家都没有意见，于是约瑟夫斯就挑选了第31号的位置。结果所有人都死了，剩下他一个活下来投降了罗马人。这也是约瑟夫斯问题的最初来源。2.2约瑟夫斯问题解决

约瑟夫问题比前面复杂的多，但并不太难，求解的方法很多;题目的变化形式也很多。一般都是利用计算机编程来做。约瑟夫问题对于n小的情况，只要画两个圆圈就可以解决，这两个圆内圈是排列顺序，而外圈是淘汰顺序。下面的定理给出了一个解决约瑟夫问题的递推公式。定理n个人排成一个封闭的圆圈,从中一个一个地往外剔.从任意哪个人开始绕着圆圈不断地往下数,每数到第m个人就把他剔出去,直到剩下最后1个人为止.假定这些人中最后剩下的那个人开始占着第个位置,如果增添一个人,即开始有n+1个人,那么,他开始应该占据第个位置,则.

证明:用数学归纳法当n=1,即具有一个人时，当有两个人时.若m为奇数,最后剩下的人是2号;若m为偶数,最后剩下的人是1号,即设当有n(n≥2)个人时,成立,则当增加到n+1个人时,最后剩下的人须由原先的位置沿圆圈向前移动m个位置，即:，但这时总共有n+1个位置，所以当时,这个人应该改占第个位置,用公式表示:约瑟夫斯问题解决

约瑟夫斯问题：

约瑟夫斯和四十名犹太士兵被罗马人围困在一个山洞中。这四十个士兵宁死不屈，决定杀身成仁。但约瑟夫斯不是这样想，但又不便公开反对，于是提出一个方法，就是四十一个人站成一个圈，从某人开始数起，凡数到三的人就让大家成全他升天，这样下去直到剩下最后一个人，这个人就自杀。大家都没有意见，于是约瑟夫斯就挑选了第31号的位置。结果所有人都死了，剩下他一个活下来。解：根据定理,m=3,最后剩下的人可作如下推理：......,即最后剩下的人开始应在第31号位置上。3、涉及到约瑟夫问题的趣题遇险的游客同乘一条船的30名游客在深海上遇险，风大浪高，此时必须将一半的人投入海中，其余的人才能幸免于难．大家经过共同商议，最后决定：30个人围成一圆圈，从某个人开始从1往下依次点数，每数到9就把那个人扔入大海，如此循环进行，直到仅余15个人为止．问：哪些位置的人是能留下来的幸运儿呢？解：最后剩下的人在第21位.设A代表留下来的游客，B代表被扔下船的游客，留下来的15人占据的位置是AAAABBBBBAABAAABABBAABBBABBAAB

请你用画圈的办法试试看，结果一样吗？

从前有一位富商,他有30个孩子,其中15个是已故的前妻所生,其余15个是现在妻子所生,妻子很想让她自己所生的最年长的儿子继承财产,于是有一天对这位富商说:“亲爱的,你就要老了,我们应当定下来谁将是你的继承人.现在让我们把我们的30个孩了排成一个圆圈,从他们中的一个数起,每逢10就让那个孩子站出去,直到最后剩下的那个孩子,他就作为你的财产继承人吧！”富商与妻子

这个建议似乎没有什么不公之处,然而当剔选过程不断进行下去的时候,这个富商愈来愈感到惊诧,因为他注意到前14个被剔出去的孩子都是前妻所生,而下一个将要站出去的仍是前妻所生的孩子。所以他马上叫停，提出从这个孩子（最后一个前妻的孩子）开始倒回去数看看情况如何.迫于马上要作出决定,并且想到她的孩子们有15比1的有利机会,他的妻子立即同意了丈夫的动议,到底谁做了继承人呢?你来算算看！最后剩下的人在第1位国王与公主

一位富有的国王有一位漂亮的公主,她的名字叫约瑟芬,向约瑟芬求婚的小伙子成百上千,最后,除了她选中的10个她最喜欢的人之外,其他人都被排除了。几个月过去了,约瑟芬还没有拿定主意.国王生气了,他说:宝贝,下个月你就17岁了,所有公主都要在这个年龄前结婚,这是我们的传统。”她答道:“爸爸,可我还没最后决定我是否最喜欢乔治.”

国王说:“既然如此,今天我们只好通过惯例来解决这个问题。接着,国王解释了这个古老仪式的进行方式,他说:“10个人围成一个圆圈,你可以根据你的意愿挑选任何一个人作为1,然后开始沿着圆周按顺时针方向数数,数到你的年龄--17为止,第17个人必须退出这个圈.我们给他100金币作为补偿,送他回家。”“他走后,你再从已退出那人的下一位数起,再从1数到17，数到17的那个人像前面一样被排除掉.依此继续做下去,每次都是对剩下的人,周而复始地从1数到17,直到剩下最后一个，他就是要和你结婚的那个人。”

约瑟芬皱着眉说:“爸爸,我还没搞清楚,我用10个金币做一下演习好吗?”国王同意了.约瑟芬把10枚金币摆成一个圆圈,开始转圈数数，拿掉每一个第17枚,直到剩下最后一个,国王一直守候着，直到他女儿完全看清了其中的奥妙为止。10名求婚者被带到王宫,他们围着约瑟芬站成了一个圆圈.约瑟芬一点也不含糊地从帕西瓦开始数了起来.很快地，除了她芳心暗许的乔治外,其余的人都被排除了.那么约瑟芬有什么诀窍使她能找到开始数的第一个人,且使得数到最后一定剩下乔治呢?

请你用画圈的办法试试看，再试着学用定理递推一下，结果一样吗？约瑟芬应将她喜欢的乔治排在第几位？

约瑟芬将她喜欢的乔治排在第3位。你算对了吗？