天平称球问题的推广

Categories: Uncategorized
Tags: No Tags
Comments: 1 Comment
Published on: 2012/05/13

  天平秤球这个问题的各种版本在很多年以前就流传开了,我在2010年的时候曾经总结过一个结论比较强的版本:

  假设有13个外形完全一样的球,其中12个等重,剩下一个重量和其他的球不同,既可能更轻又可能更重。
1.能否用天平称3次找出那个重量不同的球;
2.能否用天平称3次找出那个重量不同的球,并且获知那个球比其他的球更轻还是更重
能则给出方案,不能则证明


.

.

.

.

.

.

.

.

.
线
.

  第一个问题的解非常简单,答案是肯定的,网上可以搜到称量方法。

  第二个问题的答案是否定的,我们可以从信息论的角度证明这个问题:

  每次称量的结果只有可能是“天平左倾”,“天平右倾”和“平衡”三种结果,秤三次最多只可能区分27种可能,秤两次最多只可能区分9种可能,秤一次最多只可能区分3种可能。假设第一次称重的时候往天平左边放a个球,右边放a个球(如果放的球数目不等将有可能使得称重结果没有意义),余下(13-2a)个球。
a\ge 5时,如果天平不平衡,将余下2a种可能性(较轻的a个球中有一个轻球,或者较重的a个球有一个重球),2a\ge 10,也就是不可能至多再秤两次确定是哪种可能;
a\le 4时,如果天平平衡,将余下至少5个球,也就是10种可能性(至少5个球,每个球或轻或重),同样不可能至多再秤两次确定是哪种可能。
  所以,第二个问题是不可行的。

但是,如果我们能够借到一个一定是标准重量的“标准球”,那么第二个问题就是可解的了。我们还能够证明,因为3次称量最多能区分27种可能性,第二个问题可解的球数目的上限是13,

下面我们考虑这个推广版的问题:

  假设有n个外形完全一样的球,其中(n-1)个等重,剩下一个重量和其他的球不同,既可能更轻又可能更重。
1.如果能够用天平称k次找出那个重量不同的球,那么n最大是多少?
2.能否用天平称k次找出那个重量不同的球,并且获知那个球比其他的球更轻还是更重,那么n最大是多少?

可以证明,第一个问题中n=\frac{1}{2}(3^k-1),第二个问题中n=\frac{1}{2}(3^k-3)。我对此有绝妙的证明,但这篇blog篇幅有限写不下。(你以为你是费马吗啊喂!!!)

证明思路如下,依次证明引理:
引理一:
如果有m个球或者是标准或者比标准重,以及n个球或者是标准或者比标准轻以及至少1个标准球,则k次称量能够确定是哪个球的充要条件是:

m+n \le 3^k


引理二:
如果有n个球不知道是标准重量还是更轻还是更重,以及至少1个标准球,则k次称量能够确定是哪个球的充要条件是:

n \le \frac{1}{2}(3^k+1)


引理三:
如果有n个球不知道是标准重量还是更轻还是更重,以及至少1个标准球,则k次称量能够确定是哪个球,以及这个球是更轻还是更重的充要条件是:

n \le \frac{1}{2}(3^k-1)

引理一的充分性证明思路是:
令m=3i+j, n=3k+r。每边放i个可能重的,k个可能轻的,然后j,r=0,1,2总共9种可能,分类讨论一下可以递归解决。
必要性是显然的。
引理二的充分性证明思路是:
(3^k+1)/2个球,第一次(3^(k-1)+1)/2个球放左边,(3^(k-1)-1)/2个球加上标准球放右边,还余下(3^(k-1)+1)/2个第一次称量结束,要么平衡可以用递归证明,要么不平衡用引理证明。
引理三的充分性证明思路同理,区别在于余下(3^(k-1)-1)/2个球。
引理三的必要性证明思路与上面那个问题二相同
引理二的必要性证明就麻烦一些,不过思路还是类似。如果第一次称量不平衡要利用引理一,平衡的话递归。

最终两个问题的证明都需要单独讨论第一次称量,因为没有标准球可以借,并且数目比引理中少一,然后就可以利用引理的结论,通过类似的思路证明。

1 Comment - Leave a comment
  1. Xu says:

    学习了~

Leave a comment

Your email address will not be published. Required fields are marked *


Close Print