2008年4月3日 星期四

天秤找假幣(二)

最近忙了一點,今次先說說三題的「最佳」答案,下次才說怎樣證明為「最佳」。

說起「最佳」,我的原意是「最少用多少次天秤就能確定能找出假幣?」。網友Pop在上一篇文章留言用了另一個方法看「最佳」,就是「平均用多少次天秤就能確定能找出假幣?」。大家可以到上一篇文章的「意見」看一看。

1) a)

Pop在上一篇文章說了方法,最壞情況需要三次。

1) b)

先在天秤兩邊每邊任意放四個金幣。

若然兩邊重量一樣,則可確定不在天秤上的四個幣其中一個是假的。只需要多用兩次天秤,便能從這四個幣中判出哪個是假(這個不難,自己想一想吧)。

若然兩邊重量不一樣,定義在較輕那邊的四個幣為L1, L2, L3, L4;在較重那邊的四個幣為H1,H2,H3,H4。

把L1,L2,H1放在一邊,L3,L4,H2放在另一邊。若然兩邊重量一樣,則H3是假幣或H4是假幣。那麼只要將H3和H4秤一次,哪個較重就是假的。若然兩邊重量不一樣,不失一般性,設L1,L2,H1那邊較輕。那麼只可能出現以下情況:

i) L1是假幣,比真幣輕
ii) L2是假幣,比真幣輕
iii) H2是假幣,比真幣重

只需將L1和L2秤一次,若兩邊重量一樣,是情況iii);若L1比L2輕,是情況i);若L1比L2重,是情況ii)。

故最壞情況也是三次。

2)

設已確定為真的幣為N,而其餘五個幣的編號為1,2,3,4,5。

先將N和1放在一邊,2和3放在另一邊。若兩邊重量一樣,則4為假幣或5為假幣。之後將N和4一起秤,若重量一樣則5為假幣;若重量不同則4為假幣。

若 N和1 比 2和3 輕,則只會出現以下三種情況:
i) 1 是假幣,比真幣輕
ii) 2是假幣,比真幣重
iii) 3是假幣,比真幣重

若 N和1 比 2和3 重,則只會出現以下三種情況:
i) 1是假幣,比真幣重
ii) 2是假幣,比真幣輕
iii) 3是假幣,比真幣輕

兩組的「三種情況」均可以用一次天秤就能判別哪個是假幣,而且方法非常簡單(跟 1) b) 最後一部分類似),故略。


看了解答後,我相信部分人會有一點疑惑:1) a)只有五個幣,1) b)有十二個幣,怎麼「最佳」的解法都是三次?這不敢令人對1) a)的「最佳」解法質疑。所以,數學人必須證明它是「最佳」!

下次我便說說證明「最佳」的方法,並簡介一下這個方法解決了一個Computer Science基本但非常重要的問題。

4 則留言:

Kevin 提到...

Good post. Simple and clear.

I think the trickest part is that it is not easy to realize that for each test, there are 3 possible outcomes instead of 2.

Maybe it is also interesting to talk about the reverse question in your next post: given that 3 tests are allowed, how large can n be?

Marco_Dick 提到...

Thanks for support.

Actually I wanna discuss the problem you mentioned also, but I cannot get around some difficulties when using tree and leaves to explain. I have to use something like dynamic programming to explain, which I think is less elegant.

Emile Tsui` 提到...

你好...我係一個中2o既學生....
老師問我衣條題目...我解好左...但想搵答案.....
講番正題
你地話1b題係咁解::
先在天秤兩邊每邊任意放四個金幣。

若然兩邊重量一樣,則可確定不在天秤上的四個幣其中一個是假的。只需要多用兩次天秤,便能從這四個幣中判出哪個是假(這個不難,自己想一想吧)。

若然兩邊重量不一樣,定義在較輕那邊的四個幣為L1, L2, L3, L4;在較重那邊的四個幣為H1,H2,H3,H4。

把L1,L2,H1放在一邊,L3,L4,H2放在另一邊。若然兩邊重量一樣,則H3是假幣或H4是假幣。那麼只要將H3和H4秤一次,哪個較重就是假的。若然兩邊重量不一樣,不失一般性,設L1,L2,H1那邊較輕。那麼只可能出現以下情況:

i) L1是假幣,比真幣輕
ii) L2是假幣,比真幣輕
iii) H2是假幣,比真幣重

只需將L1和L2秤一次,若兩邊重量一樣,是情況iii);若L1比L2輕,是情況i);若L1比L2重,是情況ii)。

故最壞情況也是三次。
**************************
但係你係唔知係輕d定重d...喎

blog marketing 提到...

飞龙搬家公司,是一家专业性北京搬家公司,企业诚信,员工搬运专业,是北京搬家公司行业的后起新秀,公司长期为搬家免费纸箱。欢迎重询!
公兴上海搬场公司是经工商,税务,交通部注册的一家专业性的上海搬家公司,诚实信誉,工作细心,服务热情;为上海搬场,上海搬家的企业,如有需求,敬请垂询本搬场公司
海胜数码快印有限公司,致力于数码印刷,诚实信誉,实力雄厚,技术专业,设备先进,设计新颖,是北京数码印刷行业中新秀一支,愿做北京数码快印需求者的忠诚合作伙伴!
佳佳乐月嫂服务中心,精心提供月嫂服务,育儿嫂服务,育婴师服务,本中心月嫂,育儿嫂,育婴师,均通过健康体验,经过严格培训,持
证上岗.
华夏国际机票预定中心,全程代销各航机票
,特价机票,北京特价国际机票,留学生机票,打折机票,打折的价格,增值的服务
, 国际机票预订中心精心哈护你的远航!
星云科技,诚信于教育;研究出电子起电机,语音室,语言实验
,数字探究实验室,数字化实验室,探究实验室,系列探究实验配套设施,望广大院校前来考察!
北凝科技,废汽,余热回收,热力除氧改造,凝结水
治理专家,其推出的,定连排,烟囱余热回收器,乏汽回收,低位热力除氧器,凝结水回收器,冷凝水,
等系列产品.
北京防水堵漏公司、专业承接防水
防水堵漏地下室防水地下室堵漏北京防水北京防水堵漏北京防水公司北京防水网.防水堵漏专家! 工作心细,滴水不漏!
 北京爱福石材养护有限公司是专业从事石材翻新,石材结晶,石材护理,石材清洗,石材养护的企业,专业提供:石材翻新,石材结晶,石材清洗,石材护理,石材养护,石材无缝处理,石材防护,石材防滑,石材病症预防处理,石材修补,石材日常保养等业务.服务专线010-82922015