Re: [分享]秤球問題12顆球秤三次

[walkwall (會走路的牆)]

※ 引述《shoppinglin (瞎拼)》之銘言：
原文通通恕刪

沒想到這個題目的答案需要貼這麼多次，這應該是我第三次還是第四次貼在BBS上了...
因為被討論過很多次，所以下面列幾個Q&A，如有需要我再補充回答
此解不需要依賴之後測得的結果，事先就可以定好測量的方式
這題目是編碼學(coding theory)的題目，有研究興趣的同學可以估狗 Hamming code
或參考英文維基網址  http://en.wikipedia.org/wiki/Hamming_code

=======================================================================

回到問題本身
我們可以將球編碼，依序叫做A,B,....,K,L共12顆球
接下來請按照下面列表將球放在天平的左邊以及右邊
         天平左邊      天平右邊
第一次   A B C D   △   I J K L
第二次   B F I J   △   D E H L
第三次   D H I L   △   C E G K

然後依照你所秤得的字典順序，在下表查詢答案(左：左邊重  右：右邊重  △：一樣重)

左左左-> 無解 | 左左△-> B重  | 左左右-> L輕
左△左-> K輕  | 左△△-> A重  | 左△右-> C重
左右左-> D重  | 左右△-> J輕  | 左右右-> I輕
△左左-> E輕  | △左△-> F重  | △左右-> H輕
△△左-> G輕  | △△△-> 無解 | △△右-> G重
△右左-> H重  | △右△-> F輕  | △右右-> E重
右左左-> I重  | 右左△-> J重  | 右左右-> D輕
右△左-> C輕  | 右△△-> A輕  | 右△右-> K重
右右左-> L重  | 右右△-> B輕  | 右右右-> 無解

=====================================================================

以下是常見問題：

Q1.是不是能三次秤13顆球或更多球?
A1:由於三次天平都只會出現左重或一樣或右重的結果
   所以資訊量最多只有3^3=27種，因此十四顆球(含)以上就不討論了(可能大於等於28種)
   如上所見，如果第十三號球標示為M，則上述測量會測出△△△的結果
   看到△△△，能知道是M有問題，但是無法知道該球輕或重
   所有其他測量方式，如果要測十三顆球，必定會有一顆以上的球無法得知輕重
   所以前述解仍然是十三顆球的最好結果

Q2.怎麼想到的，解答後面的數學模型為何?
A2:此解參照下表生成，請自行對照領悟，不多做解釋
    A  B  C  D  E  F  G  H  I  J  K  L
    1  1  1  1  0  0  0  0 -1 -1 -1 -1
    0  1  0 -1 -1  1  0 -1  1  1  0 -1
    0  0 -1  1 -1  0 -1  1  1  0 -1  1

Q3.秤四次與秤五次可以秤多少顆球? 這問題的解可以衍生到其他解嗎?
A3:秤四次 -> 39顆球  秤五次 -> 120顆球  f(n)=3*(f(n-1)+1)
   衍生解就是做出類似A2的表格，衍生方法如下

   1  1  1  ...  1  0  0  0  ...  0 -1 -1 -1 ...  -1
   0               -1                1
   0  前一層的表格 -1  前一層的表格  1  前一層的表格

   所以看懂得人可瞭解：秤三次的表格，其實也是從秤兩次的表格 1  0 -1 衍生出來的
                                                            0 -1  1


先暫時這樣，有問題就在推文裡面問吧






--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.117.201.43
推 yungnan:前一篇是想找出第二種解法,第一篇已經有說明這種(一開始我
→ yungnan:也誤會第一篇是想問解答)
→ yungnan:不過推文裡已有說明了
→ walkwall:不一樣吧  第一篇是前兩次秤法固定  這是三次都固定
推 yungnan:恩恩 不同,是我的解法同第一篇才對
推 puzzlez:嗯嗯，不要再說可以秤15顆了....
推 bohsing:推 專業
推 MKing:以前的線代老師教得可真難.....