對於12樓的BS法
可以推出不可能少於100次
證明
(1)若每次都是1-1秤輕重
目的是要有66次BS
為了要得到BS
就要各有B(或者S)的一起秤就一定會得到一個BS
或者兩個未知秤可得到一個B一個S
而若是B和S秤則可能浪費一次秤(兩個資訊量)得到BB和SS
而若是一個B(或S)和一個未知的秤則可能得到BB(SS)和S(B)
浪費一次資訊量而直接測兩個未知可得到兩的資訊量
因此要秤重數最少只能秤兩個未知或者同是B或者同是S
方法數>=34+33*2=100
(67次的秤重方法為幸運方法就是每一次拿B(或者S)和一個未知秤都得到一個BS和一個S(或者B))
因此1-1秤法的最小值為(一般式)
0.1.3.4.6.7.9.....從一個開始(奇數個最後一個要秤兩次)
3(n-1)/2奇數
(3n/2)-2偶數
(2)若是2-2以上秤輕重時(不相等個數秤不考慮(沒有資訊量))
假設2-2秤
(A+B)和(C+D)秤得到B和S
則為了確定A和B以及C和D的輕重需再秤AB和CD
假設AB和CD各是BS又不能確定A(或B)是否比C(或D)大
5+1>3+2,5>1,3>2,(5>3,1<2)
若先交叉秤AC和BD
4+3>5+1,4+5>3+1...
也不能確定單一輕重(其餘各種方法也都有特殊輕重不適合)
因此需至少再測4次才一定能比出輕重(幸運的不考慮)
回歸1-1秤方法只需4次
如此一來第一次的(A+B)和(C+D)秤的資訊量可能完全浪費
同理3-3以上的秤法的資訊量可能完全浪費
所以2-2以上的秤法在最差的情況下資訊量皆為浪費
以絕對可以得到資訊量的方法就只有1-1秤
|
