geslon系列难题之二：电子秤称小球问题

colinsze

15个球称4次~~方法：首先把15个球分3组，1组5个~每组放上去称一次得到重量为X，X，Y显然重量为Y的那组有异常球~这是X/5为一个正常球重量，Y-4X/5就是异常球的重量。。。好象只称了3次....

colinsze

哦~题目没看仔细~~以为只要知道重量~~原来还要指出是哪个球~~上面的答案当我没说`我再想想

nangongke

<P>想了一晚终于想出一种方法来解这个问题，就是不知道写在这么靠后还有没有人能够看到：）</P>
<P>&nbsp;</P>
<P>设标准小球重量为s。</P>
<P>&nbsp;</P>
<P>一个事实是：如果知道异常小球是某2个小球中的一个，并且知道标准重量s，那么经过一次称量，一定可以从这两个小球中找出这个异常小球；如果再知道这两个小球的总重量，那么就可以计算出异常小球的重量来。</P>
<P>&nbsp;</P>
<P>所以，我们的目标就是经过3次称量，将异常小球的范围缩小在2个以内，并且求出标准重量s。</P>
<P><BR>先将小球进行编号，分别为：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15。</P>
<P>再设：1，2号小球重量和为A1； 3，4号小球重量和为A2； 5，6号小球重量和为B1； 7，8号小球重量和为B2； 9号小球重量为C1； 10，11号小球重量和为C2。（注，C1是单个小球9号的重量，其他都是两个小球的重量和，这点很重要）</P>
<P><BR>第一次称量1-8号共8个小球，设其总重量为a。于是可以得到等式：A1+A2+B1+B2=a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （*）（8个小球，每个小球平均重量为a/8）</P>
<P>&nbsp;</P>
<P>第二次称量5-11号共7个小球，设其总重量为b。得到等式：B1+B2+C1+C2=b&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （*）（7个小球，每个小球平均重量为b/7）</P>
<P>&nbsp;</P>
<P>若a/8与b/7的值相同，那么可以肯定1-11号都是标准小球，而标准小球的重量就是s=a/8=b/7，并且可以知道异常小球一定在12，13，14，15这4个小球之中，那么，第三次称量12，13两个小球的总重量，和s进行比较，就可以知道异常小球是在12，13中，还是在14，15中，由前边的事实便可以找出异常小球。（注，这里有一种非常极端的情况，只能指出异常小球，但不能得到其重量，其他情况均可以算出异常小球的重量）</P>
<P>&nbsp;</P>
<P>若a/8与b/7的值不相同，那么可以肯定异常小球一定在1-11号球之中。</P>
<P>&nbsp;</P>
<P>这时第三次称量1，2，5，6，9 这5个小球，设总重量为c。并得到等式：A1+B1+C1=c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （*）（5个小球，每个小球平均重量为c/5）</P>
<P>&nbsp;</P>
<P>对三个（*）式进行运算可以得到另外三个等式：</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; A2+B2-C1=a-c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （*）（3个小球，每个小球平均重量为(a-c)/3）<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; B2+C2-A1=b-c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （*）（2个小球，每个小球平均重量为(b-c)/2）<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; A1+A2-C1-C2=a-b&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （*）（1个小球，小球平均重量为a-b）</P>
<P>&nbsp;</P>
<P>比较这6个平均值（a/8, b/7, c/5, (a-c)/3, (b-c)/2, a-b）必然至少有两个平均值相等，这是因为：对于A1而言，必有2个等式B1+B2+C1+C2=b，A2+B2-C1=a-c中不含有A1，因而这两个等式中都是标准小球，其平均值必定相等，而其他4个多项式都含有A1，且每个等式中小球个数不同，因而平均值必定不同；同理，对于A2，B1，B2，C1，C2而言，也都至少有两个等式中不含它们（有的是三个等式不含它们）。</P>
<P>&nbsp;</P>
<P>所以6个平均值（a/8, b/7, c/5, (a-c)/3, (b-c)/2, a-b）中，相等的数值就是标准小球的重量s，在平均值不相等的几个等式中，共同出现的变量就是包含异常小球的变量。比如，若c/5=(a-b)，而其它4个等式中共同出现的变量是B2，所以可以确定异常小球在7号和8号中间。</P>
<P>&nbsp;</P>
<P>这样，就可以将异常小球的范围缩小到两个小球之中，并且知道标准重量s以及两个小球的重量和（重量和可以通过线性代数的知识从上边等式中求得），利用前边的事实，可以指出异常小球，并算出其重量。</P>
<P>&nbsp;</P>
<P>这种方法，完全可以指出异常小球是哪个，但是对于一种极端情况无法算出其重量，其他genetic情况下都能算出异常小球的重量来。</P>

逆水流光

作最坏的打算，先从15个小球里取出一个，再把剩下的小球放在秤的两边（每边有七个），再把轻一点那边的球取出来，按上述方法继续秤，最后秤完就刚好四次。

ares_g

我在70楼的回答不对么？LZ说句话。

寂寞的瓶子

头好大，本贴里回帖还写了大量算法的全是高手，我学习了，觉得73楼的最让我看得懂也最合理，不知道楼主的答案到底是不是这样

asawdh

我是这样称的：
一、先把15个球分为三组，第组5个，并分别编上号：
第1组：1、2、3、4、5
第2组：A、B、C、D、E
第3组：a、b、c、d、e

二、先称第1组，假设总重量为S1

三、再称第2组，假设总重量为S2

四、第3组先不称，假设总重量为S3，但目前不知道具体重量

现在分析称过两次后的几种情况：

第一种情况：
S1＝S2，很明显，重量不一样的球肯定在第3组里，并且我们知标准球的重量为K＝（S1）/5

称第3组中的a和b，得重量为T，
1)如T<>2*K，说明a和b中有一个球为重量不同的球。再称一下a
  如a<>K，则a为要找的球,a球重量为称得的重量;
  如a＝K，则b为要找的球，b球重量为T－K

2)如T＝2*K,则说明要找的球在c、d、e里，


第二种情况：
S1<>S2

wyjwyj

每组5个.分3组.称两组.相等就是没称的异常.再用这种方法一直称

wzm4970

难，想了几分钟，没有头序，直接看下人家怎么搞的

kop31071

5次很简单的啊，4次称不出来，期待答案！！