Re: [問題] 天平秤假球

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者ars1an (小曹)時間18年前 (2007/11/21 11:20)推噓8(8推 0噓 2→)

留言10則, 3人參與討論串2/4 (看更多)

※ 引述《vinnce (.. )》之銘言： : 相信大家應該都知道如何用天平秤三次秤12個球(這題如果沒玩過,可以試者玩看看) : (其中一球異常,但不知較輕還是較重) : 那如果今天可以給你秤四次,請問你最多可以秤幾個球?以及你的想法如何? : (其中一球異常,但不知較輕還是較重) : 那如果今天可以給你秤五次,請問你最多可以秤幾個球?以及你的想法如何? : (其中一球異常,但不知較輕還是較重) 我把公式推導到秤n次了，秤n次最多可以秤(3^n - 1)/2個球，所以三次可以秤13個，四次可以秤40個，五次可以秤121個我試著把我的想法寫出來，請各位指教 :) Claims: (C1) (3^n - 1)/2個球之中有一假球，不知假球輕重，秤n次可找出假球 (C2) (3^n + 1)/2個球之中有一假球，不知假球輕重，另外給一真球，秤n次可找出假球 (C3) 有兩堆球各有(3^n + 1)/2個球，這全部裡面有一假球，其中一堆有一個已知是真球，已知一堆比另一堆重另外給3^(n-1)個真球，秤n次可找出假球 (C4) 3^n個球之中有一假球，已知較輕或較重，秤n次可找出假球證明：(數學歸納法) ***************************************************************** 令n=1， (1_1) 1個球之中有一假球，很明顯那就是假球 (1_2) 2個球之中有一假球，拿其中一個和真球秤即可 (1_3)(a) 已知A1+A2 > B1+T，T為真球秤A1和A2：A1>A2則A1為較重假球；A1<A2則A2為較輕假球； A1=A2則B1為較輕假球 (b) 已知A1+A2 < B1+T，同理證之 (1_4) 拿任兩個對秤即可 ***************************************************************** 假設當n=k時，Claims(C1)~(C4)皆成立，換言之 (k_1) (3^k - 1)/2個球之中有一假球，不知假球輕重，秤k次可找出假球 (k_2) (3^k + 1)/2個球之中有一假球，不知假球輕重，另外給一真球，秤k次可找出假球 (k_3) 有兩堆球各有(3^k + 1)/2個球，這全部裡面有一假球，其中一堆有一個已知是真球，已知一堆比另一堆重另外給3^(k-1)個真球，秤k次可找出假球 (k_4) 3^k個球之中有一假球，已知較輕或較重，秤k次可找出假球 ***************************************************************** 推導n=k+1之狀況： (k+1_1) (3^(k+1) - 1)/2個球之中有一假球，不知假球輕重，秤k+1次可找出假球做法:將球分成(3^k - 1)/2、(3^k - 1)/2、(3^k + 1)/2三堆，秤前兩堆 case 1:重量不同，則知道第三堆皆真球，在前兩堆各加一顆真球後，進行(k3) case 2:重量相同，則進行(k2) (k+1_2) (3^(k+1) + 1)/2個球之中有一假球，不知假球輕重，另外給一真球，秤k次可找出假球做法:將球分成(3^k + 1)/2、(3^k - 1)/2、(3^k + 1)/2三堆，在第二堆加入真球後，秤前兩堆 case 1:重量不同，則知道第三堆皆真球，進行(k3) case 2:重量相同，則進行(k2) (k+1_3) 有兩堆球各有(3^(k+1) + 1)/2個球，這全部裡面有一假球，其中一堆有一個已知是真球，已知一堆比另一堆重另外給3^k個真球，秤k+1次可找出假球做法:假設已知真球在第一堆，稱為A；另一堆為B；且令A>B (反之同理可證) 在A之中取3^k個球(不含已知真球)，在B之中取(3^k + 1)/2個球，合為X A剩下的球，再加上3^k個真球，合為Y，秤X與Y case 1:X>Y，則知道X裡面原先為A的3^k個球之中有較重假球，進行(k4) case 2:X<Y，則知道A裡的(3^k + 1)/2個球(含一真球)>B的(3^k + 1)/2個球且知其餘為真球，進行(k3) case 3:X=Y，則知道B剩下的3^k個球之中有較輕假球，進行(k4) (k+1_4) 分成三堆各3^k個球，秤其中兩堆，之後進行(k4) ***************************************************************** 得證Claims C1~C4對於任何正整數n皆成立 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 128.61.82.163 ※ 編輯: ars1an 來自: 128.61.82.163 (11/21 11:22) ※ 編輯: ars1an 來自: 128.61.82.163 (11/21 11:25) ※ 編輯: ars1an 來自: 128.61.82.163 (11/21 11:29)