D、三组小球,数量分别是x (3^n-1)/2,y (3^n-1)/2,s (3^(n-1))
其中,最后一组(s)我称为辅助小球,数量要求大于(3^(n-1)),里面的小球必须确定是标准的。而且还要确定的是x组一定比y组重(实际上知道两者轻重关系即可,但是确定了轻重关系,下面好描述)。
在这样的情况下,n次可以找出那个坏球
方法是:
x中取(3^(n-1))个球给y,y取下(3^(n-1)),将s加到x上。再次比较。
1、如果x仍旧重,那么坏球在x和y中未移动位置的小球里,
(3^n-1)/2 - (3^(n-1)) = (3^(n-1)-1)/2
可见,这是一个递归的问题。
由于辅助球足够,x重于y,还是D类问题。
2、如果天平平衡了,说明目前天平上的小球都是好的,所以从y移出的(3^(n-1))个小球里有坏球,而且这个坏球是偏轻的。
问题转化成为:(3^(n-1))小球里有一个偏轻的球,按照C类问题,在n-1次里是可以解决的。
3、如果天平变成y重了,说明从x移动到y的(3^(n-1))小球里有一个偏重的球,按照C类问题,在n-1次里是可以解决的。
最后,D类问题的递归结束条件,当n=1时,(3^n-1)/2 = 1,用辅助小球与其中一个比较,如x,如果平衡,y里的就是坏球,且坏球轻。如果x重,那么x里的是坏球,且坏球重。