There are 8 balls. Four of them weigh X grams each, and the other four weigh Y grams each. Your task is to find two balls having different weights. You have a balance scale with two pans on which you can compare the weight of any number of balls. What is the minimum number of weighings necessary to guarantee to accomplish this task?
不負責任解題:
題目有點小吊詭, 它不是要你用最少次數『分出哪四個球輕, 哪四個球重』, 而是『找出輕重不同的兩顆球』。
因為可以秤任意數量的球, 又有組合性, 運氣好當然可能第一次秤, 天平兩端各一顆正好輕重不同, 就結束了。但顯然題目希望我們是要能百分之百確定, 而不是期待靠運氣。
通常思路停滯時, 我會倒過來想, 那最糟的情況要到幾次？如果我每次都一個一個對秤, 然後永遠都靠著我過往中大樂透的機會, 那麼我會到第4次才能找到輕重不同的兩球
(每次都秤到相同重量, 然後把一顆可能性去除, 剔除掉3顆後, 第4顆才會和天平另一端輕重不同)
這顯然是個蠢方法
--
如果八顆球分別是ABCDEFGH, 那我如果先拿AB對秤
運氣好AB不同重量就結束 – 1次
AB同樣重量, 就再秤CD, 若CD 不同重量就結束 – 2次
要是AB等重, CD 也等重, 那就秤AB v.s. CD
若AB和CD 不同重, 就挑AB 任一顆和CD任一顆, 一定不同重
若AB 和CD 等重, 就代表ABCD四球一樣重, 也就是 ABCD, EFGH 正好是輕重不同的兩組球, 所以兩組各拿一顆, 一定不同重
3次
如此可以在3次內KO
--
再換個方法
我先拿ABC 和 DEF 對秤
如果等重, 那麼就代表兩組球的組合一定都是 2X1Y 或是 1X2Y
這時我只要再拿AB 對秤
要是重量不同 – 2次
要是重量相同, 那麼任取AB其中一球和C配一定重量不同 – 2次
反之, 若是ABC 和DEF 重量不同
有可能以下4種可能性
(3X, 1X2Y), (3X, 3Y), (2X1Y, 1X2Y), (2X1Y, 3Y) [ABC 和DEF可能為前或後之組合]
接著來秤GH,
其中若是(3X, 3Y), (2X1Y, 1X2Y)這兩種搭配, 那麼剩下的GH一定重量不同 – 2次
但若是GH 等重, 就有可能是(3X, 1X2Y), (2X1Y, 3Y) 其中一組組合,
這時挑組合中比較重的一組任選兩顆和GH對秤
若是(3X, 1X2Y), 則GH 必為2Y, 對上輕重的任選兩顆是2X, 一定較輕
若是(2X1Y, 3Y), 則GH 必為2X, 對上輕重的任選兩顆是2X或1X1Y, 一定平衡或較重
上述第一種情況, 就最後一次對秤的兩組任取一顆一定重量不同 – 3 次
上述第二種情況, 就GH 和3Y兩組任取一顆一定重量不同 – 3 次
但這種題目的思惟往往是 –
1.在你覺得已經是最少的數字還有不同的方法可以達成, 再少一次才會是答案(漂亮的答案不會有另一種可能性)
2.真正最少的答案一定是沒有帶運氣的, 就是每種判斷都應該正好兩次, 沒有一次就可靠運氣達成的。（因為每次的秤都是一次資訊, 資訊只使用一次就結束太浪費了)
我的答案當然就是3-1 = 2次
第一次是兩顆兩顆對秤(AB v.s. CD)
那.....第二次呢??
沒有留言:
張貼留言