关于12个球的经典智力题

[uhm1978]

关于12个球的经典智力题

有12个球大小、颜色都一样，只有其中一个球的重量与其它11个球不一样，但不知是轻还是重。请你用天平只能称三次，将这个球找出来，而且还得回答它是轻了还是重了。
请仔细推演，很难了哟！

[uhm1978]

是我出的题太难了么？

[冬青]

分好几步骤，，反正先得4个来称。。。。。。。。。。。。

[uhm1978]

7，光说不练，废话多多。

[jingjinghd]

这是历史上的经典分类老题，可以适用于很多场合。

类似题目：有十瓶药，药片数不限（我理解的，原题未提到），其中若干瓶内药片超重。正常的药片每片5克，超重的药片每片6克。问如何只称一次，即可指出那些瓶内药片超重？

方法如下：编号，从第n瓶取2^(n-1)粒，一起称,最后比标准重量多x粒, 将x分解为若干个2若干次幂的和即可

关于称小球问题，一般是这样的：
有N个小球外形无区别，但是有一个在质量上与其他的球不一样。用天平称最少m次一定将不同的球找出来。显然随N增大，m不会减小。现在想解决的问题是对于任何给定的次数m,
找出在该次数下能解决的最大的N值,用Nmax来表示。并给出对应于(Nmax,m)的一种解法.
Nmax(k)=(3^k-3)/2.
N1max(k)=(3^k-1)/2.
意外的发现只比前面不分轻重的情况分别小一！！！

证明过程由于有太多类似，故在此略去，仅举一个例子来说明。
k=3,Nmax=12
共12个球
第一次： 4A ? 4B 剩下4C
如果相等，则A和B都是标准球。
第二次 C1+A ? C2+C3
如果相等，则坏球为C3，再用C3与标准球比较一次即可。
如果不等，再比较C2和C3，可以这两次结果判断C1,C2,C3中哪个是坏球和轻重。
如果不等，不妨设4A>4B.此时C球都是标准球。
第二次 A1+B2+B3+B4 ? B1+C1+C2+C3
如果相等，则坏球在A2,A3,A4中，且重。再比较A2和A3即知。
如果左边小于右边，则在B2,B3,B4中且轻。再比较B2和B3即可。
如果左边大于右边，则是A1且重或是B1且轻 ，再拿A1和标准球即可。

此类问题有一个统一的公式和解法,若令,n为称的次数,a_{n}表示 n 次所能区分的最大个数.则相应公式:
(1)a_{n}=3^{n}, 已知轻重.
(2)a_{n}=(3^{n}-1)/2,未知轻重,但不需确定其与别的球之间的轻重关系.
(3)a_{n}=(3^{n}-3)/2,未知轻重,需要确定其与别的球之间的轻重关系.

[jingjinghd]

下面是本题12个小球的解决办法：(我用编程语言来解决,希望能看得懂)

1-12
1234 vs 5678
if = then in 9-12
9,10 vs 11,1
if = then 12
if < then 9,10 轻or 11重
if > then 9,10 重or 12轻
此二者解法同下
if != 不妨假设>
125 vs 346
if = then in 78,且是轻的，7 vs 1 ->ok
if > then 12 重或者6轻
1 vs 2
if > then 1
if < then 2
if = then 6
if < then 34重或者5轻
3 vs 4
if > then 3
if < then 4
if = then 5
end


对于N(m)=(3^m-1)/2个小球，现在我们来寻求m次的解法。
首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很简单，在此略去?
其次，若m?lt;=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次是可以称出来的。

由这个解法加上前面所给出的上界Nmax(m)<=(3^m-1)/2，知称m次能解决的最大的小球数
Nmax(m)=(3^m-1)/2。
有兴趣的人可以验证一下m=3,N=13的情况

[冬青]

狂晕。。。。。。。。。。。。　

[jingjinghd]

呵呵，晕几次就成再造之材了，，，

[Rheinhardt]

哈哈哈哈，拿去作Math 2 的 &Uuml;bung 会下死老外的。

[Blue]

看完想不叫人头大都难

[azhu]

新问题：
如果只称3次，可以最多解决几个求的问题：1.要求搞清不一样球的轻重，2.不要求

嘻嘻，好象能到18个....

[Flysmall]

好怀念这些初中计算机比赛的老问题. 递归求解呗, 干吗让人费那么多脑子.

[azhu]

这是研究生考试面试时的一道题诶

[pkulily]

这个贴不错，虽然很早以前看过。现在再温习一遍，觉得还是很经典。

[Jonny]

这个题早就作过了，嘻嘻，不过还是挺有意思的

[Eisblume]

这道题挺熟的。

[花摘累]

晕！这叫笑口长开啊？

[tulpe123]

考小学生的都有脸拿出来，哎，可怜

[高鸟尽]

分两堆A,B，每堆6个。
第一称： A/2 ，每边3个。平了，进入下一轮。没平:！！试着从两边同时拿起两个。对，我们要的结果是：当拿起后，天平保持平衡。！！这意味着，你已拿到问题球，但不知是哪一个。
第二称：a: 在前一称没平的情况下，将手中的两个放到天平上，天平将倾斜。用另外的球来代替其中任意一个，如果替代的结果天平平衡，那被你替下的就是了；如果不平，那没被替下的就是了。至此，两次称量，问题已解。b:在第一称 A/2平衡的情况下，将 B/2放到天平两端。重复第一称中两对”！！“之间的步骤。
第三称：将第二称中由b 筛出的一对放到天平两端，重复第二称a 的步骤。
题外话------------------------
这确实不难，但也绝对不是简单得让人一目了然。生活中很多问题其本质很单纯，但我们习惯于把简单的东西复杂化，这无异于折磨。说实话，我佩服他们的韧性。

[Rheinhardt]

拿去球的话，也应该算称一次了。

[高鸟尽]

见仁见智吧

[高鸟尽]

用天平称东西，两边平了才算一次，对吧？