28个球中有一个次品用一个天平至少称几次
无砝码天平4次称量可以找出28个球中的仅有1坏球,并判断轻重
编号1-28,[]内为每次称量后得到的信息
1-132,2轻
。。。。。。。。。。。。。。。。1-3=4-6。[在7则轻,17-18中则重]
。 。。。。。。。。。。。。。。。。。。。。。1718,17重
。。。。。。。。。。。。。。。。1-3>4-6。[在4-6中且较轻]
。。。。。。。。。。。。。。。。。。。。。。45,5轻
。 。。。。。。1-7,15-16=8-13,27,17-18。[在14,19-26中较重]
。。。。。。。。。。。。。。。。19-2123,22重
。。。。。。。。。。。。。。。。19-21=22...全部
无砝码天平4次称量可以找出28个球中的仅有1坏球,并判断轻重
编号1-28,[]内为每次称量后得到的信息
1-132,2轻
。。。。。。。。。。。。。。。。1-3=4-6。[在7则轻,17-18中则重]
。
。。。。。。。。。。。。。。。。。。。。。1718,17重
。。。。。。。。。。。。。。。。1-3>4-6。[在4-6中且较轻]
。。。。。。。。。。。。。。。。。。。。。。45,5轻
。
。。。。。。1-7,15-16=8-13,27,17-18。[在14,19-26中较重]
。。。。。。。。。。。。。。。。19-2123,22重
。。。。。。。。。。。。。。。。19-21=22-24。
[在14,25,26中较重]
。。。。。。。。。。。。。。。。。。。。。。2526,25重
。。。。。。。。。。。。。。。。19-21>22-24。[在19-21中且较重]
。。。。。。
。。。。。。。。。。。。。。。。1920,19重
。。。。。。。1-7,15-16>8-13,27,17-18。[在8-13较轻,15-16较重]
。。。。。。。。。。。。。。。。8-109,9轻
。
。。。。。。。。。。。。。。。8-10=11-13。[15-16中且重]
。。。。。。。。。。。。。。。。。。。。。。1516,15重
。。。。。。。。。。。。。。。。8-10>11-13。
[在11-13中且较轻]
。。。。。。。。。。。。。。。。。。。。。。1112,12轻
1-13=14-26。[在27-28中]
(只剩下2个,略过)
最多这组也可容纳13个球,所以4次可以解决39球问题,甚至40球,多的一个放在一边,当其余39球均判断为标准时可知第40球为坏球,但不能判断其轻重
1-13>14-26。
[在1-26中,27-28标准]
。。。。。。。1-7,15-1612,11重
。。。。。。。。。。。。。。。。8-10=11-13。[15-16中且较轻]
。。。。。。。。。。。。。。
。。。。。。。。1516,16轻
。。。。。。。。。。。。。。。。8-10>11-13。[在8-10中且较重]
。。。。。。。。。。。。。。。。。。。。。。89,8重
。。。。。。。1-7,15-16=8-13,27,17-18。
[在14,19-26中较轻]
。。。。。。。。。。。。。。。。19-2120,20轻
。。。。。。。。。。。。。。。。19-21=22-24。[在14,25,26中较轻]
。。。。。。。
。。。。。。。。。。。。。。。2526,26轻
。。。。。。。。。。。。。。。。19-21>22-24。[在22-24中且较轻]
。。。。。。。。。。。。。。。。。。。。。。2223,23轻
。
。。。。。。1-7,15-16>8-13,27,17-18。[在1-7较重,17-18较轻]
。。。。。。。。。。。。。。。。1-35,4重
。。。。。。。。。。。。。。。。1-3=4-6。
[在7则重,17-18中则轻]
。。。。。。。。。。。。。。。。。。。。。。1718,18轻
。。。。。。。。。。。。。。。。1-3>4-6。[在1-3中且较重]
。。。。。。。。。。。
。。。。。。。。。。。
12,1重
以上说明4次可以解决问题
每次称量最多得到3个结论:左重,平,右重
n次称量,最多有3^n个结论
k个球(k>=3)要找出其中仅有的1个坏球,
在不知道轻重的情况下,每个球都有可能是坏球,或轻或重,
一共有2k种可能,所以必须满足:3^n>=2k,
n>=log(3)[2k]
k=28,n>=4
所以至少4次
另外3^n个结论中总有2个【不可能】结论,以及一个全平的结论
如果称量的球中有坏球,那么全平(都是好球)也【不可能】
有效结论只能有3^n-3个,所能容纳的球数k=(3^n-3)/2个
即n次称量最多能判断(3^n-3)/2个球
全平作为有效结论,则可以判断额外有1个是坏球,但无法知道坏球的轻重,所以只需找出坏球,球数可以是(3^n-3)/2+1=(3^n-1)/2个。收起