Re: [問題] 天平秤假球

[ars1an (小曹)]

※ 引述《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)
推 vinnce:請問一下三次怎麼秤13個球@@?
推 vinnce:1_1,1_2  可以知道哪個是假球 卻不能知道較重還是較輕
推 puzzlez:無妨，只要減去一，那個數量就是既能找假又知輕重的大小了
推 puzzlez:所以是有 [3^(n-1)] / 2 球，稱n次可找出又知輕重
推 puzzlez:啊，好像打錯了^^" 是(3^n - 3) / 2 , 剛錯得離譜^^"
推 puzzlez:其實vinnce之前並沒說要得知假球輕重，所以原po是ok的
推 vinnce:我大概了解意思了 推這篇歸納法 我自己是用實際演練歸納法
→ vinnce:去類推 推出來與答案不同 我現在知道自己錯在哪了
→ vinnce:我沒有把有外援和沒有外援的正常球情形不同考慮進去
推 ars1an:推p板主，減1之後可以改成能得知假球輕重的版本 :)