问题描述:
有13个球和一个没有刻度的天平,已知13个球中有一个球重量和其他12个球不一样,当然
另外12个球等重.而且这13个球的外观一模一样,不能从外观上分辨.要求称最少的次数,
将这个重量不同的球找出来
Darkness:其实就这些东西要解答的话是很考记忆力的,如果你需要的话,可以找一支笔
在球上做标记哦..
解答如下:
{H=Heavy Ball L=Light Ball O=Unknown Information S=Standard Ball}
将13球分成 4个 4个 5个 3组.将两组4个球称1次 则
1> 若不平衡,则目标球必在两组4个球中 HHHH--LLLL OOOOO _F(8,2)
2> 若平衡,则目标球必在5个1组中 SSSSSSSS OOOOO _F(5,2)
<1 将重球(沉下天平一边的球)组4个球编为H 轻球组4个球编为L. 另5个球编为标准球S
1.2> 从4个重球中随机选2个H 轻球中选一个L 标准球中选一个S 编为一组 HHLS
从剩下2个重球中选一个H 3个轻球中选一个L 4个标准球中选一个S 编为一组HLSS
剩下的重球轻球编为一组 HLL
<1.2 HHLS--HLSS 称第2次
1) 若左重右轻,则可能为左的HH重或右的L轻 1.2.1>
2)若右重,则可能为左的L轻或右的H重 1.2.2>
3)若平衡,则目标球在剩下的HLL三球中 1.2.3>
<1.2.1 将HHL中的H,H 拿出称第3次,其中重的即为目标球 (想想为什么)
若平衡,则L为目标球 ...解法<1.2.1>
{注:解法<1.2.1>对HLL三球问题也适用}
<1.2.2 将HL中任一个与标准球S称,平衡为另一球,不平衡为该球
<1.2.3 解法见 解法<1.2.1> 略
则F(8,2)问题讨论完毕
<2 F(5,2) 问题 OOOOO 5个球均无已知信息
2.1> 5球分为3组
取5个球中2个与一个标准球组成一组 OOS
取剩下3个球中1个与2个标准球组成一组 OSS
剩下两个球一组 OO
OOS--OSS 称一次
可能左重右轻(HHS--LSS) 2.1.1>
或可能左轻右重(LLS--HSS) 2.1.2>
或平衡(SSS-SSS) 2.1.3>
<2.1.1 即有HH及L 参考解法<1.2.1>
<2.1.2 即有LL及H 参考解法<1.2.1>
<2.1.3 将LL中任一个与标准球S称,平衡为另一球,不平衡为该球
则F(5,2)问题讨论完毕
而有F(8,2)及F(5,2)解决有F(13,3)问题解决
故最少称量次数为 3
此上即为13球问题解答过程
P.S. 该问题是由F(12,3)问题解答推广来的,虽多了一个球,不过核心
思想还是换汤不换药:把一个大的问题划分成若干个子问题,然后通过
对每个子问题的解决,得到大问题的解决.. 有点神似动归哈....
个人认为不可能再推广到F(14,3)问题,不过不会证明.敬请高人指教.