Re: [閒聊] 八卦板的「超怪面試問題」

[SansWord (是妳)]

: 問題三：（Intel）
: ：「你有8枚便士，7枚一樣重、1枚比較輕，你有1個秤，你要如何在3次機會中找出那個
: 最輕的？」
昨晚想了一整晚，還因此熬夜

不過最後還是沒有一個完整結果，先把我的解法拋出來引玉。
如果有人知道正確答案，請跟我說。如果已經證明題目無解，也請跟我說，謝謝！

首先我們要有一個正確假設
那就是輕與重硬幣的重量相差是顯著的，這個給定的秤一定可以量測出來。
否則工具就不是我們所可以使用的(無法區辨輕重硬幣)

先把硬幣編號1~8
秤1 2 3 7, 得到a
秤1 2 4 6, 得到b

如果a > b, 代表錯誤出現在4 or 6, 且a/4為正確重量
所以最後一次秤4, 如果等於正確重量，答案就是6, 相反就是4

如果a < b, 代表錯誤出現在3 or 7, 且b/4為正確重量
所以最後一次秤3, 如果等於正確重量，答案就是7, 相反就是3

如果a==b, 那就麻煩了(卡住的開始)
這時候錯誤有可能是1, 2 ,5 ,8 其中一個。
現在秤2, 5, 得到重量為c
若a == 2c, 則答案是8
若a <  2c, 則答案是1
若a >  2c, 則答案是2 5 其中一個。(卡住了)

進入所謂的 "右腦解法" ：
若我這個時候能上網得知一個便士的正確重量為k
那如果a == 4k, 則答案是5
      a <  4k, 則答案是2


我盡力了....

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.193.67.182
推 walkwall:帕索之前那篇有講  如果是重量秤  要四次
→ walkwall:我想是原本設計題目的人忽略 000 跟 111 無法分辨的問題
→ walkwall:天平的話就是兩次  總之沒有三次的答案
→ SansWord:有證明嗎？關於至少要4次的證明。
→ SansWord:先謝過了，我正在爬這裡哪邊出現這篇文章。
→ puzzlez:並沒有所謂至少要4次的證明 只是因為怎麼想都不可能的關係
推 ddavinci:請問有沒有講解文啊? 我想不通ㄝ
→ SansWord:是指題目嗎？還是我的解法？
→ ddtddt:有證明三次找不到百分之百的解。
→ ddtddt:但我認為更重要的是，你如何來做這件事。
→ ddtddt:就算找不到百分之百的解，仍應該提供一個較好的方法@"@
→ ddtddt:限定在三次機會中，你是否能提供比別人更好的方法。