称12球新法 直观 实用

老顾

称球问题是趣味数学中较有名的问题.

乌木转来的问题其实是称球问题中的基础

问题,我看了原文,表诉过于冗长,----

其实称球问题中有许多题是很难的,比如:

我们知道40个球中有1个坏球,最少称4次.

如果有2个坏球,3个坏球,分别最少称几次.

最著名的是N个不等量球的问题,

----

当然这些问题的难度都超出了本论坛讨论范畴.

乌木

是的，Z.Yu的原文表述有点冗长，故我未贴出。

您说看了原文，是否您认识Z.Yu先生而且他给您看过？

当然，也可能Z.Yu的文章参考了您说的那原文。

老顾

我是根据9搂提供的网址进去看的。记得不是Z.YU，而是SBH。

12球或13球问题，其实最多只须300个字节便可证明。

中山狼

http://www.oursci.org/magazine/200109/010918-1.htm

whitetiger

看了三思网上的文章和这个论坛的讨论文章，提一些自己的想法（其实也是以前的老师教的，自己发展了一下），不必要弄得这么复杂！

如果知道坏球的轻重，那么“三分法”就OK了，没什么可讨论的。

如果不知道坏球的轻重，要找出球，并且知道坏球是轻了还是重了，那么N次最多能称(3^N-3)/2个小球。其中，“x^y”表示x的y次方。（有些文章没有注明这个红色的条件，所以有“三次称13个球”的问题。）

自己在证明的时候，还发现：如果标准球足够的话，那么N次最多能称(3^N-1)/2个小球。也就是比上面的数字多了1，而且达到了极限！（因为没有实际地把证明写下来，而且用的是构造法，所以至少需要的标准球数量还不确切，估计是只要有1个标准球就可以了。）

整个问题可以归结成“信息论”的问题。

称1次，有3种情况；称N次，有3^N种情况；

M个小球，每个小球都可能轻了或者重了，所以有2M种情况；

要得到最终的结果，必须：3^N > 2M

M最多为(3^N-1)/2（记为M*）。考虑到M是整数，这就是理论上的极限情况。

但第一次如果没有标准球的话，没办法很均匀地分配各种情况。

但是对于M*-1个球，正好是3的倍数。均匀分成三组，取两组上天平称。第一次称的三种结果，每种结果都对应了(3^(N-1)-1)/2种情况，而且有了足够多的标准球。之后的问题就解决了。

至于有多少种称的方法，个人认为没有太多的研究必要，怎么称都要遵循“均匀分配各种情况”这个关键，而且变化余地不大。

阵雨

查表法是“三进制编码法”的变种，有实用性。但我觉得它掩盖了趣味性。“三进制编码法”最有意思的特色是直接由“称量码”来指认“球码”。现再介绍这种方法。推导和证明的篇幅较长，这里从略，有兴趣者可提出探讨。

[此贴子已经被作者于2006-11-6 18:28:49编辑过]

乌木

上面说：“……改变了编码方法，称量的取球规则和最后找坏球的位码转换法则也将有改变。”

那么，10楼的“称12球的又一种分组法”大概就是这种“改变”之一吧？

[此贴子已经被作者于2006-11-7 9:57:21编辑过]

宇枫 幽蓝

这道题，我以前看过，没有一点办法，今天见到高见了，顶~~~~~~~~~~~~~`

xiao01wei

顶啊，这个问题我考虑了好半天啊。。谢谢解答。。

hqjer

很好很强大，可是有没有解题过程？