标题: 天平称球 [打印本页]
作者:
天宫公主 时间: 2008-9-25 18:43 标题: 天平称球
一共有１２个球，其中一个重量和别的不同（但事先不知道是比别的轻，还是比别的重）。
１。在一个天平上称三次，找出那个“坏球”。
２。证明：无论如何都不能只用两次称出坏球。
作者:
墨叶 时间: 2008-9-26 08:12
我先证明结论2（因为没证明过，想知道这种证明方法是否合理）。
坏球是12个球中任意一个，共12*2=24种可能。
每次称量只有3种可能，2次称量为3*3=9<24，所以不可能。
作者:
小女秦怜月 时间: 2008-9-26 12:11
1、假设球是1、2、3、4、5、6、7、8、9、10、11、12
先称1234和5678，如果平，说明有问题的球在9-12里，称1、2、3和9、10、11，如果还平，12有问题。如果9、10、11沉，说明有问题的球在9-11里，而且比正常球重，称9、10，平的话11有问题，不平的话重的那个有问题。（如果第二次称9、10、11轻，同样方法，只不过是轻的有问题）
如果1234和5678不平，说明问题球在1-8里。假设左边比较沉。第二次称1、6、7、8和5、9、10、11，如果右边比较沉，说明问题在6、7、8里，而且问题球比较沉。称6、7，如果不平，沉的是有问题的；如果平，8有问题。如果第二次称的时候左边沉，说明1或5有问题。第三次称1、2，如果不平，1有问题。如果平，5有问题。如果第二次称的时候是平的，那么问题球在2、3、4里，而且比正常球沉。第三次称2、3，如果不平，沉的有问题。如果平，1有问题。
2、因为3^2=9<24。而3^3=27>24，所以最少要称3次。
作者:
北风烟雪 时间: 2008-9-26 18:18
基本就是上面两位的意思
12个中选出特别一个，信息熵为H=log12
一次称量可以提供的熵为H=log3
log12〉2log3
故2次无论如何不能解决该问题
作者:
茅延安 时间: 2008-9-26 18:52
总数为13个球呢?能3次称出么?
作者:
Z_Artemis 时间: 2008-9-26 19:13
http://www.xycq.net/forum/viewth ... 1998&highlight=
冠子发过这题的
作者:
天宫公主 时间: 2008-9-26 19:45
３楼，４楼答案正确。
５楼想法不错，但最好解释一下信息熵和本命题的关系。例如：引理－残余信息熵 > 0，则如何如何．．．
作者:
北风烟雪 时间: 2008-9-27 09:05
http://topic.csdn.net/t/20020623/20/824734.html
http://www.quzhi.net/chinese/pdf/algo_analysis.pdf
上面两个链接对这个问题有比较详细的回答。
至于信息论，详细说起来会有好大一段，有兴趣的朋友可以找找相关的资料，这里就不说了~
作者:
crayfish 时间: 2008-9-27 14:43
明白楼主命题2的意思，但是是否描述有问题
2次找到坏球的可能性是存在的，但是2次不能保证一定能找到坏球，
准确的描述应该怎么说呢？
取2个球，第一次2球等重，将其中一球换掉，第二次不等，则坏球被找出来了
作者:
茅延安 时间: 2008-9-27 19:12
6楼被无视了...
因为3^2=9<24。而3^3=27>24，所以最少要称3次。
如果这就是依据的话
对于13来说,同样有3^2=9<26, 3^3=27>26
是否意味着13个球一样可以在3次内称出呢?
试了下好像不行.
作者:
天宫公主 时间: 2008-9-28 11:22
crayfish：不好意思，第二问当然是指在所有情况下，都能在两次内称出坏球。
茅延安：决定１３个球是否能在三次内被称出来。。。这个问题很有意思，大家继续讨论。
北风烟雪：哦，其实我想说的是，当一个东西的残余信息为 I 的情况下，对它随便猜一下就能猜中的概率是 p = e^-I （从 I = -log p 得出）。那么当且仅当残余信息等于 0 的情况下，“随便一猜”才必然是正确的结果。
作者:
炎帝瀑布碎 时间: 2008-9-28 11:29 标题: 回复 #11 茅延安 的帖子
13个球肯定可以，不过不知道为什么
偶去年某道面试题就是13个球………………
作者:
墨叶 时间: 2008-9-28 16:18
13个球可以找到坏球，但是有一定几率不能判定球的轻重。
如果能额外提供一个好球，则可以判定球的轻重。
应该是这样了。
作者:
水泊船夫 时间: 2008-9-28 18:24
有一种情况可以两次称出12个球中重量不同的一个球
第一步把球分三组 第一组5个 第二组5个 第三组2个
称第一组和第二组 如果重量相等答案就是第三组中的一个是不同的 第2次称第三组就能得出答案 不过概率比较小,不过并非不可能
作者:
靖天 时间: 2008-9-28 19:25
LZ的問題出現過多次
6樓茅大哥的問題倒挺感興趣
13球的個案應該是可解的
但有些情況會不知道壞球輕重
如果一開始知道壞球輕重
那13球就很容易解決了
作者:
茅延安 时间: 2008-9-28 21:11
回14楼,问题本身在于"找出坏球",而并不需要指出其"轻重"
例如12球下,当1-4与5-8等重的时候,是无法在3次内确定坏球比好球更轻或是更重的
"13个球可以找到坏球"
希望能给出方案
作者:
茅延安 时间: 2008-9-28 21:23
收回楼上的话.12球下是可以确定坏球轻重的,只是在本题下没有必要,因为题目没有要求
作者:
茅延安 时间: 2008-9-28 21:39
刚想明白,自问自答吧
4/4/5
先比较4和4,如天平不平,则同12球
否则,比较1-3与9-11,平则比较1和12
否则,比较9和10
还是利用4楼的套路.有了套路题就没意思了
.
[ 本帖最后由 茅延安 于 2008-9-28 21:47 编辑 ]
作者:
墨叶 时间: 2008-9-28 22:47
规定：好球均可记为M。
取8个球等分为两组，分别标为 A1，A2 ，A3 ，A4 和 B1，B2 ，B3 ， B4。
比较A1，A2 ，A3 ，A4 和 B1，B2 ，B3 ， B4 的大小；
情况1：若不相等，根据对称性，不妨设A1+A2+A3 +A4> B1+B2+B3+B4 。显然，余下5球为好球。
比较A1+A2+B1与A3+A4+B2 。
若 A1+A2+B1 >A3+A4+B2 。则坏球只能在A1，A2 ， B2 中。
比较A1，A2 ，大者为坏球且坏球大于好球。
相等则 为坏球且坏球小于好球
若 A1+A2+B1 >A3+A4+B2 。方法同上。
若 A1+A2+B1 >A3+A4+B2 。则坏球只能在 B3，B4 中
比较 B3 和B4 ，小者为坏球且坏球小于好球。
情况2：若相等，则坏球在余下的5个球中。记为C1， C2， C3，C4 ，C5。
比较 C1+C2 与C3 +M。
若 C1+ C2≠ C3+M； 比较C1 ，C2 。
若 C1+C2 = C3+M；比较 C4和好球。若C4=M，则C5是坏球，但不能判定轻重。
作者:
墨叶 时间: 2008-9-28 22:58
知道坏球的轻重。称n次能在3^n个球中找出坏球。
不知道坏球轻重。称n次能在1/2（3^n-2）个球中找出坏球并判定坏球的轻重。
不知道坏球轻重。称n次能在1/2（3^n-1）个球中找出坏球但不能判定坏球的轻重。
不知道坏球轻重，且提供一个好球。称n次能在1/2（3^n-1）个球中找出坏球且能判定坏球的轻重。
作者:
龙剑止水 时间: 2008-10-1 19:39
记得Thomas Cover的经典教材《Elements of Information Theory》里讲信息熵的时候就用到了这个例子
作者:
天宫公主 时间: 2009-1-13 01:40
今晚有个朋友又问起了这个问题，讨论中发现了一个很有意思的解：
把 12 个球记为：
002，010，011，021，100，102，111，120，202，220，221，212
第一次:
不称: 002 010 011 021
左盘: 100 102 111 120
右盘: 202 220 221 212
第二次:
不称: 002 100 102 202
左盘: 010 011 111 212
右盘: 021 120 220 221
第三次:
不称: 010 100 120 220
左盘: 011 021 111 221
右盘: 002 102 202 212
每次称完记录结果如下:
一样重: 写 0
左边重: 写 1
右边重: 写 2
三次称完的结果应该是一个含有 0, 1, 2 的三位数。如果你可以在球的编号中找到这个数字，那么那个球的重量就和别的球不一样（而且比别的球重）。如果找不到的话，把这个数字里的 1 和 2 调换一下（以前写１的地方全部改２，以前２的全部改１，例如２２１－＞１１２，１０２－＞２０１），这个数字对应的那个球的编号，该球的重量和别的球不一样，而且比别的球要轻。
作者:
tianxiang011 时间: 2009-2-5 11:58
这个问题前几天同学跟我说过，我想了一个小时想出来的，呵呵
作者:
中庸 时间: 2009-2-23 18:33
假设左边比较沉。第二次称1、6、7、8和5、9、10、11，如果右边比较沉，说明问题在6、7、8里，而且问题球比较沉。
这个应该有问题吧？既然左边已经沉了，那说明1、2、3、4可能大于等于正常四个球的重量但不能确定那个球沉啊。怎么会得出问题球在6、7、8里面，而且正常重？待高人解释！
另外饿觉得这题三次称不出来的，前提是不知道轻重！
作者:
中庸 时间: 2009-2-23 18:36
另外补充一点：在不知道球重量的情况下，如果不通过标准球（也就是正常球）称量比较的话，球的轻重是无从判断的。也可能是饿没开窍！
想明白了，呵呵！
原帖由 小女秦怜月 于 2008-9-26 12:11 发表
1、假设球是1、2、3、4、5、6、7、8、9、10、11、12
先称1234和5678，如果平，说明有问题的球在9-12里，称1、2、3和9、10、11，如果还平，12有问题。如果9、10、11沉，说明有问题的球在9-11里，而且比正常球重 ...
按月月的这个称法称不出来。
[ 本帖最后由 中庸 于 2009-2-23 19:00 编辑 ]
作者:
1234554321a 时间: 2009-10-16 11:09
我老乡出的题都有点意思
作者:
KYOKO 时间: 2009-10-16 14:55
是不是脑子简单了点，越看越头大
作者:
墨叶 时间: 2009-12-13 23:13 标题: 回复 #22 天宫公主 的帖子
对这个解法很感兴趣。
有原理不，若有，希望能说明一二。谢谢。
大致明白了。
[ 本帖最后由 墨叶 于 2009-12-14 15:37 编辑 ]
作者:
天宫公主 时间: 2009-12-14 18:56
也没什么诀窍了，无非是把称球问题转换成进位制问题了。
作者:
墨叶 时间: 2009-12-14 22:29
原帖由 天宫公主 于 2009-12-14 18:56 发表
也没什么诀窍了，无非是把称球问题转换成进位制问题了。
这个能看出来。也能看明白如何找出坏球。
3进制3位数共27个。除去000，还有26个，26/2=13。122和211没有出现。
我在思考选的12个数有什么具体原则。以及如何判断坏球的轻重。
作者:
天宫公主 时间: 2009-12-17 19:53 标题: 回复 #30 墨叶 的帖子
哦，其实是这样的。两个数 abc, def (a - f 代表 0, 1, 2 这三个数字之一)，如果出现 3 | a+d and 3 | b+e and 3 | c+f，则 abc 和 def 称之为孪生姐妹。由于坏的那个球不知道比好球轻，还是比好球重，那么所选的 12 个编号中，一对孪生姐妹都不能出现。
称重的规则是，第 n 轮就看第 n 个数字，如果是 0 则不称，1 则放左盘，2 则放右盘。因此，所选的 12 个数中，每位数的 0, 1, 2 的出现频率必须正好为四次。
综上两个条件，可得出以下编号：002，010，011，021，100，102，111，120，202，220，221，212 能找出坏球是哪个。
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |