天平秤假球 - 拼圖

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

--