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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、個球，其中一個壞球，不知輕重為例：分成三組，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. 當我們不要求判斷輕重的情況下，又需要多少次呢？或者說，k次最多可以從多少個球里找出壞球呢？(首先說這個的信息論下界是log3(N),而

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

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

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