機(jī)靈的小白鼠

與約瑟夫斯問題

大花貓Tom是捕鼠能手，每天要抓到不少老鼠。但它在吃老鼠以前，先要把老鼠排成一條直線，列隊(duì)報(bào)數(shù)。從1號(hào)開始，吃一個(gè)隔一個(gè)，從排頭吃到排尾，即第一批吃掉報(bào)單數(shù)的；剩下的老鼠從排頭開始重新報(bào)數(shù)。第二批，仍吃掉報(bào)單數(shù)的；第三批也是如此……最后剩下的一只老鼠可以被保留，與第二天抓來的老鼠一起重新排隊(duì)報(bào)數(shù)。1、Tom和Jerry的故事

大花貓Tom發(fā)現(xiàn)，一連好幾天，最后被留下的總是一只機(jī)靈的小白鼠。這是一件極其有趣的事情。大花貓就問小白鼠：“你叫什么?想了什么辦法，能每天都留下呢？”小白鼠說：“尊敬的大花貓先生，我叫Jerry,每天排隊(duì)前我都先數(shù)一數(shù)你抓到了多少只老鼠，然后，我站在一個(gè)相應(yīng)的位置，就可以留下來了。大花貓Tom聽了小老鼠Jerry的詳細(xì)回答，很感嘆地說：“沒想到，害人的老鼠里居然也有你這樣聰明的小家伙呀！”一條直線

小老鼠Jerry行了一個(gè)禮，恭敬地說：“尊敬的大花貓先生，不瞞您說，我并不是害人的老鼠，我是從科學(xué)家的實(shí)驗(yàn)室里溜出來玩的，您放我回去，好嗎？”大花貓高興地放它回去，臨別的時(shí)候，大花貓還感謝Jerry給它上了一節(jié)生動(dòng)的數(shù)學(xué)課呢！你知道嗎，小老鼠Jerry每天應(yīng)站在什么位置才能不被花貓吃掉。一條直線為了方便，我們假設(shè)第一天共有二十只老鼠排隊(duì)，第二天是四十只，你來試著排排吧。100只呢?【分析】大花貓第一批吃掉序數(shù)是單數(shù)的老鼠，留下序數(shù)是雙數(shù)，也就是序數(shù)能被2整除的老鼠（如2、4,6,8、…,14,…等）。第一批吃完后，2、4、6、8、10……這些序數(shù)需要重新編號(hào)，把它們?nèi)坑?去除，得到1，2，3，……這是第二輪編的號(hào)碼。第二批要被吃掉的老鼠是重新編號(hào)的奇數(shù)號(hào)碼。剩下4、8、12……。所以，如果序數(shù)中有盡可能多的因數(shù)2，老鼠就安全了。聰明的小老鼠就專揀這樣的位置站。

比如20只老鼠排隊(duì)，站第16個(gè)（2×2×2×2=2^4）40只老鼠排隊(duì)，站第32個(gè)（2×2×2×2×2=2^5）100只老鼠排隊(duì)，站第64個(gè)（2^6）

一天大花貓Tom又抓了100只老鼠，很不幸這次小老鼠Jerry又被抓住了，這次Tom決定將老鼠排成一排，從1號(hào)開始，吃兩個(gè)隔一個(gè)，這樣吃下去，直到剩下的老鼠不足3個(gè)，那么這次小老鼠Jerry該站在哪里呢？拓展一下提示：3^k一個(gè)圓圈

又有一天，Tom又抓了64只老鼠，很不幸，Jerry又被抓住了。這一次，Tom決定把老鼠排成一個(gè)圓圈，從1到64號(hào)編了號(hào)，從1號(hào)開始吃，吃一個(gè)隔一個(gè)，一圈一圈的吃下去，直到只剩下最后一個(gè)的時(shí)候就放掉。那么這一次，Jerry該站到哪個(gè)位置，才能保證不被Tom吃掉呢？

如果有65只老鼠，大花貓還是按上述的方法吃，最后還會(huì)剩下Tom嗎？66只呢？

分析：若64只老鼠，每次吃掉一半，剩下的始終是偶數(shù)，所以和排成一條直線是一樣的，最后剩下的必然是64號(hào)。有65只老鼠時(shí)，因?yàn)榈谝粋€(gè)被吃后，也就是1號(hào)被吃后，第二個(gè)被吃的是必然3號(hào)。如果把1號(hào)排除在外，那么還剩下的仍是64只，新1號(hào)就是3號(hào)。這樣原來的2號(hào)就變成了新的64號(hào)，所以剩下的是2號(hào)（即最后剩下的一個(gè)由原先的位置沿圓圈向前移動(dòng)2個(gè)位置）。有66只老鼠時(shí)，因?yàn)榈?、3號(hào)被吃后，剩下的仍是64只，新1號(hào)就是5號(hào)。這樣原來的4號(hào)就變成了新的64號(hào)，所以剩下的是4號(hào)。（即最后剩下的一個(gè)由原先的位置沿圓圈向前移動(dòng)4個(gè)位置）※進(jìn)一步的分析

一般地，如果原來有2^k個(gè)，最后剩下的必然2^k號(hào)。設(shè)總數(shù)n滿足2^k＜n≤2^(k+1).考慮最簡單的情況n＝2^k+1，在1號(hào)被殺死后，總數(shù)就變成2^k了。接下來第一個(gè)被殺的當(dāng)然是3號(hào)，將3號(hào)看成新1號(hào)，（最后一個(gè)2^k+1號(hào)就是新2^k-1），2號(hào)就是第2^k個(gè)，故最后留下的應(yīng)當(dāng)是2號(hào)。設(shè)總數(shù)是n-1時(shí)，最后留下的是X號(hào)，那總數(shù)是n時(shí)，最后留下的是x＋2號(hào)。每增加一個(gè)老鼠（或人），最后留下的老鼠（或人）的號(hào)數(shù)就增加2，2^k+1個(gè)人，最后留下2號(hào)；2^k+2個(gè)人，最后留下4號(hào)，依此類推，2^k＋m個(gè)人，最后留下的是2m號(hào)。※練習(xí)（1）把1～999這999個(gè)自然數(shù)按順時(shí)針的方向依次排列在一個(gè)圓圈上（如圖）．從1開始按順時(shí)針的方向，保留1，擦去2；保留3，擦去4…這樣每隔一個(gè)數(shù)擦去一個(gè)數(shù)，轉(zhuǎn)圈擦下去．問：最后剩下一個(gè)數(shù)時(shí)，剩下的是哪個(gè)數(shù)？分析與解:

如果有2^n個(gè)數(shù),那么每轉(zhuǎn)一圈擦去一半,剩下的數(shù)始終是偶數(shù)個(gè),起始數(shù)始終是1。轉(zhuǎn)了n圈后,就剩下一個(gè)數(shù)是1.由于2^9=512，2^10=1024，2^9＜999＜2^10，999-512=487．即999=2^9+487這就是說，要剩2^9個(gè)數(shù)，需要先擦去487個(gè)數(shù)．按題意，每兩個(gè)數(shù)擦去一個(gè)數(shù)，當(dāng)擦第487個(gè)數(shù)時(shí)，最后擦去的數(shù)是：487×2=974．下一個(gè)起始數(shù)是975，即最后剩下的數(shù)應(yīng)是975．（2）Tom抓了81只老鼠，這一次，Tom決定把老鼠排成一個(gè)圓，從1到81號(hào)編了號(hào)，從1號(hào)開始，隔一個(gè)吃兩個(gè)，一圈一圈的吃下去，直到只剩下最后一個(gè)的時(shí)候就放掉。那么這一次，最后哪只老鼠是幸運(yùn)兒呢？若是99只老鼠呢？分析：如果有3^n個(gè)數(shù),那么轉(zhuǎn)一圈去掉2/3，剩下1/3個(gè)數(shù),起始數(shù)還是1；再轉(zhuǎn)一圈去掉剩下的2/3,又剩下前面的1/3個(gè)數(shù),起始數(shù)還是1……轉(zhuǎn)了n圈后,就剩下一個(gè)數(shù)1.因?yàn)?1=3^4,因此剩下1號(hào)。99=81+18,，要剩81個(gè)，必須吃掉18只時(shí)，（若一組3個(gè)數(shù)，一組吃2個(gè)，吃掉第18只時(shí)，越過9組），最后吃掉的是9×3=27號(hào)，下一個(gè)起始數(shù)為28，即最后剩下的應(yīng)是28號(hào)?！卣咕毩?xí)2、約瑟夫斯問題介紹

如前面我們研究的，對(duì)一個(gè)問題周期性計(jì)數(shù)的問題稱為約瑟夫斯問題。2.1約瑟夫斯問題的起源約瑟夫斯是公元1世紀(jì)的猶太歷史學(xué)家，他領(lǐng)導(dǎo)了反抗羅馬人的武裝起義，但是失敗了。他和四十名猶太士兵被羅馬人圍困在一個(gè)山洞中。這四十個(gè)士兵寧死不屈，決定殺身成仁。但約瑟夫斯不是這樣想，但又不便公開反對(duì)，于是提出一個(gè)方法，就是四十一個(gè)人站成一個(gè)圈，從某人開始數(shù)起，凡數(shù)到三的人就讓大家成全他升天，這樣下去直到剩下最后一個(gè)人，這個(gè)人就自殺。大家都沒有意見，于是約瑟夫斯就挑選了第31號(hào)的位置。結(jié)果所有人都死了，剩下他一個(gè)活下來投降了羅馬人。這也是約瑟夫斯問題的最初來源。2.2約瑟夫斯問題解決

約瑟夫問題比前面復(fù)雜的多，但并不太難，求解的方法很多;題目的變化形式也很多。一般都是利用計(jì)算機(jī)編程來做。約瑟夫問題對(duì)于n小的情況，只要畫兩個(gè)圓圈就可以解決，這兩個(gè)圓內(nèi)圈是排列順序，而外圈是淘汰順序。下面的定理給出了一個(gè)解決約瑟夫問題的遞推公式。定理n個(gè)人排成一個(gè)封閉的圓圈,從中一個(gè)一個(gè)地往外剔.從任意哪個(gè)人開始繞著圓圈不斷地往下數(shù),每數(shù)到第m個(gè)人就把他剔出去,直到剩下最后1個(gè)人為止.假定這些人中最后剩下的那個(gè)人開始占著第個(gè)位置,如果增添一個(gè)人,即開始有n+1個(gè)人,那么,他開始應(yīng)該占據(jù)第個(gè)位置,則.

證明:用數(shù)學(xué)歸納法當(dāng)n=1,即具有一個(gè)人時(shí)，當(dāng)有兩個(gè)人時(shí).若m為奇數(shù),最后剩下的人是2號(hào);若m為偶數(shù),最后剩下的人是1號(hào),即設(shè)當(dāng)有n(n≥2)個(gè)人時(shí),成立,則當(dāng)增加到n+1個(gè)人時(shí),最后剩下的人須由原先的位置沿圓圈向前移動(dòng)m個(gè)位置，即:，但這時(shí)總共有n+1個(gè)位置，所以當(dāng)時(shí),這個(gè)人應(yīng)該改占第個(gè)位置,用公式表示:約瑟夫斯問題解決

約瑟夫斯問題：

約瑟夫斯和四十名猶太士兵被羅馬人圍困在一個(gè)山洞中。這四十個(gè)士兵寧死不屈，決定殺身成仁。但約瑟夫斯不是這樣想，但又不便公開反對(duì)，于是提出一個(gè)方法，就是四十一個(gè)人站成一個(gè)圈，從某人開始數(shù)起，凡數(shù)到三的人就讓大家成全他升天，這樣下去直到剩下最后一個(gè)人，這個(gè)人就自殺。大家都沒有意見，于是約瑟夫斯就挑選了第31號(hào)的位置。結(jié)果所有人都死了，剩下他一個(gè)活下來。解：根據(jù)定理,m=3,最后剩下的人可作如下推理：......,即最后剩下的人開始應(yīng)在第31號(hào)位置上。3、涉及到約瑟夫問題的趣題遇險(xiǎn)的游客同乘一條船的30名游客在深海上遇險(xiǎn)，風(fēng)大浪高，此時(shí)必須將一半的人投入海中，其余的人才能幸免于難．大家經(jīng)過共同商議，最后決定：30個(gè)人圍成一圓圈，從某個(gè)人開始從1往下依次點(diǎn)數(shù)，每數(shù)到9就把那個(gè)人扔入大海，如此循環(huán)進(jìn)行，直到僅余15個(gè)人為止．問：哪些位置的人是能留下來的幸運(yùn)兒呢？解：最后剩下的人在第21位.設(shè)A代表留下來的游客，B代表被扔下船的游客，留下來的15人占據(jù)的位置是AAAABBBBBAABAAABABBAABBBABBAAB

請(qǐng)你用畫圈的辦法試試看，結(jié)果一樣嗎？

從前有一位富商,他有30個(gè)孩子,其中15個(gè)是已故的前妻所生,其余15個(gè)是現(xiàn)在妻子所生,妻子很想讓她自己所生的最年長的兒子繼承財(cái)產(chǎn),于是有一天對(duì)這位富商說:“親愛的,你就要老了,我們應(yīng)當(dāng)定下來誰將是你的繼承人.現(xiàn)在讓我們把我們的30個(gè)孩了排成一個(gè)圓圈,從他們中的一個(gè)數(shù)起,每逢10就讓那個(gè)孩子站出去,直到最后剩下的那個(gè)孩子,他就作為你的財(cái)產(chǎn)繼承人吧！”富商與妻子

這個(gè)建議似乎沒有什么不公之處,然而當(dāng)剔選過程不斷進(jìn)行下去的時(shí)候,這個(gè)富商愈來愈感到驚詫,因?yàn)樗⒁獾角?4個(gè)被剔出去的孩子都是前妻所生,而下一個(gè)將要站出去的仍是前妻所生的孩子。所以他馬上叫停，提出從這個(gè)孩子（最后一個(gè)前妻的孩子）開始倒回去數(shù)看看情況如何.迫于馬上要作出決定,并且想到她的孩子們有15比1的有利機(jī)會(huì),他的妻子立即同意了丈夫的動(dòng)議,到底誰做了繼承人呢?你來算算看！最后剩下的人在第1位國王與公主

一位富有的國王有一位漂亮的公主,她的名字叫約瑟芬,向約瑟芬求婚的小伙子成百上千,最后,除了她選中的10個(gè)她最喜歡的人之外,其他人都被排除了。幾個(gè)月過去了,約瑟芬還沒有拿定主意.國王生氣了,他說:寶貝,下個(gè)月你就17歲了,所有公主都要在這個(gè)年齡前結(jié)婚,這是我們的傳統(tǒng)?！彼鸬?“爸爸,可我還沒最后決定我是否最喜歡喬治.”

國王說:“既然如此,今天我們只好通過慣例來解決這個(gè)問題。接著,國王解釋了這個(gè)古老儀式的進(jìn)行方式,他說:“10個(gè)人圍成一個(gè)圓圈,你可以根據(jù)你的意愿挑選任何一個(gè)人作為1,然后開始沿著圓周按順時(shí)針方向數(shù)數(shù),數(shù)到你的年齡--17為止,第17個(gè)人必須退出這個(gè)圈.我們給他100金幣作為補(bǔ)償,送他回家。”“他走后,你再從已退出那人的下一位數(shù)起,再從1數(shù)到17，數(shù)到17的那個(gè)人像前面一樣被排除掉.依此繼續(xù)做下去,每次都是對(duì)剩下的人,周而復(fù)始地從1數(shù)到17,直到剩下最后一個(gè)，他就是要和你結(jié)婚的那個(gè)人。”

約瑟芬皺著眉說:“爸爸,我還沒搞清楚,我用10個(gè)金幣做一下演習(xí)好嗎?”國王同意了.約瑟芬把10枚金幣擺成一個(gè)圓圈,開