确实可以三次完成。
羽扇仙的答案(不管是自己写的还是从哪里抄的)的确是对的。我在草稿纸上画了一个树形图从头到尾仔细分析了过了。
要我在半小时之内验证一个答案是否正确这没什么问题。但是要我自己想出这样一个解答,我自认为在一个小时内难以完成。至于要想出一个比之更好的解答,我对此不作奢望。
所以我只是谈谈感想,简单评论一下。
最初一秒钟确实会想把12分成两个6,但是马上就意识到是不行的(居然还有那么多人提交了这种答案,有点小小的吃惊);然后就想按照分3组的方式进行下去,仔细一做才发现三次不行;接着猛然想到虽然一开始不知道这个次品的轻重,但是可以记录每一次的结果,利用这个,说不定就可以控制正在三次以内呢?做了一下,做成了,高兴了不到一分钟,发现弄错了——我做成的其实是9个砖头的情况。(回想一下,大概是受到了简单的迭代递归的思维习惯的影响)
于是又要重新做,发现按照通常的做法,12个砖头,第一称如果相等,接下来的各种分支都很容易,而且也都在3次以内;但是倘若第一称不相等,就不好办了。头脑清楚,并且说必须要四次才行的人,估计都是在这里卡住了。但是许多时候,即使我们至今为止没有找到任何可行的方法,也并不就因此证明了不存在任何可行的方法。关于一件事的可行性或者不可行性的证明当然也是有的;但是可惜的是,在这里那些说三次不可行的人并没有真的证明不存在任何可行的方法。
于是我把羽扇仙的答案认真地看了一下,我想既然写得这么详细(虽然繁琐),此人肯定是花费了一番心思验证过的,不要无视人家的劳动成果(我看的时候并不清楚这是不是抄的)。确实,这个答案比较繁琐,但是比起那些只有一两句没头没脑的答案来说,这实在好得太多了。对那些自己随随便便就写出一个想当然的答案、也没有耐心看完其他解答的人,我想说的是:这种工作是来不得半点浮夸的;真要是能证明,就应该能够把详细过程写出来,同时也要有耐心看这样的详细工作。(当然,如果不在乎这些,没有耐心也没关系,那就把这些当过眼烟云吧,以玩票的态度来对待吧,反正也不是自己本职工作,也不是当什么论文审核人。)
再回到羽扇仙的答案。一批人望而却步是因为没有耐心。另一些人可能看到了中间就看不下去,大概由于排版上的某些问题影响了阅读吧。而且通篇这种刻板的“如果...则...否则...”的方式看起来恐怕也相当倒胃口(对这些东西已经习以为常到麻木的程序员们就不会觉得倒胃口,这也许是因为有更深层次的审美,也许是因为已经没有胃口可倒了)。题目本身的难度和解答本身的繁琐也许是更大的原因:在第一称不相等的这个分支,其解法固然是对的,但是很不直观,需要看的人自己去慢慢理顺(最好是画个树形图来分析)。这里我就不写出来了。既然楼主已经知道三次是可能的,必定是验证过的,我也不用多费笔墨唇舌。对于其他看官来说,我要是写得不够详细,那还不如看原来的解答;写得太详细又嫌罗嗦。正确答案其实早就在那里。要是有心的话,与其花时间看我写的,不如自己去花时间理顺一遍,这并不需要什么过人的创造力,需要只是细致和耐心(我相信能从开头看到这里的人已经非常有耐心了)。
真正有些原创性的可能还是xiaozhu36955的解答。虽然我第一眼也对其不屑一顾,第二眼就知道其解答不符合“题意”,就像pjw258所说,对跷跷板的次数进行了“非法”的使用(如果按照“正确”的使用方式,也就是我们解这道题时所默认的那种使用方式,xiaozhu36955的解答当然是无法保证在3次以内的,只能保证在6次以内(运气好的话只要2次,运气差就要6次))。然而这个解答成功地跳出了我们默认的框框,进行了创造性地发挥。虽然要想到羽扇仙那个答案也需要突破许多束缚,但是二者不是在同一个层面上的突破。其实如果真要在现实场景中去找那块重量异常的砖头,我还宁愿用xiaozhu36955的方法,简单易行;而羽扇仙的方法固然称的次数少,但是在称之前和称之后脑子里都要绕好多弯弯,还要记录称的结果,不断回顾与比较,有这闲工夫,早就用xiaozhu36955的方法(或者其他笨办法)找到那块砖头了。(但是假如任务不是称砖头,而是称成吨的钢材,花点时间思考怎样尽量减少称的次数以降低成本还是很有实际用途的;又比如还是称砖头,但是不是一次性的,而是每一批货都要检查重量异常的砖头,那么第一次花点时间想出最少称重次数的方法,将之程序化,以后就方便了。)
给我两天时间,我会给出解答。如果两天后我没有提供任何解答,或者给出的解答是错误的,那就把分数给pjw258吧。
在给出我的解答之前,先简要评论一下这些天来新出现的四种解答。
新出现的解答有:
1、QQ850912617(以下简称QQ同学)——第一次5:5
2、姜胖大人——第一次4:4;不相等的话,第二次称就把其中一边的4个平均分成两份分别放在跷跷板两边,另一边的4个取两个分别放在跷跷板两边
3、278102649(以下简称27同学)——第一次4:4;不相等的话,第二次称就把左右各拿走一个,并把左右各取一个对调
4、1645425——力矩平衡大法
最后这一种虽不是标准解法,但是正因如此,才显得很有意思。我忍不住要把1645425称作物理小王子了,希望你再接再厉,发明出更多更新奇的物理称法。
第一种和第三种称法都是称不出来的。实际上,在掌握了下面我给出的一般方法之后(是的,我给出的是一般方法,这个方法适用于所有使用天平在n个砖头中找出唯一那个次品的问题),就很容易看出,在12个砖头中寻找1个次品,如果限定三次之内完成,那么第一次称只能是4:4,每一边的个数既不能大于4,也不能小于4。所以QQ同学在第一次称重的时候就注定了不可能三次完成。而27同学的失误则发生在第二次称重,不是“好像还差一点”的问题,如果你不改变第二次称重方案的话,永远也不可能在三次以内完成。这些都可以按照我给出的方法得到证明。
姜胖大人的方法是可以做出来的,不过存在细节上失误。大人原话是这样说的:“假设第一次左边,即1234重,那么第二次称127和348。如果平衡,那么异常球在56里且轻;如果还是左边重,那么异常球在128里且为重;如果右边重,那么异常球在347里且为轻”。仔细分析就会发现,如果左边(或右边)重,那么只能说异常球在128里(或在347里);加上“且为重(且为轻)”不仅是画蛇添足,而且是错的。(当然,平衡的情况下说“异常球在56里且轻”是正确的。)如果抛开这些失误,那么姜胖大人的方法是唯一一种这样的方法,即:在第一次称重不平衡的情况下,第二次称重不需要借助这8个砖头之外的任何砖头(即第一次称之后已被证明为正常的那4个砖头)。
当然,楼主见过的2种不同方法,其中一种大概是和姜胖大人一样的。
以下是我的解答:
先别急着动手。在做之前,先分析一下称重的作用。每一次称重的作用无非是令我们排除一些可能,缩小搜索范围,判断出重量异常的那个次品在哪个范围内,并确定下一步该如何称。而做到这一点,仅仅是通过观察称重的结果。每一次称重的结果最多有三种可能:左>右;左=右;左。其中X是U的子集,表示经由前面所有步骤判断出那个异常元素所属的范围;Y则表示A:B这样一个称重操作,其中A、B都是U的子集,且A与B没有交集,而且A和B的元素个数要相等(我们不知道正常与异常砖块的重量比,也不使用力矩称法,所以只能在跷跷板两边放置同等数量的砖块)。而每个叶结点对应U的一个子集,并且是单元集(即只含有一个元素的集合),叶结点上不再需要称重操作,因为已经确定异常元素是哪一个了。以后,在不会引起歧义的地方,我们直接把某个结点对应的判断和操作简称为判断和操作。我们还要给每条线都标上=∧∨这些记号。它们表示这条线上端那次操作的结果,如果上端那个操作是A:B,那么=∧∨分别表示g(A)=g(B),A∧B,A∨B。标注着不同记号的线导向相应的下端判断或操作。从现在起,我们有时也称一棵树为一个策略。
我们在前面说过,如果一次称重之前不存在至少一次不相等的称重结果,那么此次称重最多只能分出两种可能;否则,最多能分出三种可能。也就说,如果在一个结点之前,还不曾有过某条线(这条线不一定是紧接着这个结点的,但是必须能够经由这个结点向上通达到)被标记为∧或∨,那么这个结点的分支数最多两条;否则分支数最多三条。现在我们按照这一规则,从一个根结点开始向下分叉,并且使得深度不超过3。将每个结点下面的分支数目以及树的深度最大化,就得到下面的树形图。
这棵树的叶结点一共14个,但是从14个砖头里找到一个重量异常砖头的任务是不可能确保在三次内完成的,因为还需考虑以下限制。
如果只关注每个结点处的判断集合,即判断异常砖块所属的那个集合,那么下面几项条件限制着每个结点上集合(但没有穷尽所有限制)。
首先,一个策略的叶结点必须都是单元集,否则这个策略还是未完成的;
其次,一个结点上的集合恰好分割成它的子结点上的集合,即:一个结点的子结点上的集合互不相交,并且这些子结点对应集合的并集就等于该结点上的集合;
第三,一个结点下方所有叶结点的个数必须等于该结点对应集合的基数(即它的元素个数)。
(第三点可由前两点推出)
我们看到图中这棵树的根结点向下分为两棵子树,左边的子树有5个叶结点,右边的子树有9个叶结点。根结点上的集合就是U(就是任务开始时所给砖头的集合),而根结点上的操作则是A:B,其中A和B都是U的子集,且互不相交。根结点向下分出两支,分别对应着A=B时的操作和A∧B时的操作。若A=B,则异常砖块一定不在A或B当中;因此,在A=B这一分支下的子结点上的集合等于U-(A∪B)。若A∧B,则异常砖块一定在A或B当中;因此,在A∧B这一分支下的子结点上的集合等于A∪B。由于A和B的基数相等,假设A的基数为a(a为正整数),则A∪B的基数就等于2a。因此,右边子树下的叶结点数目必须是偶数。有了这个限制条件,且又知道深度为3的树的右边子树的叶结点最多有9个,于是我们知道右边子树的叶结点最多有8个。8和左边子树的叶结点数目5相加就是13。这就证明了不存在三步以内的策略,能够将大于等于14个砖块中的异常砖块找出来。
由上面的设定还可以知道,若U的基数为w,则U-(A∪B)的基数为(w-2a)(因A的基数是a,且A和B基数相同),也就是左侧子树的叶结点数要等于w-2a,且由于深度不大于3的树左侧叶结点数最多是5,于是w-2a≤5;类似的,右侧子树的叶结点数要等于2a,且由于深度不大于3的树左侧叶结点数最多是9,于是2a≤9。解出来就是(w-5)/2≤a≤9/2。若w=12,则a只能为4(若w=13,a也只能为4)。
(未完待续。抱歉,今天拉肚子,不然现在就写完了。上面已经证明的结论:在n块砖里找出一块异常砖头,且能够保证在三次以内完成的,n不能大于13;当n=12,第一次称重必须为4:4。明天将证明:n=12时,有10种方案可以3次完成;n=13时,有12种方案可以3次完成。我相信根据我上面给出的线索,已经有很多人知道该怎么做了。)