個球稱3次找壞球的數(shù)學(xué)解答（原作者方）(共12頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 序篇（4-4-4分組整體稱法）古老的智力題詳述:    有12個球特征相同,其中只有一個重量異常,要求用一部沒有砝碼的天平稱三次,將那個重量異常的球找出來。以下會給4個解答，一個比一個牛，一個比一個震撼！第一篇先給個被號稱網(wǎng)上最牛的解答，一種新的完全的數(shù)學(xué)解法（線代+信息論），該文解法創(chuàng)于2005年，一次與友人聊天建議發(fā)表到QQ的個人空間（2006年7月），后被網(wǎng)友轉(zhuǎn)載到各大網(wǎng)站并被收入到百度文庫。第二篇會給個EXCEL進(jìn)階解法，網(wǎng)友們可以用此法加上分塊矩陣的方法繼續(xù)找出9球稱4次找2異常球的具體解法或更復(fù)雜的稱球問題。第三篇

2、會給出2個很漂亮完美的非常特別的解，其稱量結(jié)果的三進(jìn)制和異常球序號及和輕重狀態(tài)具有簡潔的一一對應(yīng)關(guān)系。 先給個444分組的具體稱量方案：把12個球編成1，2.12號，則可設(shè)計下面的稱法：              左盤 * 右盤      第一次 1，5，6，12 * 2，3，7，11      第二次 2，4，6，10 * 1，3，8，12  &

3、#160;   第三次 3，4，5，11 * 1，2，9，10    每次都可能有平、左重、右重三種結(jié)果，搭配起來共有27種結(jié)果，但平、平、平的結(jié)果不會出現(xiàn)，因?yàn)榭傆幸粋€球是不相等的。同樣左、左、左，右、右、右的結(jié)果也不回出現(xiàn)，因?yàn)楦鶕?jù)設(shè)計的稱法，沒有一個球是三次都在左邊或右邊的。剩下的24種結(jié)果就可以判斷出哪種情況是哪一個球了。例如：如果結(jié)果是平、平、左或是平、平、右，就可判斷出是9號球，因?yàn)榈谝淮闻c第二次都沒有9號球，唯獨(dú)第三次有9號球，而第一次與第二次都是平的，只有第三次是失衡的，說明9號球的重量與其它的球不同。可依據(jù)此原理判斷出其它的各

4、種情況分別是哪個球。    有12個球，而壞球又可能比好球輕也可能比好球重，所以總共有12x2=24種可能，24可能結(jié)果如下表：    * * * *    * 可 能 * * 結(jié) 果 *    * 可 能 * 結(jié) 果 * * * * *    1號球，且重 左、右、右    1號球，且輕 右、左、左    2號球，且重 右、左、右    2號球，

5、且輕 左、右、左    3號球，且重 右、右、左    3號球，且輕 左、左、右    4號球，且重 平、左、左    4號球，且輕 平、右、右    5號球，且重 左、平、左    5號球，且輕 右、平、右    6號球，且重 左、左、平    6號球，且輕 右、右、平    7號球，且重 右、平、平  &

6、#160; 7號球，且輕 左、平、平    8號球，且重 平、右、平    8號球，且輕 平、左、平    9號球，且重 平、平、右    9號球，且輕 平、平、左    10號球，且重平、左、右    10號球，且輕平、右、左    11號球，且重右、平、左    11號球，且輕左、平、 右   12號球，且重左、右、平

7、60;   12號球，且輕右、左、平    上面的24種結(jié)果里面沒有一個重復(fù)的，也可以把上面的結(jié)果反過來當(dāng)成可能，也可唯一的推出那個球?yàn)閴那?，證明此方法可行。第一篇（完美的數(shù)學(xué)建模）    原文：網(wǎng)上的最多的方法是邏輯法,還有少數(shù)畫成圖的所謂策略樹和基于此的程序算法.這里我提出一種新的完全的數(shù)學(xué)解法:一·首先提出稱量的數(shù)學(xué)模型: 把一次稱量看成一個一次代數(shù)式,同樣問題就可以描述成簡單的矩陣方程求解問題.怎么把一次稱量表示成一個代數(shù)式呢? 1),簡化描述小球的重量(狀態(tài))-正常球重量設(shè)為0,設(shè)異常

8、球比正常球重為1或輕為-1,異常球未知輕重時用x代表(只取1或-1).用列向量j表示所有球的重量狀態(tài). 2),簡化描述稱量的左右(放法)-把某號球放左邊設(shè)為1,右邊設(shè)為-1,不放上去設(shè)為0.用行向量i表示某次稱量所有球的左右狀態(tài). 3),描述稱量結(jié)果: 由1),2)已經(jīng)可以確定一個稱量式 各球的重量*放法=天平稱量結(jié)果.-(1)式 如果我們用向量j,i分別表示球的重量狀態(tài)和球的左右放法情況(j為行向量,i為列向量),對于(1)式,可以改寫為 j*i=a(常數(shù)a為單次稱量結(jié)果) -(2)式 例如有1-6號共6個小球,其中4號為較重球,拿3號5號放左邊,1號4號放右邊進(jìn)行稱量,式子為: (-1)*

9、0+0*0+1*0+(-1)*1+1*0+0*0=-1, 從-1的意義可以知道它表示結(jié)果的左邊較輕; 同樣可以得到0表示平衡,1表示左邊較重. 4),方程用來描述稱量過程,還需附加一個重要的條件:代表放左邊的1和右邊的-1個數(shù)相等,也就是 各球的放法=0-(3)式 這樣就解決了稱量的數(shù)學(xué)表達(dá)問題. 對于12個小球的3次稱量,分別用12維行向量j1,j2,j3表示,由j1j2j3便構(gòu)成了3×12的稱量矩陣J；對于某一可能情況i,對應(yīng)的3次稱量結(jié)果組成的3維列向量b,得 J*i=b 二·稱球問題的數(shù)學(xué)建模 問題的等價： 設(shè)J為3×12的矩陣，滿足每行各項(xiàng)之和為0。i為

10、12維列向量,i的某一項(xiàng)為1或1，其他項(xiàng)都是0，即i是12×24的分塊矩陣M=(E,-E)的任一列。而3×27的矩陣C為由27個互不相同的3維列向量構(gòu)成，它的元素只能是1,0,-1. 由問題的意義可知b=J*i必定是C的某一列向量。而對于任意的i,有由J*i=b確定的b互不相同. 即 J*M=J*(E,-E)=(B,-B)=X -（設(shè)X為3×24的矩陣） 因?yàn)閄為24列共12對互偶的列向量，而C為27列，可知從C除去的3列為(0,0,0)和1對任意的互偶的列向量，這里取除(1,1,1)和(-1,-1,-1). 由上式得J*E=B推出J=B,X=(J,-J)。因此把

11、從27個3維列向量中去除(0,0,0),(1,1,1),(-1,-1,-1)然后分為互偶的兩組(對應(yīng)取反) 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1; 0, 1, 1, 1, 0, 0, 0, 1, 1,-1,-1,-1; 1, 0, 1,-1, 0, 1,-1, 0,-1, 0, 1,-1. 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1; 0,-1,-1,-1, 0, 0, 0,-1,-1, 1, 1, 1; -1, 0,-1, 1, 0,-1, 1, 0, 1, 0,-1, 1. 現(xiàn)在通過上下對調(diào)2列令各行的各項(xiàng)和為0！即可得到J.我的方

12、法是從右到左間隔著進(jìn)行上下對調(diào)，然后再把2排和3排進(jìn)行上下對調(diào)，剛好所有行的和為0。得 稱量矩陣J= 0, 0, 0, 0, 1,-1, 1,-1, 1,-1, 1,-1; 0, 1,-1,-1, 0, 0, 0,-1, 1, 1,-1, 1; 1, 0,-1, 1, 0,-1,-1, 0,-1, 0, 1, 1. 相應(yīng)三次稱量兩邊的放法： 左邊5，7，9，11 ：右邊6，8，10，12； 左邊2，9，10，12：右邊3，4，8，11； 左邊1，4，11，12：右邊3，6，7，9 。 * * * * 1號球，且重 平、平、左 1號球，且輕 平、平、右 2號球，且重 平、左、平 2號球，且輕 平

13、、右、平 3號球，且重 平、右、右 3號球，且輕 平、左、左 4號球，且重 平、右、左 4號球，且輕 平、左、右 5號球，且重 左、平、平 5號球，且輕 右、平、平 6號球，且重 右、平、右 6號球，且輕 左、平、左 7號球，且重 左、平、右 7號球，且輕 右、平、左 8號球，且重 右、右、平 8號球，且輕 左、左、平 9號球，且重 左、左、右 9號球，且輕 右、右、左 10號球，且重右、左、平 10號球，且輕左、右、平 11號球，且重左、右、左 11號球，且輕右、左、右 12號球，且重右、左、左 12號球，且輕左、右、右 三·問題延伸 1，13個球稱3次的問題： 從上面的解答中被除

14、去的3個向量為(0,0,0)(1,1,1)(-1,-1,-1).而要能判斷第13個球，必須加入1對對偶向量，如果加入的是(1,1,1)(-1,-1,-1),則 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1，1; 0, 1, 1, 1, 0, 0, 0, 1, 1,-1,-1,-1，1; 1, 0, 1,-1, 0, 1,-1, 0,-1, 0, 1,-1，1. 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1; 0,-1,-1,-1, 0, 0, 0,-1,-1, 1, 1, 1,-1; -1, 0,-1, 1, 0,-1, 1, 0, 1,

15、0,-1, 1,-1. 第一行的非0個數(shù)為奇數(shù)，不論怎么調(diào)也無法使行和為0。故加入的行只能為自對偶列向量(0,0,0),結(jié)果是異球可判斷是否是第13球時卻無法檢查輕重。也可見，13球稱3次的問題和12球稱3次的問題只是稍有不同，就如12個球問題把球分3組4個稱，而13個球問題把球分4組(4,4,4,1),第13個球單獨(dú)1組。 2，(3N-3)/2個球稱N次找出異球且確定輕重的通解： 第一步，先給出3個球稱2次的一個稱量矩陣J2 0, 1,-1; -1, 0, 1. 第二步，設(shè)Kn=(3N-3)/2個球稱N次的稱量矩陣為N行×Kn列的矩陣Jn,把(3N/3-3)/2個球稱N-1次的稱量

16、矩陣J<n-1>簡寫為J.再設(shè)N維列向量Xn,Yn,Zn分別為(0,1,1,.,1),(1,0,0,.,0),(1,-1,-1,.,-1). 第三步之1，在N-1行的矩陣J上面添加1行各項(xiàng)為0，成新的矩陣J'. 第三步之2，在N-1行的矩陣J上面,添加行向量t=(1,1,.,1,-1,-1,.,-1),成新的矩陣J".t的維(長)和J的列數(shù)一致，t的前面各項(xiàng)都是1，后面各項(xiàng)都是1；t的長為偶數(shù)時，1個數(shù)和1個數(shù)相等；t的長為奇數(shù)時，1個數(shù)比1個數(shù)少1個； 第三步之3，在N-1行的矩陣-J上面,添加行向量t=(1,1,.,1,-1,-1,.,-1),成新的矩陣J&q

17、uot;'. 第四步，當(dāng)J的列數(shù)即t的長為奇數(shù)時，用分塊矩陣表示矩陣Jn(J',J",J"',Xn,Yn,Zn);當(dāng)J的列數(shù)即t的長為偶數(shù)時，用分塊矩陣表示矩陣Jn(J',J",J"',Xn,-Yn,Zn); 此法可以速求出一個J3為 0, 0, 0, 1,-1,-1, 1,-1,-1, 0, 1, 1; 0, 1,-1, 0, 1,-1, 0,-1, 1, 1, 0,-1; -1, 0, 1, -1, 0, 1, 1, 0,-1, 1, 0,-1. 同樣可以繼續(xù)代入求出J4,J5的稱量矩陣。 3，2類主要的推廣：

18、 第1類，有(3n-3)/2個球，其中有一個異球，用天平稱n次，找出該球并確定是較輕還是較重。 第2類， 有n個球，其中混入了m個另一種規(guī)格的球，但是不知道異球比標(biāo)球重還是輕，稱k次把他們分開并確定輕重？ 顯然，上面的推廣將球分為了兩種，再推廣為將球分為n種時求稱法。 對于第一類推廣，上面已經(jīng)給出了梯推的通解式。而對于第二類推廣，僅對于m=2時的幾個簡單情況有了初步的了解，如5個球稱3次找出2個相同的異球，9個球稱4次找出2個相同的異球，已經(jīng)獲得了推理邏輯方法上的解決，但是在矩陣方法上仍未理出頭緒，16個球稱5次找出2個相同的異球問題上普通的邏輯方法變得非常煩瑣以至未知是否有解，希望有高手能繼

19、續(xù)用矩陣方法找出答案，最好能獲得m=2時的遞推式。 上面的通解法得到的J4= 0,0, 0, 0, 0, 0,0, 0, 0,0,0, 0, 1,1, 1, 1, 1, 1,-1,-1,-1,-1,-1,-1,1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1,-1,0,-1, 1; 0,0, 0, 1,-1,-1,1,-1,-1,0,1, 1, 0,0, 0, 1,-1,-1, 1,-1,-1, 0, 1, 1,0, 0, 0,-1, 1, 1,-1, 1, 1, 0,-1,-1,1, 0,-1; 0,1,-1, 0, 1,-1,0,-1, 1,1,0,-1, 0,1,-1, 0

20、, 1,-1, 0,-1, 1, 1, 0,-1,0,-1, 1, 0,-1, 1, 0, 1,-1,-1, 0, 1,1, 0,-1; -1,0, 1,-1, 0, 1,1, 0,-1,1,0,-1,-1,0, 1,-1, 0, 1, 1, 0,-1, 1, 0,-1,1, 0,-1, 1, 0,-1,-1, 0, 1,-1, 0, 1,1, 0,-1. 第二篇（EXCEL構(gòu)造大法）此法可以便捷直觀地驗(yàn)證所構(gòu)造的稱量方法是否是正確的！解決了對答案進(jìn)行正確性驗(yàn)證的難題。并且可以通過構(gòu)造分塊矩陣最終解決N球稱M次找2異常球的更高級稱球問題！貼不了EXCEL原檔，只能先截個圖了，此法要先溫習(xí)前一篇

21、的解法才風(fēng)味更佳：步驟詳解：第一步,做分塊矩陣M=-E12,E12。第二步，構(gòu)造稱量矩陣，每一列互不相同，為了滿足完備性，可以調(diào)整各列。第三步，兩矩陣求積，函數(shù)MMULT(，)第四步，對結(jié)果矩陣求各列的對應(yīng)3進(jìn)制并算出具體K值。k值函數(shù)示例(-1)B24*SIGN(B24)第五步，做三位（-1,0,1）的3進(jìn)制的全排列和對應(yīng)序列碼第六步，對于各序列碼M，做出在N中與之相等的元素個數(shù)Tt函數(shù)示例COUNTIF($B24:$Y24,B31)第七步，求MAX(T),若為1，則保證了稱量結(jié)果矩陣M的每列都是互不相同的（各列唯一性），既題得證，所構(gòu)造的稱量方案矩陣J是正確的次球狀態(tài)：M輕：負(fù)單位矩陣-E

22、12重：單位矩陣E121-10000000000010000000000020-10000000000010000000000300-10000000000010000000004000-10000000000010000000050000-10000000000010000000600000-10000000000010000007000000-10000000000010000080000000-10000000000010000900000000-100000000000100010000000000-100000000000100110000000000-100000000000101

23、200000000000-1000000000001稱量方案：J12345678910111213求和：稱量完備性要求行和須為零第一次0000-111-11-11-10第二次01-111-1000-11-10第三次-1-10110-10110-10稱量結(jié)果：X=J*M（矩陣求內(nèi)積函數(shù)MMULT(B16:M18,B2:Y13)）a00001-1-11-11-110000-111-11-11-1b0-11-1-110001-1101-111-1000-11-1c110-1-1010-1-101-1-10110-10110-1三進(jìn)制編碼：n1-23-45-6-89-1011-1213-12-34-5

24、68-910-1112-13絕對值|n|1234568910111213k=(-1)n*n/|n|-1-1-1-1-1-1-1-1-1-1-1-1111111111111令：k=-1為球輕,k=1為球重;n=9a+3b+c元素-1,0,1組成的所有排列P:-1-1-1-1-1-1-1-1-1000000000111111111-1-1-1000111-1-1-1000111-1-1-1000111-101-101-101-101-101-101-101-101-101序列碼m：-13-12-11-10-9-8-7-6-5-4-3-2-1012345678910111213求n=m的元素個數(shù)t：

25、函數(shù)COUNTIF()111111011111101111110111111最大值！MAX(t)1MAX(t)=1保證M的每列都是互不相同的，既題得解重排：把12個球分兩組(1號到6號,8號到13號)編好序號壞球n對應(yīng)稱量結(jié)果：球序號|n|1234568910111213第一次a0000-111-11-11-10a第二次b01-111-1000-11-10b第三次c-1-10110-10110-10cn=9a+3b+c-12-34-568-910-1112-13k=(-1)n*n/|n|111111111111注：求和目的是檢查稱量完備性，記k=(-1)n*n/|n|abc只能是左邊12列中的一列或取反，既(a,b,c)T=(a',b',c')T或(-a',-b',-c')T對應(yīng)的：|n|為壞球序號，且k=-1為球輕，k=1為球重第三篇（簡潔特解，有趣