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