×

Loading...
Ad by
  • 推荐 OXIO 加拿大高速网络,最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务
Ad by
  • 推荐 OXIO 加拿大高速网络,最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

My answer

本文发表在 rolia.net 枫下论坛先给小球分三组并编号,
第一组: 1, 2, 3, 4,
第二组: 5, 6, 7, 8,
第三组: 9, 10, 11, 12

第一次用天平: 任取两组小球放上天平, 假设取第一和第二组, 有两种可能,
1. 两组相等, 则判断小球在第三组, 接着用下面几小步可找出小球:
1) 第二次用天平: 从1-8中任取两小球(假设1,2), 从第三组中任取两小球(假设9,10),
放上天平: 如果相等,则是11或12; 如果不相等,则是9或10. 现假设小球是11或12,
2) 第三次用天平: 从1-10中任取一小球(假设取1号球), 从11,12中任取一(假设取11号球),
放上天平: 如果相等,则是12号球,如果不相等则是11号球.
2.两组不相等,判断小球在第一(1-4号球)或第二组(5-6号球)中,假设天平
  左向上右向下倾斜,记住该特征.
  1)第二次用天平:
    左边天平:放4号,5号,6号
    右边天平:放7号,1号,9号(9号从第三组中取)
    此时,第一组中还剩下2号和3号,第二次组剩下8号.
    A)如果相等:则判断小球在2,3,8中,
      第三次用天平,取2,3放上天平,如果相等,是8号球,
      如果不等,可判断该小球轻于其他球,则轻的小球是也.
    B)如果天平左向上右向下,即和第一次称特征一样:则判断小球是4号或7号,
      第三次用天平,方法同第一种情况的第二步.
    C)如果天平左向上右向下:判断小球在1,5,6中,
      第三次用天平,方法类似A),取5,6放上天平,.....更多精彩文章及讨论,请光临枫下论坛 rolia.net
Report

Replies, comments and Discussions:

  • 枫下沙龙 / 休闲娱乐 / 智力题
    以下据说为 XXX 的面试考题:

    有12个外观一样的小球,其中有一个重量和其它11个球不一样的小球A。用一架天平,只允许称三次,请选出那个小球A。

    (华工一研究生应试失败后,在班里试了30分钟没人解出。几天前,其班上同学(朋友)拿来一试.....)

    ---------------

    你也来试一试?
    • my approach... (not finished yet)
      本文发表在 rolia.net 枫下论坛1, Suppose the target ball is X, and standard ball is S. Devide the balls into 3 groups with 4 balls each, mark them as Group A, B, C;

      2, Weight A versus B, for the weight there're two situations:

      2.1 A and B weight the same: The ball X must in Group C, and all balls in A and B are standard balls S. Mark C balls as C1, C2, C3, C4. Weight 2 standard balls versus C1 and C2. (second pass). If C1 + C2 <> 2S. Either C1 or C2 must be X, mark them as Cx1 and Cx2; Other wise C1 + C2 = 2S, either C3 or C4 must be X, mark them as Cx1 and Cx2.

      2.1.1 Weight S versus Cx1. (third pass) If Cx1 = S, then Cx2 = X ; otherwise Cx1 = X. (end)

      2.2 A and B weight differently, then every ball in C is S. Mark balls in A and B as A1, A2, A3, A4 and B1...B4. Suppose A > B. Weight A1, A2, B1, B2 (AB12) versus 4S.

      2.2.a If AB12 > 4S, then X is among A12 (because A>B). Mark A1 as Cx1, A2 as Cx2, goto step 2.1.1.

      2.2.b If AB12 < 4S, then X is among B12. Mark B1 as Cx1, B2 as Cx2. goto step 2.1.1.

      2.2.c If AB12 = 4S, then X is among AB34, and A34 > B34.更多精彩文章及讨论,请光临枫下论坛 rolia.net
      • why do u so hard to do that?
        My solution is easy:

        (1) 12 = 6 + 6
        (2) 6 = 3 + 3
        (3) 4 = 3 + 1 ( 1 from the other team)

        think it over

        Right?
        • sailor is right!
    • 1.divide the 12 balls into 2 groups (6 a group). Weigh the first time. discard the lighter group. 2. divide the 6 into 2 groups (3 a group), weigh the second time. discard the lighter group.
      3. pick up any two balls, weigh the 3rd time. If they are equal, the one not picked up is A. If not, the heavier one is A.
      • 没有您想的这么简单,要是如此的话平均每人两分钟以内都可以想出来的,因为你根本不知道那个球是比其它球重还是轻,我老当年花了两天两夜才苦思出来.
      • Why discard the lighter group? It suppose A is weight different than others not lighter.
        • You get the point. I had the wrong perception.
    • 这题我做过,确实不简单,我趟在床上苦想了1小时左右吧,才解出,答案要写满一张A4纸。
      • 老油,你比我聪明多了.
        • 承蒙夸奖,飘飘然之余,再吹两句。
          才注意到你说两天两夜做出来的,不好意思。
          一般男性比较善于空想吧,而且不易分心,你能想出来也不容易了。我估计你两天两夜的有效时间也不会太久。而且猜想你是不是边想边拿笔在纸上画来着?
          我是只会空想,大一暑假,弄来个魔方,白天怎么也难有进展,结果连着三个晚上睡觉前的空想,每天早上是大有进展,到第三天半夜爬起,总算大功告成。
    • BBS水木清华站: 称小球问题终结(99年微软招聘的考题耶,愿意练脑者请看:http://www.sdfi.edu.cn/tsinghua/greatturn.aix/index.htm)
      本文发表在 rolia.net 枫下论坛关于称小球问题,一般是这样的:
      有N个小球外形无区别,但是有一个在质量上与其他的球不一样。用天平称最少m次一定将
      不同的球找出来。显然随N增大,m不会减小。现在想解决的问题是对于任何给定的次数m,
      找出在该次数下能解决的最大的N值,用Nmax来表示。并给出对应于(Nmax,m)的一种解法.

      现在来求m次所能解决的上限Nmax(m)问题。
      为解决这个问题,我们给出几个引理。

      引理一:无论加上什么其他的附加条件,只要k个球中的任一个都有可能是坏球(概率不
      为0),则当k>3^L时,称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,
      除k个未知球外还提供若干个标准球,以及k个球中某些的质量和大于另外一些的和等等,
      只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
      证明:很显然,若k>3^L,则哪个球是坏球一共有k中情况,而称L次一共有3^L种情况,
      由k>3^L知不可能一定分辨出哪个球是坏球。

      引理二:如果另外在提供任意多个标准球(即在N个未知球外还任给标准球作"砝码"用)?nbsp;
      则称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)次中不能肯定找出这个坏球来?nbsp;
      另外,若第一次称碰到的都是好球,则第一次称后的结果就是多提供了一些
      标准球(这个结果对已经提供了任意个标准球的情况是毫无意义的)和缩小
      坏球的范围到剩下的球中。由归纳假设,剩下的球的数目不超过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的情况,相当于四个小球来称两次的情况,这个已经讨论过多次了,也很
      简单,在此略去?nbsp;
      其次,若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),即已知的标准球数不小于未知球数?nbsp;
      所以在以后的测量中就相当于任意给定标准球的情况,由前面的引理二可知
      对于[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球放左边?nbsp;
      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的情况----该情况已经被反复拿出来讨论过了。更多精彩文章及讨论,请光临枫下论坛 rolia.net
      • 疑问?
        经过第二次称:如果左边等于右边,则说明是在第二次称时没用的3^(k-2)个B球中质量轻的为坏球。???
        为什么不可以是第二次称时没用的A球中质量重者为坏球????
    • 我已经几乎解出来了,到最后功亏一篑。认输。
    • I got it, cost me 20mins.
      Divide the 12 ball into 4 3ball group A,B,C and D. Measure A and B, now you know the different ball is in A,B or C,D.Say it is in A and B, A>B. , then measure A1+B2to B1+A2, if it the same, then the different ball is A3 or B3, then measure C1+C2with A3+C1,if it is the same, B3 is the different ball, if it is different, A3 is the different ball. But if A1+B2 >B1+A2, then it means A2, B2 did not change the weight difference, so the different ball is in A1 and B1, then measure A1+C3and C1+C2, you can get the different one. If A1+B2<B1+A2, means the A2 and B2 change the weight difference, so the different ball is in A2 and B2, then measure A2+C3and C1+C2, you can get the different one.
      • I waste a little, you only need to measure C1 with A1,A2,A3 or B1 B2 and B3
      • You forget one situation:
        In the first measuring, how if A=B? Then the different is in either C or D. Could you weight only twice and find it out from those 6 balls?
      • IF A=B, How do you know C>D or C<D? Mesure C and D for the second time? haha,不够严密吧。
        • 我刚解出来时,记得可以多一个球,13个球也行,后来有一次有人提到这个题目时,好象推翻了。但刚刚一想好象还是行。只是有可能最后找出来的那个球(肯定能找出来。)不知道轻重。
          不过好象题目没要求知道轻重的吧?现在老了,完整的正确答案也想不清楚了。
          第一步肯定只有分成三组,其它肯定不行,如果还想找出答案的话,应该照这个思路走下去。
          • 老油老油, 我的VCD在你那儿吗
            • 唉呀,今天早上太匆忙,忘记了,你还有空过来吗?或者交给Beibei,他今晚要到我这儿来,你们下次开腐败大会时,他再给你?Beibei在吗?收到我Email没有?
              • 没事儿, 不着急, 怕你又带回上海去.
              • Hi buddy, I got you message. Please check you mail box. If any, please just give me a ring.
            • 你怎么又改名了?不申请学校啦?
              • 申请完了, 等OFFER呢
          • Check this solution
            Divide it into group A(A1,A2,A3,A4),group B(B1,B2,B3,B4) and Group C(C1,C2,C3,C4)

            IF (#1)A>B,
            (#2)A1+B1+A3>A2+B2+COMMON BALL=>A1+A3>B2+COMMON BALL GOTO #3
            (#2)A1+B1+A3=A2+B2+COMMON BALL=>A4+COMMON BALL>B3+B4 GOTO#3
            (#2)A1+B1+A3<A2+B2+COMMON BALL=>B1<A2(WHICH IS EASY TO MEASURE #3)
            (#1) A=B
            (#2)C1+C2>C3+COMMON BALL GOTO#3
            (#2) C1+C2<C3+COMMON BALL GOTO#3
            (#2)C1+C2=C3+COMMON BALL=> C4 IS THE DIFFERENT BALL

            (#3)FOR EXAMPLE: C1+C2>C3+COMMON BALL
            AT THIS TIME, WE KNOW, IF A1OR A2 IS DIFFERENT, IT MUST BE HEAVIER THAN COMMON BALL, IF C3 IS DIFFERENT, IT MUST BE LIGHTER THAN COMMON.
            THAN MEASURE C1 AND C2, IF C1>C2, C1 IS DIFFERENT, C1=C2, C3 IS DIFFERENT, IF C1<C2, C2 IS DIFFERENT.
        • You are right, my fault. I am thinking
    • My answer
      本文发表在 rolia.net 枫下论坛先给小球分三组并编号,
      第一组: 1, 2, 3, 4,
      第二组: 5, 6, 7, 8,
      第三组: 9, 10, 11, 12

      第一次用天平: 任取两组小球放上天平, 假设取第一和第二组, 有两种可能,
      1. 两组相等, 则判断小球在第三组, 接着用下面几小步可找出小球:
      1) 第二次用天平: 从1-8中任取两小球(假设1,2), 从第三组中任取两小球(假设9,10),
      放上天平: 如果相等,则是11或12; 如果不相等,则是9或10. 现假设小球是11或12,
      2) 第三次用天平: 从1-10中任取一小球(假设取1号球), 从11,12中任取一(假设取11号球),
      放上天平: 如果相等,则是12号球,如果不相等则是11号球.
      2.两组不相等,判断小球在第一(1-4号球)或第二组(5-6号球)中,假设天平
        左向上右向下倾斜,记住该特征.
        1)第二次用天平:
          左边天平:放4号,5号,6号
          右边天平:放7号,1号,9号(9号从第三组中取)
          此时,第一组中还剩下2号和3号,第二次组剩下8号.
          A)如果相等:则判断小球在2,3,8中,
            第三次用天平,取2,3放上天平,如果相等,是8号球,
            如果不等,可判断该小球轻于其他球,则轻的小球是也.
          B)如果天平左向上右向下,即和第一次称特征一样:则判断小球是4号或7号,
            第三次用天平,方法同第一种情况的第二步.
          C)如果天平左向上右向下:判断小球在1,5,6中,
            第三次用天平,方法类似A),取5,6放上天平,.....更多精彩文章及讨论,请光临枫下论坛 rolia.net
      • 第一次看见这个题目是在上海的地铁票上当时...
        和先生两人讨论了一会儿,决定该题无解,xixi...:)
        但今天看到说居然有解,既然如此,想了好一会儿,在纸上划了半天,
        答案应该没错吧,各位多多指教.
      • Great solution!
        • 谢谢夸奖!
          • 是不是同意13个球也可以啊?
            • 同意, 13个球也可以,方法如下...
              同样分成三组,第一组4球,第二组4球,第三组5球.

              第一次使用天平: 若重量不等,则参照我前面贴子说的方法.
              若重量相等,则小球在第三组的5个球中,先编个号1,2,3,4,5
              第二次使用天平: 5球中任取3球, 假设取1,2,3放上天平一端,天平另一端
              放三个标准球.
              如果相等,则是4号或5号
              第三次使用天平:方法同前面贴子
              如果不等,则1,2,3中的一个,而且此时能判断该小球是轻是重.
              第三次使用天平: 123中任取两个放上天平一称即知.

              谢谢! :)
              • 真聪明!但还稍有一点问题,最后一步不能在123中任取两个,而必须取第二次称时放在一边的两个。
                • 我觉得可以呀, 因为这种情况下,第二次使用天平时已知该小球是轻还是重了,所以第三次只要从1,2,3中任取两个称称即知, (另,我不太明白你的意思)
                  • 比如 12 > 30 (0为标准球),你只只能知道如果x在12中则是重了,如果x为3则是轻了,你怎知x是轻是重?所以只能把12再称一下,相等则x=3,不等则x=max(1,2),OK?
                    • yi~,我的意思是,
                      因为这种情况下,第二次使用天平时已知该小球是比别人重还是轻了,假设是轻.

                      把1,2,3中任两个放上天平两端,假设1号和2号, 如果1=2,那么是3号,
                      如果1<>2, 那么就是轻的那个.

                      看起来好象咱们说的是一个意思嘛!

                      对吗?谢谢!
                      • 那你解释一下,第二次使用天平时,你是怎么知道该小球是比别人重还是轻的,你也有火眼金睛?要么是你先生告诉你的?
                        • 我没有火焰兢兢... :), 老油请进
                          第二次称时,5球中任取3个(假设是1,2,3号)放上天平一端,另一端放3个标准球, 如果不相等, 假设1,2,3这一端向下沉,说明该小球比其他重; 如果1,2,3这一端向上翘,说明该小球比其他轻.
                          • 我第二次称法和你不一样,只想到用一个标准球。果然厉害,而且不用先生帮忙。看来13个球不仅有解,还有多解!
                            • 多谢多谢! 您更厉害, 躺在窗上就能想出来!
                              • 躺在窗上,不敢不敢!来了这么些天,整天无所事事,今天晚上就要出发回国了,倒有机会练了练脑子。你这么快就解出答案,而且你的方法比我的简单,说明你不简单。
                                • 哦, 那你该去机场了,祝回家开心!
                • 还有啊, 谢谢夸奖!
                  • 不用谦虚,确实厉害!你先生没帮你?
                    • 那就不谦虚了,是自己做的. :)
      • 第三次用天平,取2,3放上天平,如果相等,是8号球,如果不等,可判断该小球轻于其他球. Again, you don't know if that ball is lighter or heyier than others, still need one extra step.
        • 请进
          2号和3号属于第一组.
          记得我的假设吗,假设第一次称时是左向上右向下, 即此时你已经知道第一组是轻于第二组的.

          我回答了你的问题了吗?
      • 其中C)写错了,应该是 C)如果天平左向下右向上..........
        再罗唆几句我是怎么想到答案的, XIXI...
        该题的关键在于第二次使用天平如何从两组中取球. 如何取球呢? 这时候我用的是反推法:
        因第三次使用天平就必须找出小球,所以此时用于判断的小球必须<=3个, 最坏的情况是3个, 又因为要利用第一次称已知的特征(哪组轻哪组重),这3个球必须分属两组, 即2球在一组,1球在另一组.
        此时问题就变成了, 两组8个球分成三组的问题,而且要符合上面所说的条件, ......
      • 聪明
    • 我一分钟想出了这个答案,不知对不对,请进:
      任取8个小球,分两组,各4个,用天平秤。
      如果平衡,说明轻的球在剩下的4个里面。取出剩下4个,分两组,再秤。可以找到轻一些的两个球,再秤最后一次,得到答案。
      如果不平衡,说明轻的球是取出来的8个球中的一个。于是也是得到4个球,如上法所说,再秤两次,得到答案。

      就是这样了
      • 人家的问题不是说有一个球轻, 而是说有一个球的重量不一样.
    • 我认为这道题很简单
      也是分三组,各4 个球.
      先秤两组, 如果不平衡, 那么此球肯定在这八个里. 如果此球比其它重的话, 当各拿去两个时, 假设它还在盘中那它一方, 肯定更往下倾斜, 这样一来只需将重的一方两个在称一次, 那个重的就是它. 反之如果它轻的话, 当各那掉两个相同的, 它会微微向下一点, 同样只需在称一下这两个, 轻的就是了. 如果它在那没被称的四个里, 放入盘中各两个, 然后各拿起一个其它相同的, 各放入其中(记住它们). 如果它重, 它那方将稍比刚才翘起, 然后将重的那方原来的两个再称一下, 重的就是. 依此类推.
      • 人家的问题不是说有一个球重, 而是说有一个球的重量不一样------Rollor
        • Yes, I know. Please read my answer carefully
          • You mean if you know the special ball is heavier, you can solve it, or if you know the special ball is lighter, you can also find it. I agree with that. But the problem is, nobody tells you whether it's heavier of lighter. OK?
      • 是我刚刚看的不够仔细。不过,当你各拿掉两个时,重的那边还是重,轻的那边还是轻,你怎么把范围缩小到两个呢? 要么是A1A2重,要么是B1B2轻,但你只有一次机会了。呵呵!
        • 这个道理很简单假设他们的偏差是5 克那么 45 比 40 肯定比25 比 20 倾斜的角度小.
          • 同意!原来你有火眼金睛啊?! 但是重的那边还是重,轻的那边还是轻,只是倾斜的角度稍大,你选择重的那两个还是轻的那两个?简单吧。
      • 你的思维太简单了。
      • 说老实话我觉得他很有创意,应该鼓励.
    • 不好意思,俺小学三年级就遇到这个问题了
    • The max number is 18 balls. You can try!
      • 18个球,不知轻重,三次我称不了!老兄,说说答案听听。