发信人: joeren()
整理人: bsese(1999-05-27 16:44:50), 站内信件
|
更普遍的结果是，若n个球中有一个是次品，那么
1。在有一个标准球的情况下，称[log3(2n)]次（[x]是高斯函数，即小于x的最小
整数）
2。没有标准球时，称[log3(2n+1)]次
1的必要性很容易，因为每个球都可能是比正品轻或重的次品，总可能性有2n种。
而天平称一次可以有3种结果，
所以称k次后共有3^k种结果。因此要知道哪个球是次品，必须3^k>2n.
而充分性也不难。使用数学归纳法就可以。这里的关键是“对分原则”。每次称
的时候，必须尽量使得导致天平每一种结果的情形数都一样（或最多差1）。如能
达到这个原则，那么就可以得到称k次以后有3^k种结果，且每种结果的情形数都
最多差一。
可以实施一个普遍的证明：假设有m个球其中可能有个比正品重，有n个球其中可
能有个比正品轻，r个球不知道具体情况，还有一个（多于一个当然行，但是可以
证明只要一个就够了）标准球。
在这种情况下，必然可以实施对分原则。由于m、n、r都是模3的，因此证明这个
问题只需要进行简单的枚举。
至于2，关键是证明当2n+1=3^k时若没有标准球，则不可能实施对分原则。例如，
4个球的情形就不可能对分（必须把8分成3、3、2才算，但是最好的情况下只能分
成4、2、2）。
其他所有问题都是其推论。
【 在 100619 (蔷薇花) 的大作中提到: 】
: 如果一堆等重乒乓球中有一个次品，不知轻或重，用无砝码的天平以最少
: 的次数称出次品。
: 如果有3个乒乓球，至少只称2次，
: 如果有12个乒乓球，至少只称3次，
: .......
--
虽说是,天涯海角,芳草碧连天,只可惜曾经沧海难为水;
怎奈那,流水落花,无情却有意,长叹息良辰美景奈何天!
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.104.200.108]
|
|