智商吧 关注:203,458贴子:1,885,456

十二球问题解法思路的条理化归纳

只看楼主收藏回复

【以下内容,原为另一个话题楼里面的回复帖,该话题楼已经被删(可能是被看做重复题目了)。但鄙人认为这些内容还是有意义的,故单作一话题另发,有修改。】
十二球问题是:有十二个乒乓球特征相同,其中只有一个重量异常(假球),现在要求用一部没有砝码的天平称三次,将那个重量异常的假球找出来,并且分辨假球是偏重还是偏轻。
这个题目已经讨论过多次,答案不难检索到。但是因为解法步骤的描述过于繁琐,即使查到了答案往往也看不明白。例如@C爪机留名C 兄的帖子《完美终结12球1异常》(http://tieba.baidu.com/p/3931300028)中,叙述已经相当清晰完整了,但后面仍然有许多跟帖质疑者,而质疑的主要原因就是“没看清”。
所以我想改个叙述方式,不去直接叙述解法步骤,而是把解法的思路分解为若干较小的要点,按先简后繁的次序来分别解释,或许会容易理解一些?
首先,先列出以下结论,各位不妨先分别想想这些结论对不对,后面我再解释:
一、如果预先知道假球的轻重,那么
(1) 称1次,可以从3个中挑出假球。
(2) 称2次,可以从9个中挑出假球。
(3) 称3次,可以从27个中挑出假球。
推而广之,称N次,就可以从3^N个球中挑。
二、如果虽不知道假球的轻重,但知道:“假如假球在某几个中则假球为轻,否则假球为重”,那么同样
(1) 称1次,可以从3个中挑出假球。
(2) 称2次,可以从9个中挑出假球。
(3) 称3次,可以从27个中挑出假球。
同样,称N次,就可以从3^N个球中挑。
三、如果完全不不知道假球的轻重,且要求在挑出假球时能得出它是轻还是重,那么:
(1) 称1次,只可以从1个中挑。
(2) 称2次,可以从4个中挑。
(3) 称3次,可以从12个中挑。
下面,再解释这些情况下的具体做法。
(待续)


IP属地:陕西1楼2017-02-07 17:26回复
    (续)
    下面,依次解释上述各种情况下的具体做法。
    下面所述的步骤中,有些地方需要借用“标准球”来做比较。这一点,在这个问题的大背景中显然是可以的。例如下面的“三(2)”,既然已经断定假球就在这四个中,那么这四个以外的球都是可以用作标准球的了。
    一、预先知道假球的轻重,那么:
    每称一次时,把准备挑的球分成三等分,两份放在天平两边,一份留在旁边。结果有三种:左边重、右边重、两边平。就可以把需要挑的范围缩小到原来的三分之一了。所以:(1) 称1次,可以从3个中挑;(2) 称2次,可以从9个中挑;(3) 称3次,可以从27个中挑。
    二、虽不知道假球的轻重,但知道:“假如假球在某几个中则假球为轻,否则假球为重”的情况(为便于叙述,我们称不可能偏轻只可能偏重的球为A类;称不可能偏重只可能偏轻的球为B类):
    同样把准备挑的球分成三等分,两份放在天平两边,一份留在旁边。
    但是分组时需满足要求:或者,使天平两边全同是A类或全同是B类,或者,使天平左边的A类球与天平右边的A类球一样多,天平左边的B类球与天平右边的B类球一样多。如下图示意。
    不难证明,这种分法一定是可以做到的。
    于是,称后如果两边平,假球就在留在天平外的那一组中;如果左边重,假球就在左边的A类球和右边的B类球中;如果右边重,假球就在右边的A类球和左边的B类球中。如下图示意。

    这样,同样可以吧需要挑的范围缩小到原来的三分之一了。
    (待续)


    IP属地:陕西2楼2017-02-08 22:26
    收起回复
      (续)
      三、如果完全不不知道假球的轻重,且要求在挑出假球时能得出它是轻还是重,那么:
      (1) 称1次,只可以从1个中挑。
      ——已经知道这一个是假球,称一次只不过是拿它和一个标准球比较一下。即可。
      (2) 称2次,可以从4个中挑。
      ——分成3、1两组,将这三个和另外三个标准球称一次比较。若不等重,则假球就在这三个中且已经知道轻还是重,下一步按照上面“一(1)”即可。
      ——若这三个和标准球比较后等重,则假球就是这另一个,下一步按“三(1)”即可。
      (3) 称3次,可以从12个中挑。
      ——分三组:4,4,4。两份放在天平两边,一份留在旁边。
      ——如果称后两边平,假球就在留在旁边的那一组4个中。于是按照上面的“三、(2)”,再称两次就可以了。
      ——如果称后两边不平,则假球就在天平上的8个中,且已经知道有4个属于A类,有四个属于B类。于是按照上面的“二、(2)”,再称两次就可以了。上面的“二、(2)”可以从9个中挑,现在只有8个当然更可以了(例如可以配上一个标准球,还可以有别的灵活做法)。
      完了。怎么样?
      (待续)


      IP属地:陕西3楼2017-02-08 22:28
      收起回复
        (续)
        再补充说明一点:
        上面的具体操作,某些情况有灵活的余地,所以不同人给出的具体答案可以有细节差别。
        例如,
        上面的“三、(2)”,“称2次从4个中挑”的操作,
        除了上面所说的“分成3、1两组,将这三个和另外三个标准球称一次比较”以外,
        也可以将这三个,添上一个标准球,分放在天平两边各两个。如果平,同样说明假球就是另一个;如果不平说明假球在这三个中,且知道了其中两个或一个是A类,一个或两个是B类,下一步按照上面“二(1)”即可。


        IP属地:陕西4楼2017-02-08 22:38
        回复
          赞一个


          星座王
          点亮12星座印记,去领取
          活动截止:2100-01-01
          去徽章馆》
          IP属地:上海来自iPhone客户端5楼2017-02-08 22:42
          回复
            问题在于两次机会称9个球对吧,我验证过125,346这个方案可行,并且最糟糕方案也可得出异常球并得出轻重,让我验证验证你的,如果我看懂了的话应该是这样的


            来自Android客户端12楼2017-02-08 23:44
            回复
              如果按8+1做法
              那么无法得出轻重球啊
              3/3/3
              3/3平
              1/1无法得出


              来自Android客户端13楼2017-02-08 23:46
              回复
                上面是要求将那个重量异常的假球找出来,并且分辨假球是偏重还是偏轻。
                下面再说一下不要求分辨假球是偏重还是偏轻的情况。
                如果降低要求,只要求挑出来,不要求分辨假球是偏重还是偏轻,那么显然上面所述的各种情况,只有“三”可以再放宽。
                具体做法:在上述做法中,一律可以多一个球,多的这一个分在天平外面,就可以了。上述步骤完了后如果别的球都不是,就是这一个了。所以
                (1) 称1次,可以从2个中挑。
                ——拿其中一个和一个标准球比较一下。即可。
                (2) 称2次,可以从5个中挑。
                ——分成3、2两组,将这三个和另外三个标准球称一次比较。若不等重同前面,若等重,则假球就在这另2个中,下一步按上面“(1)”即可。
                (3) 称3次,可以从13个中挑。
                ——分三组:4,4,5。两份4放在天平两边,一份5留在旁边。若不等重同前面,若等重,则假球就在这另5个中,下一步按上面“(2)”即可。


                IP属地:陕西15楼2017-02-09 09:44
                回复
                  那么楼主的结合方案是?请分步奏说明,如
                  4/4/4
                  4/4左重于右
                  左重于右125/346 7/8
                  1/2平则6轻
                  左轻于右
                  测3/4

                  则5轻
                  其余重则重


                  来自Android客户端21楼2017-02-09 11:30
                  收起回复
                    @4869之徒 兄:
                    不太清楚您上面所问是什么意思。我已经给您回复数次,都被删了,估计是因为这个题目属于重复题。以前已经讨论过多次,我的回复看来也属于重复内容了。
                    所以,您如还有不明白之处可搜一下以前的帖子就行了。


                    IP属地:陕西28楼2017-02-09 13:50
                    回复
                      十二球问题有多种解法,这种方法你归纳的很好


                      IP属地:四川来自Android客户端30楼2017-02-10 00:38
                      收起回复
                        @VENTURE妄言


                        IP属地:上海来自Android客户端32楼2017-02-13 16:32
                        回复
                          朝闻道,夕死可矣


                          IP属地:上海来自Android客户端33楼2017-02-13 16:42
                          回复
                            之前没看到@,推了之后才看到。
                            可能推的人没有仔细看这个帖子。按照原题的意思,是没有外带的标准球的,而楼主的意思,有外带的标准球,这不是标准的12球问题。
                            假如考虑外带标准球,称3次是可以从13个中挑的。称N次可从(3^N-1)/2个中挑。


                            IP属地:广东来自Android客户端35楼2017-02-13 17:48
                            回复
                              复35楼@C爪机留名C 兄:
                              看来,我上面的措辞是有不够清楚严密的地方,造成误解。
                              我的原题,并非“有外带的标准球”,仍然是:“标准的12球问题,没有外带的标准球”。
                              虽说,我上面的叙述中有几个地方(如三(1)及三(2))用了标准球,但这些标准球并不是12个以外的,而只是“假球嫌疑范围以外”。所以总的这一个大题目(标准的12球问题)中,并没有使用“外带的”标准球。
                              不过,我上面的措辞,似乎这9个问题都是各自独立的,没有明确表示出我的这几个地方只是这个大题目里的一个局部,一个“子问题”。所以会引起误解。
                              特别是这9个小题目中有超出“12球”范围的,更容易让人误解觉得我不是在叙述“ 大题目里的子问题”。这属于我措辞不当。
                              虽说2楼开头有点解释,但显然解释得还不太理想。如能把措辞整理一下,或许更好?
                              (待续)


                              IP属地:陕西44楼2017-02-14 01:13
                              回复