很有意思的一个问题,开始思考这道题目,总是两个入手,一个是分类,怎么样第一步就把不同的那个球尽量限制到数量少的堆里.然后再处理，然而思路总是被无法处理大小而无法识别,呵呵，直到后来看到答案,呵呵，又一次确认自己不属于聪明人一类~~~~.
这里从南大小百合找来一些帖子回在这儿,更多的大家查看清华或者复旦bbs.
其拓展问题是:
0. N 个球，其中有一个坏球比别的球重，
问用无砝码天平最多称几次可将坏球找出来
(典型例子：27个球最多称3次)
1. N 个球，其中有一个坏球与别的球重量不同，
问用无砝码天平最多称几次可将坏球找出来
(典型例子：13个球最多称3次)
2. N 个球，其中有一个坏球与别的球重量不同，
问用无砝码天平最多称几次可将坏球找出来，并知其偏轻还是偏重
(典型例子：12个球最多称3次)
3. N 个球，其中有一个坏球与别的球重量不同，另有一个标准球，
问用无砝码天平最多称几次可将坏球找出来
(典型例子：14个球最多称3次)
4. N 个球，其中有一个坏球与别的球重量不同，另有一个标准球，
问用无砝码天平最多称几次可将坏球找出来，并知其偏轻还是偏重
(典型例子：13个球最多称3次)
下面将给出称球问题次数的答案，并提出一个扩展问题供大家讨论。
　
[说明]
称球问题长期以来都是各大BBS的一个经久不衰的题目，相信许多
网友都已知道了它的答案，所以下面仅给出各题的称球次数公式，
至于详细步骤，大家可以可去清华，木棉，南开等 bbs 站查到详细解答，此处就从略了。
　
[答案]
各题至多所需称球次数依次为：
0. ceiling(log3(N))
1. ceiling(log3(2*N+1))
2. ceiling(log3(2*N+3))
3. ceiling(log3(2*N-1))
4. ceiling(log3(2*N+1))
其中 ceiling 表示上取整，log3表示取以3为底的对数
　
[扩展分析]
下面我想提出一个称球问题的扩展来供大家讨论。
以上5个称球问题的传统解，其各次称法一般是相关的，即第2次
称哪些球一般要依赖于第1次的称球结果，而第3次所称的球又要
依赖于前2次的称球结果，等等。
　
[加强条件]
我们可以考虑对称球方案加强一个条件，要求各次称量必须相互独立，
即必须在第1次称量前就排出各次称量方案，而不能在称量进行
后动态指定。不妨将这个条件称为“独立性条件”。
　
[新的问题]
于是，给以上5个问题分别加上独立性条件的约束，就形成了5个新
的问题：0' 1' 2' 3' 4' ，现在要问各题至少所需称球的次数与
称法是什么?
　
以问题2为例，新的问题是(其余类推):
2' N 个球，其中有一个坏球与别的球重量不同，
如果要求第1次称量前就排出各次称量方案来，
问用无砝码天平最多称几次可将坏球找出来，并知其偏轻还是偏重
[例子]
以 2' 问题为例，3个球时，可找到称两次的独立方案：
设三个球为ABC，第1次称A和B，第2次称A和C，下面是称量结果分析表：
┏━━┯━━━┯━━━┯━━━┓
┃ │AB ┃
┠──┼───┼───┼───┨
┃A
┠──┼───┼───┼───┨
┃A=C │ B重 │不可能│ B轻 ┃
┠──┼───┼───┼───┨
┃A>C │不可能│ C轻 │ A重 ┃
┗━━┷━━━┷━━━┷━━━┛
对于4个球ABCD，可找到称3次的独立称量方案：
三次分别称：A-B，C-A，D-A，即可(结果分析从略)
[几点说明]
1) 新的5个问题都已有明确的答案与证明
2) 新的5个问题中，第0'题最为简单，且与其余4题关系不是很大
3) 1'2'3'4'四个问题中，解决第2'题最为关键，一旦2'题获解，另
三题唾手可得
4) 对于传统问题而言，当你可用k次称出N个球后，那么显然k次
也可称出(N-1)个球。
而对新问题而言，通常时候 N 个球的称法与 (N-1) 个球的称法会
相差很多。这正是新问题的一个难点所在。所以当你做出了 12 个
球的情况时，不要忘了 11 个球的问题仍需要你去解决。


发信人: Nature (成长的烦恼), 信区: Mathematics
标 题: [转载] 关于称球问题的我的解答
发信站: 南京大学小百合站 (Wed Nov 8 17:47:05 2000), 站内信件

【 以下文字转载自 Algorithm 讨论区 】
【 原文由 grass 所发表 】
这是我当时的一份作业题报告.写的有些乱，不过，应该可以看明白的，我想。

试题一：
有12个球,其中有一个坏球,但不知道是轻是重。试用天平称三次，找出坏球，并说出它是轻是重。

试题二：
称n次，最多可以在多少个球中找出坏球来。（坏球只有一个）对于天平问题，我们通常都可以把它和3相联系，这是因为对于每一次称物，都可以分
为三堆，天平上两堆，再加上未放上去的一堆；这样无论天平是否平衡，我们都可以得到一些信息，并且信息不浪费。具体先看试题一的解答：

12个球，分别编号1，2，……，11，12。
1、 1，2，3，4 对 5，6，7，8 （一）
< 转6 ; > 转10 （类似 <） ； = 转2 ；
2、 9，10 对 11，1 （二）
< 转 5 ; > 转 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、 结束。
通过对第一题的思索解答，我们可以发现一些规律：对于称n次，若我们能把称n-1次的问题解决，n次就可以用递推来求出球的个数。（对于我们要解决的这个问题，用f(n)表示。）
但是，也不是单纯简单的递推。因为我们在称第一次的时候，得到了一些信息，这些信息可以给我们后面的称球带来帮助。
我们来分析第一次称的三堆球：
(一)若不平衡，我们得到的信息是：
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<2*(3^k), 则天平两边各放[a/2]个半确定重球,3^k-[a/2]个半确定轻球。若不平衡，坏球在重的那堆中的半确定重球或轻的那堆半确定轻球中；平衡的话，坏球在剩下的那堆中。这时剩3^k个球，k次可判断出来，共k+1次，成立。
a < b 同理可证。
所以3^(k+1)个球是可判断的。
②若3^(k+1)+1个球，称一次，只能提供三条信息，由抽屉原理，必然有3^k+1个球的信息是相同的，这3^k+1个球无法用k次称出。故k+1次无法保证能判断出来。
故，n=k+1也成立。
由归纳法，h(n)=3^n对一切自然数都成立。
再回到原题，来求f(n).
对于第一次处理后，若不平衡，天平两边的球都将成为半确定球。设两边球个数各为a个，另外一堆个数为b个。易知，a与b相互独立。为使得f(n)=2a+b最大，即要分别求出a , b的最大值。
由引理二，这2a个半确定球要在n-1次判断出，当且仅当
2a <= h (n-1)=3^(n-1). 但等号无法取到，因为3^(n-1)为奇数,所以2a<=3(n-1)-1,
max(a)=(3^(n-1)-1)/2
f(n)=(3^(n-1)-1)+max(b)
定义四、给一个确定好球，n次能称的最多非确定球的个数用g(n)表示。
引理三：g(n)=f(n)+1若有任意确定好球的话，g(n)比f(n)可提高效率的地方就在于第一次称的时候可以两边放的非确定球的个数不一样多。一边放c个不确定球，一边放a个不确定球和c-a个确定好球，剩下一堆为b个。平衡的话,b个球的处理同f(n),所以此时的max(b)显然等于f(n)的max(b)。若不平衡的话，就有a + c个不确定球。
a + c <= 3 ^ ( n – 1 ) （等号可取）
令c=a+1=(3^(n-1)+1)/2,则此时只需要一个确定好球,
g(n)=max(a + c)+max(b)=3^(n-1)+max(b)=f(n)+1 #
再来研究max(b).若不平衡,则b个球全为确定好球,否则,全为非确定球。但天平上的球全为确定好球。这时的b就恰好同我们刚刚讨论的g(n). 即有max(b)=g(n-1)=f(n-1)+1.

故有f(n)=3^(n-1)-1+f(n-1)+1 =f(n-1)+3^(n-1)
这是一个递推公式。
我们又易知，f(2)=3 ,所以易解得
f (n)=(3^n-3) / 2
故，称n次，最多可以在(3^n-3) / 2个球中找出坏球来。（坏球只有一个）
当n=3时，即第一题，f(3)=12. 3次能称得的最大数目将是12个。

头晕了，一一，来，让我靠一下

我先涂点清凉油，清醒一下

94啊

神经

来偶带你看医生啊

讨论过了的，不久以前！
实际上一个优选法。
小小问题却有大道理呢！