据说是世界上目前最好的智力题目。(300分)

13个球的问题好象是哈佛某一年学生会举办活动时出的一个智力题
我花了四个小时还做了出来，做得真累

看到楼上各位的解题思路，真为一些缺少数学基础的程序员的前途担忧，
更为其中既缺少数学基础又非常“自信”的“同志”悲哀：当你补上数学
这门课以后就不会那么自信了，也就成熟了。
等着挨骂。

天啊，有完没完啊？？
麻烦各位贴你们的答案前看看我的答案嘛，，我给的都是正确答案！！

回复stuwe的问题：
“若重，则取3球中的2个球互称（过秤三）
取重者为异常球，若相等，则没有称的第3球必为异常球
若轻，算法同上。
樓上老兄，何以得知重球為異常球呢，假如異常球是輕的，那不是全錯了？？？
”
你所问的是第三次称重的算法，然而在此之前你应该注意第二次称重的算法。
在这个计算分支中，第一次的称重是假设了排除8个正常球的情况，那么请注意第二次的称重
是将4个未确定球中的3个和3个已经确定的正常球做称重，若未确定球重，则很显然异常球是重球，若轻
则异常球是轻球，若相等，则全是正常球。
有了以上的结论，再做第三次称重，就可以明确的知道异常球是重是轻了，因此老兄的假设是不存在的。
可能是我表达太简单了，引起误解，抱歉。

其实我在计算的时候最大的障碍是最后一称的条件，要知道异常球是轻是重，又要控制剩余
球的数量。我起初尝试过4-8分法和6-6分法，这是最容易想到的两种分法，但是单走两条路中
的任何一条都无法得到理想的结果，后来.我尝试把两种算法结合起来,以4-8分法为主,在处理
8个球的分支中使用了6-6分法的一部分,在此期间,每次称重我都十分注意取得异常球的轻重状况,
其实算法的难点也在这里,往往轻重的概念容易被忽视,但在最后它却在论证中起了决定性的作用。
我对我前面发的算法十分满意的，希望大家能够一起讨论，提出不对之处。
还有，智力题当然要大家来参与才有意思，就算一看就知道错的答案也罢了，
自己没有算法却嘲笑别人的发言可实在不怎么样。

要是条件诗异常轻或者异常重就好了

智力题就是这样难呀,要是知道轻重的话,就变成"世界上目前最无聊的智力题目"了

我的算法和ka_lee的一致,1又1/6小时;
由于落落有答案>落落的解法不一定是自己的;
tyzytyz_cn的算法有意思,一开始得到了更多的信息,后面的推理就相对简单了;
请教落落个问题:
如果从20000个球里找出一个不标准球,最少需要秤几次?请给出证明:
1:n次能秤出;
2:n-1次不能称出.

有谁能告诉我，类似称小球、分酒这类问题，在数学中是哪一类问题？
有没有一个更系统的方法解决此类问题？
我想，掌握了对此类问题的一个“通用”的解决方法才是我们的最终目的吧？

这个是求m次所能解决的上限Nmax(m)问题。
为解决这个问题，我们给出几个引理。
引理一：无论加上什么其他的附加条件，只要k个球中的任一个都有可能是坏球（概率不
为0），则当k>3^L时，称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球，除k个未知球外还提供若干个标准球，以及k个球中某些的质量和大于另外一些的和等等，只要在这些条件下k个球中的任一个都还有可能是坏球，就可以是引理所说的附加条件。
证明：很显然，若k>3^L，则哪个球是坏球一共有k中情况，而称L次一共有3^L种情况，
由k>3^L知不可能一定分辨出哪个球是坏球。
引理二：如果另外在提供任意多个标准球（即在N个未知球外还任给标准球作"砝码"用）?则称m次最多能从N1max(m)=(3^m+1)/2个球中找出坏球来。
证明：对该引理的证明可以采用数学归纳法。
当m=1时，显然若只有两个球，则任挑一个与另外的标准球比较（额外提供的，不是
两个中的），若相等则是剩下那一个，若不等则是这一个。所以N1max(1)>=2。
而对于三个球的情况，如果第一次称用了两个或三个未知球，则无法判断出用
过的球中谁是坏球（只称一次），而如果第一次称只用了一个未知球，则剩下
的两个球无法区分。因此一次不能解决三个球的问题。所以N1max(1)<3。
由N1max(1)<3和N1max(1)>=2知，N1max=2。
设当m<=k-1时命题都成立，则考虑m=k的情况。
第一次称不能使用超过3^(k-1)个未知球，否则如果坏球在这超过3^(k-1)个
球中的话，由引理一，在剩下的(k-1)次中不能肯定找出这个坏球来?
另外，若第一次称碰到的都是好球，则第一次称后的结果就是多提供了一些
标准球（这个结果对已经提供了任意个标准球的情况是毫无意义的）和缩小
坏球的范围到剩下的球中。由归纳假设，剩下的球的数目不超过N1max(k-1)
才能保证一定能称出来。所以：N1max(k)<=3^(k-1)+N1max(k-1)=(3^k+1)/2。
如果有(3^k+1)/2个未知球，则第一次将3^(k-1)个未知球和提供的3^(k-1)个
未知球比较：如果相等，则坏球在剩下的N1max(k-1)个中，由归纳假设能分
出来；如果不等，则坏球在这3^(k-1)个中，但是同时知道了坏球是轻还是
重，由三分法可以很容易用k-1次找出来。所以对于(3^k+1)/2个未知球的情
况，是能够用k次找出坏球来的。即N1max(k)>=(3^k+1)/2.
由前面的推导知，N1max(k)=(3^k+1)/2。所以m=k时命题也成立。
由数学归纳法,所以N1max(k)=(3^k+1)/2对所有的自然数k都成立。
引理二得证。
引理三：Nmax(m)<=(3^m-1)/2。(m>=2)
证明：在原来的称小球问题中，起初没有提供标准球，所以第一次称的数目必须是偶数，由和引理二中推导N1max(m)时类似，有如下结论：
Nmax(m)<=N1max(m-1) + [3^(m-1)-1]
若第一次称平衡了最多剩下的球数 第一次称最多使用的球数，必须是偶数
所以Nmax(m)<=(3^m-1)/2=N1max(m)-1。命题得证。
到此为止，我们求出了称小球问题的一个上界Nmax(m)<=(3^m-1)/2。（m>=2)
在后面我们将证明这是一个上确界，即Nmax(m)=(3^m-1)/2。
对于m=1的情况，由于必须有两个以上球（否则无所谓好坏球），所以一次是怎么也称不
出来的，因此我们不讨论m=1的情况。

对于N(m)=(3^m-1)/2个小球，现在我们来寻求m次的解法。
首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很
简单，在此略去?
其次，若m?=k-1时，假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。
现在来考虑m=k的情况。
第一次称取[3^(k-1)-1]个球放在天平天平两端，则：
如果平衡，获得[3^(k-1)-1]个标准球，坏球在剩下的[3^(k-1)+1]/2个中。由于
[3^(k-1)-1]>=[3^(k-1)+1]/2，（k>=2),即已知的标准球数不小于未知球数?
所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理二可知
对于[3^(k-1)+1]/2的情况(k-1)次可解。
如果不平衡，大的那方记做A,小的那方记作B。标准球记做C.
则现在我们有[3^(k-1)-1]/2个A球和B球，有[3^(k-1)+1]/2个C球。
第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边?
3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
如果左边大于右边，则说明是在左边的3^(k-2)个A球中质量大的为坏球；
如果左边等于右边，则说明是在第二次称时没用的3^(k-2)个B球中质量轻
的为坏球。以上两种情况都可以再用三分法(k-2)次解决，加上前两
次共k次解决。
如果左边小于右边，则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样
数目的A球中。此时的情况和第二次开始时类似（只不过是k-1变成k-2).
用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况，这时
只需拿A球和标准球比较以下就行了。
因此在这种情况下也是可以最终用k次解决的。
由以上两步加上数学归纳法知，对于N(m)=(3^m-1)/2的情况，称m次是可以称出来的。
20000个球，你自己算嘛~~~我公式都给你拉~~~啦啦啦~~

据说张亚勤六岁就做过这题.

怎么还没完成啊，这题也够难的了

此题有解！我有朋友做出来过。

up

提前先，思考中～～

分成4组，没组三个，设为 组1 组2 组3 组4
组1-2比较一次 组3-4比较一次，这里最用2次
取出最重的那一组，将其中2个再称一次
结果就出来了
哈，最少用2次，最多3次就出来结果了
我的第一想法哦！
实在佩服自己
有够聪明！！！....
等等，似乎以前做过............
晕

耶，不知道其中哦！
倒
再研究！

做过,CSDN杂志上有过,好像是微软的面试题目.........

sephil:
错误答案。
早该结束了

to:天空还下着沙
正确的答案上面已经有了
to:落落 / chn2k
在这里我们首先要认识一个问题:我们要获得的只是一个具有通用性的公式，
即是对于不同数量的球都具有适用性的算法。而不是一个即具有通用性，又
能够实现最优方案的算法公式。事实上，由于球数的不同，实现最优方案的
算法可能各不相同，象这样含盖所有最优算法的公式可能根本不存在，举一
个最简单的例子，像落落提供的算法，（虽然我还没有看完。。）不需要代
入20000，只要代入12，便可以得到最后的答案肯定大于3。那是因为数学归
纳法所使用的公式是一个易于理解和操作的公式，一个这样的公式是不可能
号称“世界上目前最好的智力题目”的。
在这里我介绍一下我的思路：
首先我们需要知道在K个球的情况下，当K小于某个值的时候，称重次数N是
可以被确定下来的。即当K无限大时，每一组称重（一组是固定的次数1次或
2次或更多次的称重）都会排除一部分正常球，而当K缩小到某一个值之内时，
可以知道剩下还需要称几次。在这里，我假设K的最终值为3，则N=2，不需要
附加条件。
有了最终值,接下来讨论当K>=4的情况。我采用4分法方式。将K个球等分为4
份，若有余数M，则M必为（3，2，1，0）。算法是将4份中取任意两份称重，
若不相等，则坏球必在这两份中，若相等，则再称另外两组，判定坏球是否在
另外两组中，若还是相等，则坏球在余数中。
于是我们得到每一组称重最多要2次，当球数为K（K>=3），每组称重后的剩余
球数是K=（K-（K mod 4））/2,因为我们要获得的是最多需要几次称重，所以
要讨论运气最坏的情况，在K<=3之前，计算始终不会进入余数分支中。
余数分支的计算非常简单：当K=3则N=2，K=2 N=1，K=1 N=0，K=0 N无解（全是
正常球）
这样使用数学归纳法能够很快得到计算方法。我写了个函数实现这个算法：
Function do
itplease(k:interger,N:interger):Boolean;
//K为球数，N为称重数
begin
N:=0;
if (k<=3) then
begin
case k of
0:N:=-1;
1:N:=-1;
2:N:=-1;
3:N:=2;
end;
end;
while not(k<=3) do
begin
k:=(k-(k mod 4))/2
N:=N+2;
end;
case k of
0:N:=-1;
1:N:=N;
2:N:=N+1;
3:N:=N+2;
end;
end;

当然这不是最优算法,用12代入答案是5而不是3,不过作为通用算法
是个很不错的公式.不知道谁有更好的公式,拿出来一起讨论吧。