Question

有12个球,有一个质量不一样,请用天平称3次,把那个球称出来!

Answer 1

12个球,分别编号1,2,……,11,12.
1、 1,2,3,4 对 5,6,7,8 （一）
转6 ; > 转10 （类似 转 4 ; = 转3
3、 1 对 12 （三）
坏球为12 ,重；> 坏球为12 , 轻 ；不可能=.
转999；
4、 9 对 10 （三）
坏球为9 , 轻；> 坏球为10 , 轻 ；= 坏球为11 重.
转999；
5、 9 对 10 （三）
坏球为10 , 重；> 坏球为9 , 重 ；= 坏球为 11 轻；
转999；
6、 1 , 2 , 5 对 3,4,6 （二）
转9 ；> 转 8 ；= 转 7
7、 1 对 7 （三）
< 坏球为7 , 重 ；< 坏球为8 , 重 ；= 不可能
8、 3 对 4 （三）
< 坏球为 3 ,轻 ；< 坏球为 4 , 重 ；= 坏球 5 ,重
9、 1 对 2 （三）
< 坏球为 1 ,轻 ；< 坏球为 2 , 重 ；= 坏球 6 ,重
10、 类似于6—9
999、 结束.
第一次称的三堆球：
(一)若不平衡,我们得到的信息是：
1． 坏球在天边上的两堆里；
2． 有一堆的球重,一堆轻.
大家往往会忽视第二条信息,实际上这条信息是非常重要的.若我们知道一些球的轻重
关系,我们可以用比不知道这个关系称的次数更少就得出结论.如：若告诉你坏球轻,
那么27个球只要三次就够了.
所以我们要研究一下,若我们知道一些球的轻重关系,n次最多可以称出多少个球.我们
用函数h(n)表示.
（二）若平衡,则得到的信息是：
1． 坏球在剩下的一堆中；
2． 有若干个好球可以给我们利用.
第二条信息又是大家容易忽视的.就如12个球,称第一次若平衡,我们就可以用天平上
的球作为标准球.有标准球,两次可以称称出4个球（见第一试题解答部分的2—5）；若
没有的话,就只能称出3个球.
所以我们还要研究一下,若我们有一个标准球,n次最多可以称出多少个球.我们用函数
g(n)表示.
定义一：若一个球,若知道它不可能偏重（或知道不可能偏轻）,则我们称此球为半确
定重球（或半确定轻球）；半确定重球和半确定轻球统称为半确定球.
第一题中,通过第一次称重后,若不平衡,则1,2,3,4,5,6,7,8号球都成为半确定球,
若1,2,3,4〈5,6,7,8,则1,2,3,4为半确定轻球,5,6,7,8为半确定重球.
定义二：若一个球,若知道它是好球,则我们称此球为确定好球；若知道是坏球,确定
坏球.确定好球和确定好球统称为确定球.
第一题中,通过第一次称重后,若平衡,则1,2,3,4,5,6,7,8号球都成为确定球好球.
定义三：若一个球,既不是确定球,也不是半确定球若,则我们称此球为不确定球.
第一题中,通过第一次称重后,则9,10,11,12号球都成为不确定球.
一次未称之前,所有球都是不确定球.
引理一、对于放上过天平的球,都是半确定球或是确定球
这是个显然成立的命题.
定义四：若所有球都是半确定球,那么n次可称出的球的最大个数我们用 h(n)表示.
引理二：h(n)=3^n.
证明：
用归纳法来证：
⑴对于n=1,先证3个球是可称的,再证4个是不可称的.
① 3个球可称,
若全为半确定重球,任意挑两个,若不平衡,重的就是坏重球；否则,剩下的那个就是
坏重球；
全为半确定轻球同理；
若两个半确定重球,一个半确定轻球,则称两个两半确定重球,若不平衡,重的就是确
定重球；否则,剩下的那个就是确定轻球；
若一个半确定重球,两个半确定轻球同理.
所以,3个求可称.
②四个球不可称
若是4个球,天平称一次,只能提供三条信息,由抽屉原理,必然有两个球的信息是相同
的.故一次无法保证能判断出来.
故,n=1是h(n)=3^n是成立的.
⑵设n = k时命题成立,对于n=k+1
①先证t=3^(k+1)个球是可判断的：
设t中有a个半确定重球,b个半确定轻球,t =a + b ;
由对称性,不妨设a>b (a + b是奇数,所以不可能相等)
按如下方法分为三堆：
若a>=2*(3^k),则天平两边各放3^k个半确定重球.若不平衡,坏球在重的那堆中；平衡
的话,坏球在剩下的那堆中.这时剩3^k个球,k次可判断出来,共k+1次,成立.
若a