只用天平称3次,找出13个球中重量与其他球不同的唯一球

题目:13个有编号的球,其中12个重量相同,剩下的一个与其他球重量不同,但不知是轻了还是重了,只用天平称3次,找出这个与众不同的球
twitter上无意从别人的转推看到,开始以为很简单,深入思考后发现细分的情形还是不少的。其实它是一条扫雷题。或许某些招聘也会拿来当面试题

如果知道与众不同的球(下面简称特殊球)是轻了还是重了,就变成了非常简单的题目,即使球数量是27个,都能只称3次就找出特殊球

闲得蛋疼推导出了解法

解法:
将重量都相同的球称之为标准球。
不妨假定球的编号是1,2,3,…,13

将之分成三堆,1,2,3,4为堆A,5,6,7,8为堆B,9,10,11,12,13为堆C

第一次称:
将堆A和堆B放在天平上,如果平衡(分支一),则特殊球在堆C,如果不平衡(分支二),则特殊球在堆A或堆B

分支一:
堆A和堆B的球全部都是标准球。这时候要利用上标准球的一个,不妨加入球1
将球1和球9放在天平一边,球10和球11放在天平另一边,称第二次,如果平衡(分支三),则特殊球在12,13之中,如果不平衡(分支四),则特殊球在9,10,11之中,我们要记下1,9 VS 10,11那边轻那边重

分支三:
很简单,将12和标准球放在天平两边称第三次,平衡则特殊球是13(已经找出但仍然不知道轻了还是重了),不平衡则特殊球是12,并且还能知道轻了还是重了

分支四:
将10和11放在天平两边称第三次,
如果平衡,则特殊球是9,因此10,11都是标准球,依据第二次的结果,还能知道9重了还是轻了
如果不平衡,则特殊球在10,11当中。在第二次的结果中,如果10,11这边重了,说明特殊球是重了,则特殊球是第三次的较重者;如果第二次10,11这边轻了,说明特殊球是轻了,则特殊球是第三次的较轻者

回到分支二
分支二:
回顾一下:特殊球要么在堆A中,要么在堆B中
如果堆A在第一次测量中较轻,分支五
如果堆B在第一次测量中较轻,分支六
分支五和分支六的后续解法是对称的,我们只需要解决分支五即可

分支五:堆A(1,2,3,4)较轻,堆B(5,6,7,8)较重,这个结果很重要,后面的推理要利用到
将1,5,6放在天平一边,2,7,8放在天平另一边,称第二次
如果天平平衡,则1,2,5,6,7,8都是标准球,特殊球在3,4当中,拿标准球的任一个和3称第三次,如果平衡则特殊球是4,如果不平衡,则特殊球是3
如果1,5,6较轻,2,7,8较重,分支七
如果1,5,6较重,2,7,8较轻,分支八

分支七:
我们要筛选出特殊球的备选球,第二次测量的结果也要利用,1,5,6较轻,2,7,8较重
1,7,8都是特殊球的备选,2,5,6都不可能是备选。因为2或5或6如果是特殊球,代入去都能导致矛盾
这种推理过程跟扫雷是一样的
然后将7,8放在天平两边称第三次,如果平衡,则特殊球是1,如果不平衡,则特殊球是较重的那个

分支八(和分支七的推理逻辑是一样的):
第二次测量结果已知是1,5,6较重,2,7,8较轻
可以筛选出2,5,6是特殊球的备选。1,7,8都不可能是。
将5,6放在天平两边称第三次,如果平衡,则特殊球是2,如果不平衡,则特殊球是较重的那个

OVER。

2012年7月5日 | 归档于 私语
  1. 2012年7月14日 08:34 | #1

    刚刚看过朋友写的的关于12个球中称重找出不同者的解答,现在在这里看到了13球问题解答,今天也是收获满载呢(*^-^)

  2. 蓬莱山空
    2012年7月5日 02:41 | #2

    回想起了奥数噩梦啊啊啊啊o(≧口≦)o

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
:wink: :-| :-x :twisted: :) 8-O :( :roll: :-P :oops: :-o :mrgreen: :lol: :idea: :-D :evil: :cry: 8) :arrow: :-? :?: :!: