称球问题的外推
http://www.readfree.net/bbs/read-htm-tid-4516538-fpage-2.html讲述了用3进制解决称球问题，这里推广一下这个结论。首先看看把称球问题这么描述：有12个球，只有一个与其它的重量不一样，仅使用天平，请问你最少需要多少次称量才能找出这个这个球。
问题的解决办法可以直接利用3进制的方法来获得，简单的说，就是要找到一种可能的组合，能将所有的情况标识出来。这里可以看到12个球有24中状况，所以用3^3＝27（底数3表示天平称量会出现3中基本情况，具体参见上面的链接）可以解决这个问题，所以，最少的次数是3次。
利用这个基本原理，对于更多的球同样可以解决，比如13个球有26种状况，同样3次就能解决。那么14个球呢？3次显然不行了，因为27<28，所以，需要至少4次，依次类推，在14－40个球的情况，都需要4次。
这里只是把前文中的结论显式化了，对于这类问题，其根本的求解方法是：
1. 先获得基数，比如天平称量中包含 {左重,平衡，右重}三种情况，所以基数为3，同样喝酒那个例子中，包含的基本情况是对于每瓶酒 {喝，不喝}两种情况,所以基数为2。
2. 所有情况的总数。对于天平那个例子，每个球都放到天平上，因为每个球可能放到左边或者右边，所以对于每个球有两种情况。对于喝酒的例子，酒的数目是最终总数
这样，通过求对数的方法，就能找到最少需要的次数 上面的描述中有一个错误，因为不能编辑了，所以回帖修正一下：
计算总数的描述中，天平例子的总数是这样计算的：
因为题目中提到有一个异常的球，那么会存在24中情况，他们是：1号球重，1号球轻.....，一共24种可能。
另外进一步扩展的问题是： 如果找到了这种可能，如何确定具体的办法呢？喝酒的例子可以说是唯一的解法（因为2^3=8)，但12个球的时候，27>24，也就是意味着此题肯定是多解，实际的问题归结为如何找到这样的组合呢？ 再继续扩展，此题一共有多少解呢？ 其实这个问题还可以延伸出另一个关键的问题:
就是,第一次该在天平上多少球的问题 n次问题实际的解是能称至少(3^n-1) / 2个球
而第一次上天平的球实际上是有限制的
当然,喝酒问题和天平,实际上是有一些区别的.
当初很凑巧,给我出喝酒问题的人,和天平问题的人,只差了1天,才让我想到了三进制的解决方法.
后来翻翻书,其实前人早有推断.
更把这个问题扩展到一个{n,B=1,N=(3^n-1) / 2} 可解问题
其实还有以下结论:
1 {n,B<=1,N=3,4,...,(3^n-3) / 2}可解
2 {n,B<=1,N>=(3^n-1) / 2} 不可解
3 {n,B=1,N=(3^n-1) / 2} 可解
4 {n,B<=1,G=1, N=(3^n-1) / 2} 可解
5 {n,B=1,N>(3^n-1) / 2} 不可解
6 {n,B=1,G=1,N=(3^n+1) / 2} 可解
7 {n,B<=1,G任意,N>=(3^n+1) / 2}不可解
8 {n,B=1,G任意 ,N>=(3^n+3) / 2}不可解
n次数,B已知坏球个数 G已知好球个数 N球个数
具体推论可以参看我推荐的那本书.
页:
[1]