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

[walkwall (會走路的牆)]

※ 引述《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
: 我盡力了....


路過亂證
--------

因為三次測量

最輕的那球只有可能在或者不在秤上

如果故意讓球的數量不同,會白白浪費秤的機會

故每次秤都讓球的數量一樣多

因此只會有七種結果

1.一樣重
2.第一次較輕
3.第二次較輕
4.第三次較輕
5.第一次較重
6.第二次較重
7.第三次較重

然而球的狀態有八種可能

所以不論設計何種策略

依照鴿籠原理,必然至少兩種可能會落在上述七種結果之一

故得證三次不可能

騙P幣完畢   謝謝收看

------------------------------------------------------

基於良心過不去  附贈天平板兩次解答

A~H共八個球

第一次測量  ABC左 DEF右

1.若左輕(右頃)  表示ABC之一為答案  則第二次左A右B  左輕A 右輕B 一樣C

2.若右輕(左頃)  表示DEF之一為答案  同理  左D右E可得解

3.若一樣  表示GH之一為答案  左G右H輕的那邊是答案

※ 編輯: walkwall        來自: 140.117.120.119      (01/06 18:37)
→ puzzlez:天平版的還要寫哦？XDDDDDDDD
→ walkwall:本來沒有要寫   不過上一篇看起來有需求  順便補一下
推 ddavinci:喔喔 這個天平版解答好聰明喔
推 SansWord:這個證明我可以接受，不過有個變數是重量的差值
→ SansWord:即使三次個數不一樣，我仍舊可以用平均值判斷我是否抓到
→ SansWord:輕硬幣。  所以我一直覺得個數不同才有機會有正確答案
→ SansWord:甚至只兩次個數不同，我就能用二元一次方程式算出
→ SansWord:正確的硬幣與輕硬幣的重量。可是即使如此，我還是
→ SansWord:不能利用最後一次量測機會找出哪個是錯誤的。
→ walkwall:如果會知道要用平均值  那表示你接受手的感知重量差別
→ walkwall:那麼直接都用手感覺就好了  不需要用秤...
推 puzzlez: 如果事前知道正常硬重多少，秤三次一定找得出來...
→ puzzlez: 偷偷加進這項條件再回答好了XDDDDD
推 shou0823:剛剛在古狗上面發現有人用三次使用"秤"成功解出來了..!
→ shou0823:不對!!  後來想一想還是有四次的風險...
推 SansWord:事先知道硬幣重量的話，那我就能算出來了。
→ SansWord:麻煩的是如果第一次第二次量測的值一樣，我無法分辨
→ SansWord:到底是兩次都沒拿到假的，還是都拿到假的
→ SansWord:就不能知道硬幣正確重量了