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