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

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

只看楼主收藏回复

(续)
假如就是无条件允许外借标准球的话,那么@C爪机留名C 兄说得对:称3次,不止可以从12个中挑,而是可以从13个中挑。
从上面可以看到:“三(3)”中,如果称后两边不平,则假球就在天平上的8个中。但是“二、(2)”可以从9个中挑,从这里看还有一个余地。只不过9是奇数,无法分成两半比较。所以才只能拿8个称。
如果无条件允许外借标准球的话,那就好办了,
——将13个分成两组:9,4。将9个放在天平一边,另一边用外借的9个标准球。称一次。
——如果称后两边平,同前。
——如果称后两边不平,则假球就在这9个中,且已经知道轻还是重,接着按照上面“一(2)”,再称两次就可以了。
上面的方法要借用9个标准球,如嫌借太多,也可如下,只借一个:
——将13个分成三组:5,4,4。将5个放在天平一边,另一边放4个再加一个外借的标准球。称一次。
——如果称后两边平,同前。
——如果称后两边不平,则假球就在天平上的9个中,且已经知道有5个属于A类4个属于B类,或者4个属于A类5个属于B类。于是按照上面的“二、(2)”,再称两次就可以了。


IP属地:陕西46楼2017-02-14 02:08
回复
    (再补充几句)
    我前面的措辞不太恰当之处,主要是顶楼以及三楼中的“三(1)、(2)、(3)”。其中(1)、(2)都允许使用标准球,而只有(3)不允许,这主要是我把(3)当成了“大题目”而把(1)、(2)当成“子问题”了。但文字中又没有交代清楚。
    假如换一种叙述,全都采用同样的条件:都允许使用标准球,那么问题或许更加规整。采用数学归纳法,就可以推导出上面C爪机留名C 兄给出的公式(3^N-1)/2。
    然后不难证明:不允许使用外单的标准球,则总球数需减1;不要求最后得出轻重,则总球数可加1.
    这些,@C爪机留名C 兄在帖子《完美终结12球1异常》(http://tieba.baidu.com/p/3931300028)后面的跟帖69楼中,都已经有叙述了


    IP属地:陕西48楼2017-02-14 02:57
    回复
      确实如此。原来三(1)(2)只是(3)的两块拼图,不能独立为题。
      主楼一开始的表述可谓是相当不妥。特别是又放在开篇…怎么看都有问题。应当说:
      “三、如果完全不知道假球的轻重,且要求在挑出假球时能得出它是轻还是重,那么:
      (1) 称1次,可以从0个中挑。
      (2) 称2次,可以从3个中挑。
      (3) 称3次,可以从12个中挑。
      四、完全不知道假球的轻重,但有一额外标准球,要求在挑出假球时能得出它是轻还是重,那么:
      (1) 称1次,可以从1个中挑。
      (2) 称2次,可以从4个中挑。
      (3) 称3次,可以从13个中挑。”
      尽管废话了一些,但是明晰了。
      从这个角度解这题的话,二三四往复相互借用,把数字往上累,就可以推广到N了。


      IP属地:广东来自Android客户端49楼2017-02-14 03:03
      收起回复
        把我原帖69楼的重要部分转一下……
        对于任意n∈N+且n≥2,
        ①有(3^n-3)/2个球特征相同,其中只有1个重量异常,现在要求用一部没有砝码的天平称n次,将那个重量异常的球找出来,并说明它比正常球重了还是轻了;
        ②有(3^n-1)/2个球特征相同,其中只有1个重量异常,现在额外提供1个正常球,要求用一部没有砝码的天平称n次,将那个重量异常的球找出来,并说明它比正常球重了还是轻了;
        ③有(3^n+1)/2个球特征相同,其中只有1个重量异常,现在额外提供1个正常球,要求用一部没有砝码的天平称n次,将那个重量异常的球找出来。
        当然,这些特殊值是称量次数加多一次的分界线,对于任意n个1异常,则…比如对于①问,只要(3^a+1)/2<n≤ (3^a+1)/2,a∈N+那么就要称a+1次。(②③类似)


        IP属地:广东来自Android客户端50楼2017-02-14 03:13
        回复
          然后贴一下我的k球1异常称n次出通解…可能不是最好的、还有提升空间。
          好像贴过好几个地方了…希望总是看到的人不会感觉“诶这人咋这么烦”,哈哈。
          先上几个显然的结论:
          1.n次称球上限是k(n)=(3^n-3)/2个球,k可以做,小于k显然可做,故只需考虑k(n)个球的情况。
          2.对于一有轻嫌疑的球与一有重嫌疑的球,可将两者捆绑,视作一有异常嫌疑的二倍球,对于一堆二倍球应用一倍球的找异常并分轻重称量方案,可以找出被捆绑的异常一倍球并分轻重。这种方法不妨称为“捆绑”。
          3.对于一个找出异常并分轻重的称量方案,不存在每一次称量都平的可能。对于此方案,如再加一轻/重嫌疑球(此球倍数不作要求)而不称此球,若得到每一次都平,则此球为轻/重球。这种判别法不妨称为“全平”。
          具体方法:
          ————————————————
          首先做k(n)+1球中1异常,附1标准球,称n次可找出异常并分轻重的方案。(n≥2)
          ——————
          1)n=2时,对于4球,附1标准球,称2次可出是显然的。
          2)n>2时,假如对于k(n-1)+1球,附1标准球,称n-1次可出。则对于k(n)+1球:
          先分为k(n-1)+2,k(n-1)+1+1标,k(n-1)+1三份;
          对前两份进行称量:
          若平,则对第三份应用k(n-1)+1方案;
          若不平,则在第一份中取出一球*,取走第二份中的标准球,对剩下的球进行捆绑并应用k(n-1)+1方案,球*使用全平判别。
          于是,对于k(n)+1球,附1标准球,称n次可出。
          ——————
          综上,归纳得到k(n)+1球中1异常,附1标准球,称n次可找出异常并分轻重的方案。(n≥2)
          ————————————————
          现在来做k(n)球,称n次可找出异常并分轻重。(n≥2)
          ——————
          1)n=2时,对于3球,称2次可出是显然的。
          2)n>2时,有:对于k(n-1)+1球,附1标准球,称n-1次可出。则对于k(n)球:
          先分为三份k(n-1)+1;
          任取两份进行称量:
          若平,则从一二份中任取一球作标准球,对第三份应用k(n-1)+1方案;
          若不平,则从第三份中任取两球捆绑作二倍标准球,然后对一二份进行捆绑并应用k(n-1)+1方案。
          ——————
          综上,即k(n)球中1异常,称n次找出异常并分轻重的解法。(n≥2)
          后面的k(n)+1已经内含于k(n)中,而k(n)+2不分轻重其实就是k(n)+1加一个“全平”判别。也都是很明显的东西了。


          IP属地:广东来自Android客户端51楼2017-02-14 03:14
          回复
            附一下两道升级称球题、
            1.16球,2等重异常,称5次出。
            2.16球,2异常,1比标准轻,1比标准重,称5次出。
            称球题还有许许多多拓展…就记得的先放这俩(其实可以算是一样的)。不过不管条件怎么变,有些东西万变不离其宗。


            IP属地:广东来自Android客户端52楼2017-02-14 03:22
            收起回复
              我推送了吧广播,大家看看在客户端能收到吗


              星座王
              点亮12星座印记,去领取
              活动截止:2100-01-01
              去徽章馆》
              IP属地:上海来自iPhone客户端53楼2017-02-14 16:11
              收起回复


                IP属地:山东来自iPhone客户端54楼2017-02-15 14:57
                回复
                  火钳?


                  来自Android客户端55楼2017-02-15 23:19
                  回复
                    受益匪浅


                    来自Android客户端56楼2017-02-25 00:05
                    回复
                      这个会不会是,一个方法最大几率能测出来,而不是百分百,就是同样的方法测试,然后打乱,在测试在打乱。
                      100次有90次是准确的。
                      有方法可以百分百准确吗


                      IP属地:广东来自Android客户端57楼2017-03-14 21:10
                      收起回复
                        这个理解很详细,但我只是想知道如何测第三种:12分三,1234重于5678,测125和346,就算测出125重于346,那怎么得知是125中有重的球还是346中有轻的异常球呢


                        来自Android客户端58楼2017-04-05 14:46
                        收起回复
                          【接受上面@C爪机留名C 兄的意见,将上述归纳全文改写如下】
                          十二球问题解法思路的条理化归纳
                          【前言】
                          十二球问题是:有十二个乒乓球特征相同,其中只有一个重量异常(假球),现在要求用一部没有砝码的天平称三次,将那个重量异常的假球找出来,并且分辨假球是偏重还是偏轻。
                          这个问题还有几种变形题(假球存在的范围比12个再增加):
                          变形一:最后只要求挑出假球,不要求判定假球是偏重还是偏轻。
                          变形二:操作过程中,允许在“嫌疑假球”的范围之外,借用标准球来作比较。
                          这个题目已经讨论过多次,答案不难检索到。但是因为解法步骤的描述过于繁琐,即使查到了答案往往也看不明白。可以看到网上讨论的话题中,前面叙述已经相当清晰完整了,但后面仍然有许多跟帖质疑者,而质疑的主要原因就是“没看清”。
                          所以这里打算改个叙述方式,不去直接叙述解法步骤,而是把解法的思路分解为若干较小的要点,按先简后繁的次序来分别解释,或许会容易理解一些?
                          (待续)


                          IP属地:陕西59楼2017-04-12 11:29
                          回复
                            (续)
                            【先列出几个结论】
                            首先,先列出以下结论,各位不妨先分别想想这些结论对不对,后面我再解释:
                            说明:下文中所谓“从×个中挑”,意为已知假球就在这×个中。也就是说×就是开始时“嫌疑假球”的个数。
                            一、如果预先知道假球的轻重,那么
                            (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次,可以从13个中挑。
                            推而广之,称N次,就可以从(3^N-1)/2个球中挑。
                            四、如果同情况三,但操作中不允许借用已知假球范围以外的标准球来做比较,那么允许的开始时“嫌疑假球”的个数比情况三减一,即:
                            (1) 称1次,可以从0个中挑(即不可以完成)。
                            (2) 称2次,可以从3个中挑。
                            (3) 称3次,可以从12个中挑。
                            也就是说,称N次,就可以从(3^N-1)/2-1个球中挑。
                            五、如果同情况三(或情况四),但已知条件中并不肯定“嫌疑假球”范围内有一个假球,而是最多有一个,也可能没有。要求是:如果有一个则得出情况三(或情况四)要求的结果,如果没有假球则判断出没有,那么,允许的开始时“嫌疑假球”的个数仍然同情况三(或情况四)。
                            六、如果同情况三(或情况四),但最后只要求挑出假球,不要求判定假球是偏重还是偏轻,那么允许的开始时“嫌疑假球”的个数比情况三(或情况四)加一,即:
                            (1) 称1次,可以从2个(或1个)中挑。
                            (2) 称2次,可以从5(或4个)个中挑。
                            (3) 称3次,可以从14(或13个)个中挑。
                            也就是说,称N次,就可以从(3^N-1)/2+1个(或(3^N-1)/2个)球中挑。
                            上述情况“四(3)”,就是我们基本的“12球问题”,而情况“三(3)”、“六(3)”,就是上面说的本题目的变形。
                            下面,再解释这些情况下的具体做法。
                            (待续)


                            IP属地:陕西60楼2017-04-12 11:36
                            回复
                              (续)
                              【情况一】
                              预先知道假球的轻重,那么:
                              每称一次时,把准备挑的球分成三等分,两份放在天平两边,一份留在旁边。结果有三种:左边重、右边重、两边平。就可以把需要挑的范围缩小到原来的三分之一了。
                              所以:(1) 称1次,可以从3个中挑;(2) 称2次,可以从9个中挑;(3) 称3次,可以从27个中挑。
                              称N次,就可以从3^N个球中挑。
                              【情况二】
                              虽不知道假球的轻重,但知道:“假如假球在某几个中则假球为轻,否则假球为重”的情况(为便于叙述,我们称不可能偏轻只可能偏重的“嫌疑假球”球为A类;称不可能偏重只可能偏轻的“嫌疑假球”为B类):
                              同样把准备挑的球分成三等分,两份放在天平两边,一份留在旁边。
                              但是分组时需满足要求:使天平左边的A类球与天平右边的A类球一样多,天平左边的B类球与天平右边的B类球一样多。如下图示意。
                              不难证明,这种分法一定是可以做到的。
                              于是,称后如果两边平,假球就在留在天平外的那一组中;如果左边重,假球就在左边的A类球和右边的B类球中;如果右边重,假球就在右边的A类球和左边的B类球中。如下图示意。

                              这样,同样可以吧需要挑的范围缩小到原来的三分之一了。
                              所以同样:称N次,可以从3^N个球中挑。
                              (待续)


                              IP属地:陕西61楼2017-04-12 11:45
                              回复