作者ars1an (小曹)
看板puzzle
标题Re: [问题] 天平秤假球
时间Wed Nov 21 11:20:36 2007
※ 引述《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)
1F：推 vinnce:请问一下三次怎麽秤13个球@@? 11/21 11:49
2F：推 vinnce:1_1,1_2 可以知道哪个是假球 却不能知道较重还是较轻 11/21 12:06
3F：推 puzzlez:无妨，只要减去一，那个数量就是既能找假又知轻重的大小了 11/21 12:15
4F：推 puzzlez:所以是有 [3^(n-1)] / 2 球，称n次可找出又知轻重 11/21 12:16
5F：推 puzzlez:啊，好像打错了^^" 是(3^n - 3) / 2 , 刚错得离谱^^" 11/21 12:20
6F：推 puzzlez:其实vinnce之前并没说要得知假球轻重，所以原po是ok的 11/21 12:23
7F：推 vinnce:我大概了解意思了 推这篇归纳法 我自己是用实际演练归纳法 11/21 13:00
8F：→ vinnce:去类推 推出来与答案不同 我现在知道自己错在哪了 11/21 13:01
9F：→ vinnce:我没有把有外援和没有外援的正常球情形不同考虑进去 11/21 13:02
10F：推 ars1an:推p板主，减1之後可以改成能得知假球轻重的版本 :) 11/21 23:02