个人资料
正文

趣味数学(五)再论称球

(2013-03-21 13:33:19) 下一个

假如我们能够使用k次天平找出n个球中的一个坏球并告之轻重,并且没有一个球在k次称法中总在同一个盘中,如何在这个基础上用k+1次天平找出更多的球中的一个坏球并告知轻重?

我们说,用k+1次天平,能找出3n+3个球中的一个坏球,作法如下。

将3n+3个球依次标号为a_1,a_2,...,a_n;b_1,b_2,...,b_n;c_1,c_2,...,c_n;d_1,d_2,d_3。

假设对标号为1,2,...,n的n个球,k次称法分别为W_1,W_2,...,W_k。

现在我们用如下称法:在每次称法中,a_i,b_i,c_i放在i对应的盘中。在这k次称法中,d_1总放在左盘,d_2总放在右盘。在接下来的一次称法W中,d_2和所有的b球放在左盘,d_3和所有的c球放在右盘,d_1和所有的a球不在盘中。请注意,在这(k+1)次称法中,依然没有一个球总在同一个盘中。

我们说,按这样的称法,就能找出3n+3个球中的一个坏球。为什么?理由如下。

如果在前k次称法中,每次结果都一样,那就表示坏球必在d_1,d_2,d_3中;在下一次称法中就能进一步确定坏球和轻重了。

如果坏球不在d_1,d_2,d_3中,在前k次称法,能找到坏球x,那就表示我们的坏球必在a_x,b_x,c_x之中,接下去的称法必能进一步确定哪一个是坏球和轻重。

接下来让我们看一个简单问题:如何使用2次天平找出3个球中的坏球?这个就容易了。第一次,左盘放1号球,右盘放2号球,3号球放一边;第二次,左盘放2号球,右盘放3号球,1号球放一边。这样很容易找出坏球并告知轻重。

这样,使用3次天平找出个12球中的坏球也就不难了。具体称法如下:

  左盘                                右盘
-------------------             ---------------------
a_1,b_1,c_1,d_1               a_2,b_2,c_2,d_2
a_2,b_2,c_2,d_1               a_3,b_3,c_3,d_2
b_1,b_2,b_3,d_2               c_1,c_2,c_3,d_3

知道数学归纳法的朋友,不难把这个结果推广为:使用k次天平,能够找出(3^k-3)/2个球中的一个坏球并告之轻重。

[ 打印 ]
阅读 ()评论 (2)
评论
朝霞满天 回复 悄悄话 谢碧蓝天留言。我得慢慢改,尽量使它通俗易懂。
碧蓝天 回复 悄悄话
这复杂了点。一看头就疼,把俺这文科生吓坏了!先顶着数学家!
登录后才可评论.