天平秤假球 - 拼圖

※ 引述《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

--