經(jīng)典稱球問題Word版

1、傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！我將首先致力于解決下面的問題：問題：已知 N 個(gè)球中有1個(gè)是壞的，但不知輕重，問用天平至少稱多少次可以把它找出來，并判斷輕重？在解決這個(gè)問題之后，將是此問題的一些推廣，關(guān)于非隨機(jī)應(yīng)變策略，關(guān)于多臂天平，以及關(guān)于多個(gè)壞球等等。 我也說一句從一個(gè)最簡單的問題開始問題：假設(shè)三個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且已知是重的,則可以稱幾次將非標(biāo)準(zhǔn)球找出來？個(gè)人企業(yè)舉報(bào)垃圾信息舉報(bào)我也說一句假設(shè)三個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且已知是重的,則可以稱一次將非標(biāo)準(zhǔn)球找出來。方法是隨便取兩個(gè)來稱，如果天平平衡，則第三個(gè)球是壞的，如果天平不平衡，則較重的那個(gè)球是壞的。那么，如果是9個(gè)

2、球的話，又如何呢？假設(shè)9個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且已知是重的,則可以稱2次將非標(biāo)準(zhǔn)球找出來。方法是把9個(gè)球分成3組A,B,C，第一次稱其中兩組(A vs B)，如果天平平衡，說明壞球在C組，如果天平不平衡，則壞球在較重的那一組中，然后問題歸結(jié)為3個(gè)球的情況 我也說一句假設(shè)3k個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且已知是重的,則可以稱k次將非標(biāo)準(zhǔn)球找出來?；蛘哒f：【定理】假設(shè) N 個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且已知是重的,則可以稱log3(N)次將非標(biāo)準(zhǔn)球找出來。=找不到上取整符號(hào)，我用表示上取整，=好了，這是我們得到的第一個(gè)一般性的結(jié)論。為了嚴(yán)密起見，我將嚴(yán)格的證明它。我需要證明的是下面兩條：1.N=3k+1時(shí)，稱k次不

3、能必然把壞球找出來。我也說一句 我也說一句 我也說一句 我也說一句1.N=3k時(shí)，可以稱k次把壞球找出來。首先說明一個(gè)平凡的情況：N=1此時(shí)，既然已經(jīng)知道有一個(gè)壞球，而又只有一個(gè)球，則它自然就是壞球也就是說稱0次可以把它找出來，因而命題成立。下面用歸納法證明，對(duì)k歸納(1)k=1時(shí)此時(shí)N=1，2或3N=1時(shí)不用說了N=2時(shí)，有兩個(gè)球A,B，則稱A vs B，較重的那個(gè)是壞的，一次就可以把壞球找出來N=3時(shí), 見3L。也是一次就可以把壞球找出來。(2)假設(shè)對(duì)k-1命題成立，即N=3(k-1)時(shí)，可以稱k-1次把壞球找出來。當(dāng)N=3k時(shí)，首先將N個(gè)球平均分成A,B,C 3份(此處“平均”是指每兩份

4、之間相差不超過1個(gè))容易知道，|A|,|B|,|C|都=3(k-1)，并且其中有兩組球個(gè)數(shù)相等（有可能三組球個(gè)數(shù)都相等）我們?nèi)〕鰞山M個(gè)數(shù)相等的球，不妨設(shè)為A,B第一次 稱 A vs B如果天平平衡，說明壞球在C組中，如果天平不平衡，說明壞球在A,B中較重的那一組中總之，我們把壞球限制在A,B,C中的一組當(dāng)中由于每一組球的個(gè)數(shù)都=3(k-1),由歸納假設(shè)，我們可以用k-1次從A(或BC)中將壞球找出來因此我們可以用k次從N=3k+1時(shí)，稱k次不能必然把壞球找出來。這個(gè)涉及到信息論，簡單來說就是一共有3k+1種可能的結(jié)果，每一次稱量可以從3組（互不相容的）信息中選出一種因此k次稱量最多可以從3k種

5、不同的結(jié)果中選出一種所以 N=3k+1時(shí)，稱k次不能必然把壞球找出來。=或者說我們有這樣一個(gè)原理：如果要從M種可能的情況中確定一種情況，又每次測量有a個(gè)結(jié)果，則最少需要測量loga(M) 次。當(dāng)然實(shí)際需要的次數(shù)可能更多，因?yàn)槟悴荒鼙ＷC每次都得到“有用”的信息。但是 loga(M) 是所需次數(shù)的一個(gè)下界，我們把這個(gè)值稱為【信息論下界】=回到4L的定理，我們有相對(duì)應(yīng)的一個(gè)結(jié)論【定理】假設(shè) N 個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且已知是輕的,則可以稱log3(N)次將非標(biāo)準(zhǔn)球找出來?，F(xiàn)在，在已知壞球輕重的情況下，我們得到了把壞球找出來的最少次數(shù) 我也說一句假設(shè)3k個(gè)球中有一個(gè)不標(biāo)準(zhǔn),其中一部分已知不重,另一部分已

6、知不輕,則可以稱k次將非標(biāo)準(zhǔn)球找出來,并判定其輕重.假設(shè)3k個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且這3k個(gè)球一部分已知不重,另一部分已知不輕,則可以稱幾次將非標(biāo)準(zhǔn)球找出來？=所謂某個(gè)球不重是指這個(gè)球或者是標(biāo)準(zhǔn)的，或者是壞的但比標(biāo)準(zhǔn)球輕=首先這個(gè)問題的信息論下界是 k 次，那么k次能把壞球找出來嗎？ 我也說一句首先解決LS提出的問題：假設(shè)N=3k個(gè)球中有一個(gè)不標(biāo)準(zhǔn),其中一部分已知不重,另一部分已知不輕,則可以稱k次將非標(biāo)準(zhǔn)球找出來,并判定其輕重.（注意此處我沒說N(3k-1)/2的話N=(3k+1)/2由信息論下界知稱k次是不能將非標(biāo)準(zhǔn)球找出來,并判定其輕重的。） 我也說一句在歸納假設(shè)中，我假設(shè)命題對(duì)k-1成立

7、，意思是對(duì)N=3(k-1)個(gè)球，只要滿足命題條件，都可以用k次將壞球找出來?；蛘哒f，3(k-1)分成兩組，一組已知不重，一組已知不輕，（不論滿不滿足情形1）都可以用k次將壞球找出來。收起回復(fù)收起回復(fù) 我也說一句吧友58.61.56.*我看到13L的時(shí)候發(fā)現(xiàn)自己對(duì)不重不輕這兩個(gè)概念理解不能k=1，N=3個(gè)球,共有四種情況(1) 全部不重 (2)全部不輕 (3) 兩個(gè)球不重，一個(gè)球不輕 (4) 兩個(gè)球不輕，一個(gè)球不重什么叫全部不重？什么叫全部不輕？ 我也說一句吧友58.61.56.*全部不重是指三個(gè)球全部不重于標(biāo)準(zhǔn)球？那就是壞球是輕球？那么兩個(gè)不重，一個(gè)不輕又是指什么呢？有兩個(gè)球不重于標(biāo)準(zhǔn)球，如果

8、它們中有一個(gè)是壞球，那么壞球是輕球；如果不是，則壞球是不輕的那個(gè)球，也就是重球。同樣的，兩個(gè)不輕，一個(gè)不重，則壞球分別是重球和輕球。是不是這樣？ 我也說一句吧友58.61.56.*不知道為什么LZ要造出這兩個(gè)概念來三個(gè)球，有一個(gè)是壞的，不是輕就是重。什么叫不輕？什么叫不重？這種題目總是用三分法來做的吧？分成三部分，兩個(gè)一稱，平的話在第三堆，不平的話則在這兩堆中。然后繼續(xù)判斷。 我也說一句 我也說一句吧友58.61.56.*假設(shè)一次能一堆一堆的稱，則球的總數(shù)目為3K情形的：均分三堆，稱兩次知道壞球在哪一堆，不可能更?。ㄒㄗ顗那樾危┝頢I表示第I次得到的壞球那一堆的數(shù)目以及HI為此時(shí)已用的稱量

9、次數(shù)則HI=2I，SI=3(K-I)I=K時(shí)，HI=2K,SI=1。稱量完畢。至于輕重，在上述的稱法中每得到下一個(gè)SI時(shí)即已得出。無需再稱。然后不明白LZ為什么寫那么多來說明這種能夠一堆一堆的稱，并且球總數(shù)還為3K的情況回復(fù) 收起回復(fù) 我也說一句吧友58.61.56.*證明：A,B,C三堆。第一次：AB。若平，說明是C。若不平，C是好的。然后稱第二次：第二次：AC。若平，說明是B；若不平，說明是A。由于ABC只是任意相同數(shù)目的堆，所以對(duì)于此類三等均分情形均得證另外：第一次中知道是C，但不知輕重。第二次就一定知道。不會(huì)運(yùn)氣好的這么離譜，每次都一次直接找出吧？ 我也說一句吧友61.150.43.*

10、在14L的結(jié)論中，我們說過，對(duì)N=2是不成立的，實(shí)際上這是唯一的一個(gè)特例，我們有：假設(shè)3=N=3k個(gè)球中有一個(gè)不標(biāo)準(zhǔn),其中一部分已知不重,另一部分已知不輕,稱k次將非標(biāo)準(zhǔn)球找出來,并判定其輕重.另外，對(duì)于N=2的情況，借助一個(gè)標(biāo)準(zhǔn)球也可以一次將非標(biāo)準(zhǔn)球找出來。這個(gè)證明略。 現(xiàn)在證明這個(gè)：假設(shè)N(3k-1)/2個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且不知其輕重,則可以借助一個(gè)標(biāo)準(zhǔn)球稱k次將非標(biāo)準(zhǔn)球找出來,并判定其輕重.對(duì)k歸納。k=1時(shí)，N=1.用標(biāo)準(zhǔn)球與這一個(gè)球稱一次就可以了。假設(shè)命題對(duì)=k-1,成立，則對(duì)N(3k-1)/2個(gè)球?qū)⑶蚱骄殖?組A,B,C,（平均指每兩組個(gè)數(shù)相差不超過1），則每組個(gè)數(shù)=(3k+1

11、)/2 ）或者說，至多有一組個(gè)數(shù)=(3(k-1)+1)/2。不妨設(shè)A組個(gè)數(shù)最多。（|B|,|C|=(3(k-1)-1)/2 ）第一次，稱A vs B （如果|B|A|的話，在B中加上那個(gè)標(biāo)準(zhǔn)球）如果天平平衡，則說明壞球在C組中，由歸納假設(shè)，可以用k-1次將非標(biāo)準(zhǔn)球找出來并判斷其輕重（借助標(biāo)準(zhǔn)球）如果天平不平衡，不妨設(shè)A重B輕。則(1)非標(biāo)準(zhǔn)球在A和B中，C中的都是標(biāo)準(zhǔn)球。 (2)2=|A|+|B|=3(k-1).我們?nèi),B兩組的所有球則壞球在這N（3=N=3個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且不知其輕重,則可以稱log3(2N+3)次將非標(biāo)準(zhǔn)球找出來,并判定其輕重.或者說k次可以從至多 (3k-3)/2

12、個(gè)球中將壞球找出來，并判斷其輕重。（這個(gè)數(shù)列的前幾項(xiàng)是 a2=3, a3=12, a4=39, a5=120 .）下面我證明兩條：1.或者說k次可以從 N=3)。2.N=(3k-1)/2個(gè)球，用k次是不能將壞球找出來，并判斷其輕重的。證明1. k=1是沒有意義的，k=2.將 N=(3k-3)/2 個(gè)球平均分成3份，則每份最多有 (3(k-1)-1)/2 個(gè)球，并且有兩份數(shù)目相等。設(shè)A,B,C三組，A,B相等。（另外，每組至少有一個(gè)球）第一次 A vs B如果平衡，說明壞球在C組，而且我有了一個(gè)標(biāo)準(zhǔn)球。又 |C|=(3(k-1)-1)/2,根據(jù)29L的結(jié)論，我可以用k-1次將壞球找出來并判斷其輕

13、重。如果不平衡，則壞球在A,B中，并且我已知了一部分不重，另一部分不輕，而且我有了一個(gè)標(biāo)準(zhǔn)球。又 |A|+|B|=(3k+1)/2，則所需次數(shù)的信息論下界log3(2N)=k+1，因此k次顯然不夠。 下面假設(shè) N=(3k-1)/2由于每次稱量天平的兩邊必須放相同數(shù)目的球（否則得不到確定的信息），假設(shè)第一次 A vs B，對(duì)第一次稱球的數(shù)目分兩種情況討論，情形1：|A|=|B|=(3(k-1)+1)/2，如果A,B平衡的話，我需要在C組中找出壞球并判斷其輕重。 而這時(shí)的信息論下界至少為log3(3(k-1)+1)=k。 所以至少需要k次。這種情況下共需k+1次。情形2：|A|=|B|=(3(k-

14、1)+1)/2,在這種情形下，如果A,B不平衡的話，則壞球在A,B中，（當(dāng)然我可以知道一部分不重，另一部分不輕），但A,B球總數(shù)=3(k-1)+1，因此這時(shí)的信息論下界至少為log3(3(k-1)+1)=k。 所以至少需要k次。這種情況下共需k+1次?？傊?，我不能只用k次將壞球找出來并判斷其輕重。 我也說一句吧友61.150.43.*現(xiàn)在，我完全回答了這個(gè)問題假設(shè)N個(gè)球中有一個(gè)不標(biāo)準(zhǔn),且不知其輕重,則可以稱多少次將非標(biāo)準(zhǔn)球找出來,并判定其輕重呢，是 log3(2N+3) 次。實(shí)際上，當(dāng)N=3k（k較大時(shí)），log3(2N+3)=k+1（即不知球輕重的情形下，需要比已知球輕重的情形多稱一次）以9

15、個(gè)球，其中一個(gè)壞球，不知輕重為例：分成三組，A、B、C，先稱A和B，1. A和B平衡，則壞球在C中，再多稱一次A和C,即可判斷出壞球是輕還是重，歸結(jié)為已知球輕重的情形。2. A和B不平衡，不妨假設(shè)AB,再稱B和C：3.4.5.6. 若B和C平衡，則說明壞球在A中，且是重球，7. 若CB，說明壞球在B中，且是輕球，若BC，此種情形不可能出現(xiàn)。8.9.10.11.12. 亦歸結(jié)為已知球輕重的情形。證畢。 13.14.15.16.17.18.19.20.21.22. 當(dāng)我們不要求判斷輕重的情況下，又需要多少次呢？或者說，k次最多可以從多少個(gè)球里找出壞球呢？(首先說這個(gè)的信息論下界是log3(N),而

16、并非log3(2N),因?yàn)橹挥蠳種可能的結(jié)果）答案是 k次最多可以從 (3k-1)/2 個(gè)球里找出壞球.（與需要判斷輕重的情況比較，僅僅多1個(gè)球）我也說一句我來試著根據(jù)樓主的思路接著證明最這個(gè)問題吧，但得事先加一個(gè)獨(dú)立在試驗(yàn)球數(shù)之外的標(biāo)準(zhǔn)球。構(gòu)造方式如下：k=0和k=1時(shí)是個(gè)平凡解。k=2時(shí)，(3k-1)/2=4。從4個(gè)球中任取2個(gè)球a,b放在天平上，若a,b平衡則壞球在剩下的2個(gè)球c,d里，此時(shí)標(biāo)準(zhǔn)球是a,b，用標(biāo)準(zhǔn)球能輕易比較出c,d誰是壞球。（因?yàn)椴恍枰垒p重）；若a,b不平衡則壞球在a,b里，此時(shí)標(biāo)準(zhǔn)球是c,d，同理用標(biāo)準(zhǔn)球能輕易比較出c,d誰是壞球。不妨設(shè)k=n-1時(shí)命題成立，其中

17、n可取大于3的任意自然數(shù)，即(3(n-1)-1)/2個(gè)球能用n-1次稱出壞球來，現(xiàn)在構(gòu)造k=n的情況：將(3n-1)/2個(gè)球均分為每份差小于等于1的3份，顯然最大的1份(不妨設(shè)為集合A)為(3(n-1)+1)/2 ,同時(shí)較小的2份（設(shè)為集合B,C）一定相等且為(3(n-1)-1)/2。首先任取一份較小的，不妨取B,并加上一個(gè)標(biāo)準(zhǔn)球,和A稱重(注意|B|=|C|=|A-1|=(3(n-1)-1)/2)，若天平平衡，則壞球在余下較小的那份，即C里，由歸納歸納可得結(jié)論成立。若天平不平衡，不妨設(shè)傾向A（傾向B結(jié)論一樣），此時(shí)可知所有A里的小球非輕，并且所有B里的小球非重，并且|A|+|B|=(3(n-

18、1)-1)/2 +(3(n-1)+1)/2 =3(n-1)。此時(shí)由29L的結(jié)論可得結(jié)論成立。顯然以上歸納了每一種原命題的情況。我來試著根據(jù)樓主的思路接著證明最后這個(gè)問題吧:k次最多可以從多少個(gè)球里找出壞球.事先加一個(gè)獨(dú)立在試驗(yàn)球數(shù)之外的標(biāo)準(zhǔn)球。構(gòu)造方式如下：k=0和k=1時(shí)是個(gè)平凡解。k=2時(shí)，(3k-1)/2=4。從4個(gè)球中任取2個(gè)球a,b放在天平上，若a,b平衡則壞球在剩下的2個(gè)球c,d里，此時(shí)標(biāo)準(zhǔn)球是a,b，用標(biāo)準(zhǔn)球能輕易比較出c,d誰是壞球。（因?yàn)椴恍枰垒p重）；若a,b不平衡則壞球在a,b里，此時(shí)標(biāo)準(zhǔn)球是c,d，同理用標(biāo)準(zhǔn)球能輕易比較出c,d誰是壞球。不妨設(shè)k=n-1時(shí)命題成立，其中n可取大于3的任意自然數(shù)，即(3(n-1)-1)/2個(gè)球能用n-1次稱出壞球來，現(xiàn)在構(gòu)造k=n的情況：將(3n-1)/2個(gè)球均分為每份差小于等于1的3份，顯然最大的1份(不妨設(shè)為集合A)為(3(n-1)+1)