2008 (4)
假如我们能够使用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个球中的一个坏球并告之轻重。
这复杂了点。一看头就疼,把俺这文科生吓坏了!先顶着数学家!