39楼宏哥
(......)
发表于 2007-10-18 11:58
只看此人
我在网上找到了称球系列问题的解法，恐怖啊。
摘录如下：
称球问题的解法
qzongci
称球问题是一类饶有趣味的数学问题,历来引起人们的兴趣,讨论也很多.其中12个球的问题是最为经典的.而实际上,12个球的问题早已研究透彻.下面用信息和熵的概念讨论这个问题并给出一种简单易行的分析方法。
为了引入概念，我们先考虑这样一个简单的问题：有10只球，从中任意取1只，要求 猜测 其颜色，（1）已知10球颜色是5白5黑；（2）已知10球是2白8黑；（3）已知10球是9白1黑；（4）已知10球全是白的。
第一种情况最难猜，因为白黑数量相等，无论猜哪一种颜色都只有50% 的把握。第二种情况好一些，猜是黑色可有80% 的胜算。第三种情况最好猜，任何一个人大约都会猜是白球，这差不多总是对的，因为有90% 的概率。至于第四种情况，没有不确定性。我们说第一种情况球的颜色的不确定性最大。如果获得了足够的信息，可以确定其结果，就消除了不确定性，或者说不确定性是0。称不确定性为熵。因此熵是可以度量的，而且熵的度量与信息的度量是一致的。
设事件A 发生的概率是 P(A)，如果此事件已经发生，称获得了I=-log(P(A))=log(1/P(A)) 的信息量，这里对数可以以任何大于0不等于1的实数为底。为例便于计算，下面取自然对数，即以e 为底。
如果一个试验A有若干个不同的结果A1,A2,...,An ,其发生概率分别是 P(Ai) ，则其平均信息量是 ∑P(Ai)I(Ai)=∑P(Ai)(-ln(Ai))=∑P(Ai)(ln(1/Ai)) ， 称之为熵，记做H(A) 。
前面的题目中，熵分别是：
（1）H=0.5×ln2+0.5×ln2=ln2=0.69315
（2）H=0.2×ln5+0.8×ln1.25=0.50040
（3）H=0.9×ln1.11111+0.1×ln10=0.32508
（4）H=1×ln12=0
这如果所获得有用信息的信息量小于熵的数量，问题就不可能得到解决。如果所获得的信息量不小于熵，则问题 有可能 得到解决。
下面简单分析两个称球问题。
问题1 有12只球,编号1--12,它们外形相同,除其中1只略轻(称作坏球)外,其余重量相等.要求用一架天平称量3次,找出这只坏球.
一开始，12个球都有相等的可能，故熵 h0=12×(ln12)12=ln12=2.48491 。
如果有个数相等的三组球，其中仅有1只稍轻，用天平称一次，可以由三组确定哪一组含有轻球，故称一次得到的信息是I=ln3 。 三次得到的信息量是 3×ln3=ln27>ln12 。故问题有可能解决。实际上这个问题是能够解决的,具体解法较多，例如下面表示的解法。
第一次称量
第二次称量
第三次称量
结论 : 坏球为
1,2,3,4<5,6,7,8
1,2<3,4
1<2
1
1>2
2
1,2>3,4
3<4
3
3>4
4
1,2,3,4>5,6,7,8
5,6<7,8
5<6
5
5>6
6
5,6>7,8
7<8
7
7>8
8
1,2,3,4=5,6,7,8
9,10<11,12
9<10
9
9>10
10
9,10>11,12
11<12
11
11>12
12
我们不难发现，如果球的个数达到27，也可以类似解决。
问题2 有12只球,编号1--12,它们外形相同,其中有11只重量相等,另外1只重量略有不同(称作坏球),但不知这只球是偏轻还是偏重.要求用一架天平称量3次,找出这只坏球,并判定它是偏轻还是偏重。
一开始，有24种可能：1号偏轻，2号偏重，2号偏轻，2号偏重，等。故熵 H0=ln24 。如下表，以0表示不可能，1表示确定，空表示未知。
1 2 3 4 5 6 7 8 9 10 11 12
偏轻
偏重
每称量一次，获得 ln3 的信息，三次获得 3ln3=ln27 的信息，ln27>ln24 ，故问题可能得到解决。
第一次称量，三个球一组，例如1234在左边，5678在右边，结果有三种可能。假设1234>5678（表示左边重于右边，以下类似），如下表。
1 2 3 4 5 6 7 8 9 10 11 12
偏轻 0 0 0 0 0 0 0 0
偏重 0 0 0 0 0 0 0 0
其中不确定的还有8种可能，H1=ln8 。第一次称量获得ln3 的信息，但真正起作用的稍小于ln3 。
注意第二次称量至少要排除5种可能。因为如果剩下仍有4种可能，熵为ln4>ln3 ，那么最后一次就不可能得出结果。
如果 取12在左边，34在右边，当结果是12>34 时，得到下表。
1 2 3 4 5 6 7 8 9 10 11 12
偏轻 0 0 0 0 0 0 0 0 0 0 0 0
偏重 0 0 0 0 0 0 0 0 0 0
剩下只有两种可能，再一次称量就可以得出结果。但如果12=34，如下表：
1 2 3 4 5 6 7 8 9 10 11 12
偏轻 0 0 0 0 0 0 0 0
偏重 0 0 0 0 0 0 0 0 0 0 0 0
还有4种可能，由于ln4>ln3 ，已经不可能成功了。 因此第二次比较12与34是不行的。
实际上，由第一次还可以知道，9－12都是好球。下面的称量应当利用这个信息。为此，必须采用“好球坏球混合”的方法，即把可能轻的、可能重的、好球混合起来称量，以获得更多的信息。例如，156左边，289右边，其中9号已经知道肯定是好球。于是比较156与289。以下又有三种情况：
如果156>289，可得到下表。
1 2 3 4 5 6 7 8 9 10 11 12
偏轻 0 0 0 0 0 0 0 0 0 0 0
偏重 0 0 0 0 0 0 0 0 0 0 0
只剩下两个可能，要么1偏重，要么8偏轻，再来一次当然可以解决。例如比较1和2，不可能出现1<2，如果1=2，说明8号偏轻；如果1>2 说明1号偏重。
如果156<289，可得到下表。
1 2 3 4 5 6 7 8 9 10 11 12
偏轻 0 0 0 0 ? ? 0 0 0 0 0 0
偏重 0 ? 0 0 0 0 0 0 0 0 0 0
只剩下三个可能：2偏重，5偏轻，6偏轻。第三次比较5，6。如果5<6 说明5号偏轻；5>6 说明6号偏轻；5=6 说明2号偏重。
如果156=289，可得到下表。
1 2 3 4 5 6 7 8 9 10 11 12
偏轻 0 0 0 0 0 0 ? 0 0 0 0 0
偏重 0 ? ? ? 0 0 0 0 0 0 0 0
剩下也是三个可能：2偏重，3偏重，7偏轻。第三次比较2，3。如果2<3 说明3号偏重；2>3 说明2号偏重；2=3 说明7号偏轻。
第一次称量如果得到1234<5678 ,或1234=5678，可类似分析。
总之要做到第一次称量后的可能结果数要<=9;第二次称量后可能结果数要<=3。
从这个例子可以看出，尽管这个问题可以得到解决，但称量的方法不对，仍然解决不了。必须正确安排，使得每次称量得到尽可能多的信息才行。
对各种情况的分析，总结成为下表。
第一次称量
第二次称量
第三次称量
结论 : 坏球为
1,2,3,4<5,6,7,8
1,5,6<2,8,9
1<9
1 轻
1=9 8 重
1,5,6=2,8,9
3<4
3 轻
3=4
7 重
3>4
4 轻
1,5,6>2,8,9
5<6
6 重
5=6
2 轻
5>6
5 重
1,2,3,4=5,6,7,8
9,10<5,11
9<10
9 轻
9=10
11 重
9>10
10 轻
9,10=5,11
1<12
12 重
1>12
12 轻
9,10>5,11
9<10
10重
9=10
11 轻
9>10
9 重
1,2,3,4>5,6,7,8
1,5,6<2,8,9
5<6
5 轻
5=6
2 重
5>6
6 轻
1,5,6=2,8,9
3<4
4 重
3=4
7 轻
3>4
3 重
1,5,6>2,8,9
1=2
8 轻
1>2
1 重
引申一下，如果是13个球， 其中有12只重量相等,另外1只重量略有不同,但不知这只球是偏轻还是偏重.还能否用一架天平称量3次,找出这只坏球,并判定它是偏轻还是偏重
注意这里一开始有26种可能，熵H0=ln26<ln27，似乎可以。但实际上，假设第一次称量比较1234与5678，如果二者不等，同上面可以解决。如果二者相等，则剩下5个球计10种可能，ln10>ln9=2ln3，后面两步无论如何得不到ln10 的信息，故不论怎样安排，都无法解决。因此，一开始信息量的分析似乎可以解决，但如果无法安排好，即有的称量，总是获得一些重复的信息，那问题就是不可解的。.
