※ 引述《vinnce (.. ￾  )》之銘言： : 相信大家應該都知道如何用天平秤三次秤12個球(這題如果沒玩過,可以試者玩看看) : (其中一球異常,但不知較輕還是較重) : 那如果今天可以給你秤四次,請問你最多可以秤幾個球?以及你的想法如何? : (其中一球異常,但不知較輕還是較重) : 那如果今天可以給你秤五次,請問你最多可以秤幾個球?以及你的想法如何? : (其中一球異常,但不知較輕還是較重) 說一點我的想法:) 假設有秤n次的機會 因為每次秤會有三種結果(左重,右重,一樣) 所以可以得到的訊息為3^n 有k個球的情況下 有2k種可能(1號較輕,1號較重,2號較輕,2號較重...etc) 因為這2k種可能要被n次, 也就是3^n決定 所以 3^n>=2k k的最大值為(3^n-1)/2 那當k=(3^n-1)/2時, 就一定可以用n次完成嘛 答案是否定的 由於我們希望在第一秤秤完後 剩下來的待處理訊息比3^(n-1)小 所以將(3^n-1)/2分成[3^(n-1)-1]/2兩堆和[3^(n-1)+1]/2 將數目相同的兩堆秤一次 如果相等的話 表示假幣在[3^(n-1)+1]/2那堆中 這樣的數目明顯不能由n-1次完成 因此k不能等於(3^n-1)/2 最大值為(3^n-3)/2 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.99.19.169