機靈的小白鼠

與約瑟夫斯問題

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

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

小老鼠Jerry行了一個禮，恭敬地說：“尊敬的大花貓先生，不瞞您說，我并不是害人的老鼠，我是從科學(xué)家的實驗室里溜出來玩的，您放我回去，好嗎？”大花貓高興地放它回去，臨別的時候，大花貓還感謝Jerry給它上了一節(jié)生動的數(shù)學(xué)課呢！你知道嗎，小老鼠Jerry每天應(yīng)站在什么位置才能不被花貓吃掉。一條直線為了方便，我們假設(shè)第一天共有二十只老鼠排隊，第二天是四十只，你來試著排排吧。100只呢?【分析】大花貓第一批吃掉序數(shù)是單數(shù)的老鼠，留下序數(shù)是雙數(shù)，也就是序數(shù)能被2整除的老鼠（如2、4,6,8、…,14,…等）。第一批吃完后，2、4、6、8、10……這些序數(shù)需要重新編號，把它們?nèi)坑?去除，得到1，2，3，……這是第二輪編的號碼。第二批要被吃掉的老鼠是重新編號的奇數(shù)號碼。剩下4、8、12……。所以，如果序數(shù)中有盡可能多的因數(shù)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只老鼠，每次吃掉一半，剩下的始終是偶數(shù)，所以和排成一條直線是一樣的，最后剩下的必然是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號。設(shè)總數(shù)n滿足2^k＜n≤2^(k+1).考慮最簡單的情況n＝2^k+1，在1號被殺死后，總數(shù)就變成2^k了。接下來第一個被殺的當然是3號，將3號看成新1號，（最后一個2^k+1號就是新2^k-1），2號就是第2^k個，故最后留下的應(yīng)當是2號。設(shè)總數(shù)是n-1時，最后留下的是X號，那總數(shù)是n時，最后留下的是x＋2號。每增加一個老鼠（或人），最后留下的老鼠（或人）的號數(shù)就增加2，2^k+1個人，最后留下2號；2^k+2個人，最后留下4號，依此類推，2^k＋m個人，最后留下的是2m號?！毩?xí)（1）把1～999這999個自然數(shù)按順時針的方向依次排列在一個圓圈上（如圖）．從1開始按順時針的方向，保留1，擦去2；保留3，擦去4…這樣每隔一個數(shù)擦去一個數(shù)，轉(zhuǎn)圈擦下去．問：最后剩下一個數(shù)時，剩下的是哪個數(shù)？分析與解:

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

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

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

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

約瑟夫斯問題：

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

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

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

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

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

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

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