IQrace 版 (精华区)

发信人: ciel (二分之根号五减一℃·冬天来啦), 信区: IQrace
标  题: 称小球问题终结----结语
发信站: 哈工大紫丁香 (2003年10月25日14:39:06 星期六), 站内信件

关于称球问题以及几种变形(要求判明轻重或另有标准球)，主要的思想就是用数学归纳法
。有一种办法是先证明以下两个引理：

 1) k 次称量，能且最多能在 3^k 个有偏轻偏重标记的球中找出坏球
    (当然找出坏球后，自然知道是偏轻还是偏重)
    (其中偏轻偏重的球各占一半，当然一种比另一种多一个)
    (所谓偏轻的球是指此球参与称量时，其所在的一端总是轻的一端，
     偏重的类似理解)
 2) 若至少有 3^(k-1) 个标准球，则 k 次称量能且最多能在 (3^k-1)/2
    个球中找出坏球
 利用数学归纳法可以证明上述两个引理。
 再利用这两个引理和数学归纳法即可证明4个称球问题。

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.228.216]