天平称球 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#1

发表于 2008-9-25 18:43 资料主页短消息只看该作者

天平称球

一共有１２个球，其中一个重量和别的不同（但事先不知道是比别的轻，还是比别的重）。
１。在一个天平上称三次，找出那个“坏球”。
２。证明：无论如何都不能只用两次称出坏球。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#2

发表于 2008-9-26 08:12 资料个人空间短消息只看该作者

我先证明结论2（因为没证明过，想知道这种证明方法是否合理）。
坏球是12个球中任意一个，共12*2=24种可能。
每次称量只有3种可能，2次称量为3*3=9<24，所以不可能。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#3

发表于 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次。

[广告] 真诚支持说岳，携手共创辉煌


	北风烟雪

组别	士兵
级别	仁勇校尉
功绩	2
帖子	171
编号	292032
注册	2008-9-24

#4

发表于 2008-9-26 18:18 资料短消息只看该作者

基本就是上面两位的意思

12个中选出特别一个，信息熵为H=log12

一次称量可以提供的熵为H=log3

log12〉2log3
故2次无论如何不能解决该问题

[广告] 真诚支持说岳，携手共创辉煌


	茅延安

组别	士兵
级别	忠义校尉
功绩	3
帖子	260
编号	61296
注册	2006-3-2
来自	阿里布达

#5

发表于 2008-9-26 18:52 资料短消息只看该作者

总数为13个球呢?能3次称出么?

[广告] 《精忠报国岳飞传完整版》火热发布


	Z_Artemis (冠子)


	燕郡公集庆军节度使 ★★

组别	节度使
级别	骠骑将军
好贴	6
功绩	895
帖子	8351
编号	68083
注册	2006-5-8
来自	雲夢山莊
家族	幽神幻韵

#6

发表于 2008-9-26 19:13 资料个人空间短消息只看该作者

http://www.xycq.net/forum/viewth ... 1998&highlight=

冠子发过这题的

[广告] 《精忠报国岳飞传完整版》火热发布


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#7

发表于 2008-9-26 19:45 资料主页短消息只看该作者

３楼，４楼答案正确。

５楼想法不错，但最好解释一下信息熵和本命题的关系。例如：引理－残余信息熵 > 0，则如何如何．．．

[广告] 真诚支持说岳，携手共创辉煌


	北风烟雪

组别	士兵
级别	仁勇校尉
功绩	2
帖子	171
编号	292032
注册	2008-9-24

#8

发表于 2008-9-27 09:05 资料短消息只看该作者

http://topic.csdn.net/t/20020623/20/824734.html

http://www.quzhi.net/chinese/pdf/algo_analysis.pdf

上面两个链接对这个问题有比较详细的回答。

至于信息论，详细说起来会有好大一段，有兴趣的朋友可以找找相关的资料，这里就不说了~

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	crayfish

组别	校尉
级别	右将军
功绩	12
帖子	1200
编号	2011
注册	2003-11-10

#9

发表于 2008-9-27 14:43 资料文集短消息只看该作者

明白楼主命题2的意思，但是是否描述有问题

2次找到坏球的可能性是存在的，但是2次不能保证一定能找到坏球，
准确的描述应该怎么说呢？

取2个球，第一次2球等重，将其中一球换掉，第二次不等，则坏球被找出来了

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	茅延安

组别	士兵
级别	忠义校尉
功绩	3
帖子	260
编号	61296
注册	2006-3-2
来自	阿里布达

#10

发表于 2008-9-27 19:12 资料短消息只看该作者

6楼被无视了...

QUOTE:

因为3^2=9<24。而3^3=27>24，所以最少要称3次。

如果这就是依据的话
对于13来说,同样有3^2=9<26, 3^3=27>26

是否意味着13个球一样可以在3次内称出呢?

试了下好像不行.

[广告] 《精忠报国岳飞传完整版》火热发布


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#11

发表于 2008-9-28 11:22 资料主页短消息只看该作者

crayfish：不好意思，第二问当然是指在所有情况下，都能在两次内称出坏球。

茅延安：决定１３个球是否能在三次内被称出来。。。这个问题很有意思，大家继续讨论。

北风烟雪：哦，其实我想说的是，当一个东西的残余信息为 I 的情况下，对它随便猜一下就能猜中的概率是 p = e^-I （从 I = -log p 得出）。那么当且仅当残余信息等于 0 的情况下，“随便一猜”才必然是正确的结果。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	炎帝瀑布碎 (月半月半)


	余杭郡公监管使京东西路经略使 ★★★★★★

组别	经略使
级别	征东将军
好贴	1
功绩	2358
帖子	5212
编号	85388
注册	2006-10-1
来自	轩辕学院
家族	肉肉门

#12

发表于 2008-9-28 11:29 资料个人空间短消息只看该作者

回复 #11 茅延安的帖子

13个球肯定可以，不过不知道为什么
偶去年某道面试题就是13个球………………

[广告] 真诚支持说岳，携手共创辉煌


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#13

发表于 2008-9-28 16:18 资料个人空间短消息只看该作者

13个球可以找到坏球，但是有一定几率不能判定球的轻重。

如果能额外提供一个好球，则可以判定球的轻重。

应该是这样了。

[广告] 《精忠报国岳飞传完整版》火热发布


	水泊船夫

组别	士兵
级别	护军
功绩	6
帖子	452
编号	59879
注册	2006-2-13
来自	甘肃
家族	轩辕狼党

#14

发表于 2008-9-28 18:24 资料短消息只看该作者

有一种情况可以两次称出12个球中重量不同的一个球
第一步把球分三组第一组5个第二组5个第三组2个
称第一组和第二组如果重量相等答案就是第三组中的一个是不同的第2次称第三组就能得出答案不过概率比较小,不过并非不可能

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	靖天

组别	士兵
级别	忠义校尉
功绩	3
帖子	286
编号	271095
注册	2008-3-15
来自	HK
家族	轩辕狼党

#15

发表于 2008-9-28 19:25 资料个人空间短消息只看该作者

LZ的問題出現過多次
6樓茅大哥的問題倒挺感興趣
13球的個案應該是可解的
但有些情況會不知道壞球輕重
如果一開始知道壞球輕重
那13球就很容易解決了

[广告] 真诚支持说岳，携手共创辉煌


	茅延安

组别	士兵
级别	忠义校尉
功绩	3
帖子	260
编号	61296
注册	2006-3-2
来自	阿里布达

#16

发表于 2008-9-28 21:11 资料短消息只看该作者

回14楼,问题本身在于"找出坏球",而并不需要指出其"轻重"

例如12球下,当1-4与5-8等重的时候,是无法在3次内确定坏球比好球更轻或是更重的

QUOTE:

"13个球可以找到坏球"

希望能给出方案

[广告] 真诚支持说岳，携手共创辉煌


	茅延安

组别	士兵
级别	忠义校尉
功绩	3
帖子	260
编号	61296
注册	2006-3-2
来自	阿里布达

#17

发表于 2008-9-28 21:23 资料短消息只看该作者

收回楼上的话.12球下是可以确定坏球轻重的,只是在本题下没有必要,因为题目没有要求

[广告] 《精忠报国岳飞传完整版》火热发布


	茅延安

组别	士兵
级别	忠义校尉
功绩	3
帖子	260
编号	61296
注册	2006-3-2
来自	阿里布达

#18

发表于 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 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#19

发表于 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是坏球，但不能判定轻重。

[广告] 真诚支持说岳，携手共创辉煌


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#20

发表于 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）个球中找出坏球且能判定坏球的轻重。

[广告] 《精忠报国岳飞传完整版》火热发布


	龙剑止水

组别	校尉
级别	奋威校尉
好贴	2
功绩	11
帖子	124
编号	99726
注册	2007-1-9

#21

发表于 2008-10-1 19:39 资料文集短消息只看该作者

记得Thomas Cover的经典教材《Elements of Information Theory》里讲信息熵的时候就用到了这个例子

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#22

发表于 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

组别	百姓
级别	在野武将
功绩	0
帖子	6
编号	307097
注册	2009-1-22

#23

发表于 2009-2-5 11:58 资料短消息只看该作者

这个问题前几天同学跟我说过，我想了一个小时想出来的，呵呵

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	中庸


	白衣伯爵中大夫

组别	白衣卿相
级别	镇南将军
好贴	1
功绩	198
帖子	3726
编号	6419
注册	2004-4-2
家族	轩辕丐帮

#24

发表于 2009-2-23 18:33 资料个人空间短消息只看该作者

假设左边比较沉。第二次称1、6、7、8和5、9、10、11，如果右边比较沉，说明问题在6、7、8里，而且问题球比较沉。

这个应该有问题吧？既然左边已经沉了，那说明1、2、3、4可能大于等于正常四个球的重量但不能确定那个球沉啊。怎么会得出问题球在6、7、8里面，而且正常重？待高人解释！

另外饿觉得这题三次称不出来的，前提是不知道轻重！

[广告] 《精忠报国岳飞传完整版》火热发布


	中庸


	白衣伯爵中大夫

组别	白衣卿相
级别	镇南将军
好贴	1
功绩	198
帖子	3726
编号	6419
注册	2004-4-2
家族	轩辕丐帮

#25

发表于 2009-2-23 18:36 资料个人空间短消息只看该作者

另外补充一点：在不知道球重量的情况下，如果不通过标准球（也就是正常球）称量比较的话，球的轻重是无从判断的。也可能是饿没开窍！

想明白了，呵呵！

QUOTE:

原帖由 小女秦怜月 于 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

组别	百姓
级别	在野武将
功绩	0
帖子	32
编号	342934
注册	2009-10-12

#26

发表于 2009-10-16 11:09 资料短消息只看该作者

我老乡出的题都有点意思

[广告] 《精忠报国岳飞传完整版》火热发布


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#27

发表于 2009-10-16 14:55 资料个人空间短消息只看该作者

是不是脑子简单了点，越看越头大

[广告] 《精忠报国岳飞传完整版》火热发布


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#28

发表于 2009-12-13 23:13 资料个人空间短消息只看该作者

回复 #22 天宫公主的帖子

对这个解法很感兴趣。
有原理不，若有，希望能说明一二。谢谢。

大致明白了。

[ 本帖最后由墨叶于 2009-12-14 15:37 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#29

发表于 2009-12-14 18:56 资料主页短消息只看该作者

也没什么诀窍了，无非是把称球问题转换成进位制问题了。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#30

发表于 2009-12-14 22:29 资料个人空间短消息只看该作者

QUOTE:

原帖由 天宫公主 于 2009-12-14 18:56 发表
也没什么诀窍了，无非是把称球问题转换成进位制问题了。

这个能看出来。也能看明白如何找出坏球。
3进制3位数共27个。除去000，还有26个，26/2=13。122和211没有出现。
我在思考选的12个数有什么具体原则。以及如何判断坏球的轻重。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！