12個球稱3次找壞球的完美解答
古老的智力題詳述:
有12個球特征相同,其中只有壹個重量異常,要求用壹部沒有砝碼的天平稱三次,將那個重量異常的球找出來。
網上的最多的方法是邏輯法,還有少數畫成圖的所謂策略樹和基於此的程序算法.這道題有13種不同的答案.這裏我提出壹種新的完全的數學解法:
壹·首先提出稱量的數學模型:
把壹次稱量看成壹個壹次代數式,同樣問題就可以描述成簡單的矩陣方程求解問題.怎麽把壹次稱量表示成壹個代數式呢?
1),簡化描述小球的重量(狀態)----正常球重量設為0,設異常球比正常球重為1或輕為-1,異常球未知輕重時用x代表(只取1或-1).用列向量j表示所有球的重量狀態.
2),簡化描述稱量的左右(放法)-----把某號球放左邊設為1,右邊設為-1,不放上去設為0.用行向量i表示某次稱量所有球的左右狀態.
3),描述稱量結果:
由1),2)已經可以確定壹個稱量式
∑各球的重量*放法=天平稱量結果.--------(1)式
如果我們用向量j,i分別表示球的重量狀態和球的左右放法情況(j為行向量,i為列向量),對於(1)式,可以改寫為
j*i=a(常數a為單次稱量結果) -------------(2)式
例如有1-6號***6個小球,其中4號為較重球,拿3號5號放左邊,1號4號放右邊進行稱量,式子為:
(-1)*0+0*0+1*0+(-1)*1+1*0+0*0=-1,
從-1的意義可以知道它表示結果的左邊較輕;
同樣可以得到0表示平衡,1表示左邊較重.
4),方程用來描述稱量過程,還需附加壹個重要的條件:代表放左邊的1和右邊的-1個數相等,也就是
∑各球的放法=0-------------------------(3)式
這樣就解決了稱量的數學表達問題.
對於12個小球的3次稱量,分別用12維行向量j1,j2,j3表示,由j1j2j3便構成了3×12的稱量矩陣J；對於某壹可能情況i,對應的3次稱量結果組成的3維列向量b,得
J*i=b
二·稱球問題的數學建模
問題的等價：
設J為3×12的矩陣，滿足每行各項之和為0。i為12維列向量,i的某壹項為1或－1，其他項都是0，即i是12×24的分塊矩陣M=(E,-E)的任壹列。而3×27的矩陣C為由27個互不相同的3維列向量構成，它的元素只能是1,0,-1.
由問題的意義可知b=J*i必定是C的某壹列向量。而對於任意的i,有由J*i=b確定的b互不相同.
即
J*M=J*(E,-E)=(B,-B)=X -----（設X為3×24的矩陣）
因為X為24列***12對互偶的列向量，而C為27列，可知從C除去的3列為(0,0,0)和1對任意的互偶的列向量，這裏取除(1,1,1)和(-1,-1,-1).
由上式得J*E=B推出J=B,X=(J,-J)。因此把從27個3維列向量中去除(0,0,0),(1,1,1),(-1,-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].
[ 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].
現在通過上下對調2列令各行的各項和為0！！即可得到J.我的方法是從右到左間隔著進行上下對調，然後再把2排和3排進行上下對調，剛好所有行的和為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].
相應三次稱量兩邊的放法：
左邊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號球，且輕 －平、右、平
3號球，且重 －平、右、右 3號球，且輕 －平、左、左
4號球，且重 －平、右、左 4號球，且輕 －平、左、右
5號球，且重 －左、平、平 5號球，且輕 －右、平、平
6號球，且重 －右、平、右 6號球，且輕 －左、平、左
7號球，且重 －左、平、右 7號球，且輕 －右、平、左
8號球，且重 －右、右、平 8號球，且輕 －左、左、平
9號球，且重 －左、左、右 9號球，且輕 －右、右、左
10號球，且重－右、左、平 10號球，且輕－左、右、平
11號球，且重－左、右、左 11號球，且輕－右、左、平
12號球，且重－右、左、左 12號球，且輕－左、右、右
三·問題延伸
1，13個球稱3次的問題：
從上面的解答中被除去的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, 0,-1, 1,-1].
第壹行的非0個數為奇數，不論怎麽調也無法使行和為0。故加入的行只能為自對偶列向量(0,0,0),結果是異球可判斷是否是第13球時卻無法檢查輕重。也可見，13球稱3次的問題和12球稱3次的問題只是稍有不同，就如12個球問題把球分3組4個稱，而13個球問題把球分4組(4,4,4,1),第13個球單獨1組。
2，(3^N-3)/2個球稱N次找出異球且確定輕重的通解：
第壹步，先給出3個球稱2次的壹個稱量矩陣J2
[ 0, 1,-1];
[-1, 0, 1].
第二步，設Kn=(3^N-3)/2個球稱N次的稱量矩陣為N行×Kn列的矩陣Jn,把(3^N/3-3)/2個球稱N-1次的稱量矩陣J<n-1>簡寫為J.再設N維列向量Xn,Yn,Zn分別為(0,1,1,...,1),(1,0,0,...,0),(1,-1,-1,...,-1).
第三步之1，在N-1行的矩陣J上面添加1行各項為0，成新的矩陣J'.
第三步之2，在N-1行的矩陣J上面,添加行向量t=(1,1,...,1,-1,-1,...,-1),成新的矩陣J".t的維(長)和J的列數壹致，t的前面各項都是1，後面各項都是－1；t的長為偶數時，1個數和－1個數相等；t的長為奇數時，1個數比－1個數少1個；
第三步之3，在N-1行的矩陣-J上面,添加行向量t=(1,1,...,1,-1,-1,...,-1),成新的矩陣J"'.
第四步，當J的列數即t的長為奇數時，用分塊矩陣表示矩陣Jn＝(J',J",J"',Xn,Yn,Zn);當J的列數即t的長為偶數時，用分塊矩陣表示矩陣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].
同樣可以繼續代入求出J4,J5的稱量矩陣。
3，2類主要的推廣：
第1類，有(3^n-3)/2個球，其中有壹個異球，用天平稱n次，找出該球並確定是較輕還是較重。
第2類， 有n個球，其中混入了m個另壹種規格的球，但是不知道異球比標球重還是輕，稱k次把他們分開並確定輕重？ 顯然，上面的推廣將球分為了兩種，再推廣為將球分為n種時求稱法。
對於第壹類推廣，上面已經給出了梯推的通解式。而對於第二類推廣，僅對於m=2時的幾個簡單情況有了初步的了解，如5個球稱3次找出2個相同的異球，9個球稱4次找出2個相同的異球，已經獲得了推理邏輯方法上的解決，但是在矩陣方法上仍未理出頭緒，16個球稱5次找出2個相同的異球問題上普通的邏輯方法變得非常煩瑣以至未知是否有解，希望有高手能繼續用矩陣方法找出答案，最好能獲得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, 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].