八卦板的「超怪面試問題」 - 拼圖

By Frederica
at 2011-01-06T18:32

Table of Contents

※ 引述《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 01/06 19:45

→ walkwall:本來沒有要寫不過上一篇看起來有需求順便補一下 01/06 19:52

推 ddavinci:喔喔這個天平版解答好聰明喔 01/06 21:27

推 SansWord:這個證明我可以接受，不過有個變數是重量的差值 01/06 21:36

→ SansWord:即使三次個數不一樣，我仍舊可以用平均值判斷我是否抓到 01/06 21:37

→ SansWord:輕硬幣。所以我一直覺得個數不同才有機會有正確答案 01/06 21:37

→ SansWord:甚至只兩次個數不同，我就能用二元一次方程式算出 01/06 21:37

→ SansWord:正確的硬幣與輕硬幣的重量。可是即使如此，我還是 01/06 21:38

→ SansWord:不能利用最後一次量測機會找出哪個是錯誤的。 01/06 21:38

→ walkwall:如果會知道要用平均值那表示你接受手的感知重量差別 01/06 22:42

→ walkwall:那麼直接都用手感覺就好了不需要用秤... 01/06 22:42

推 puzzlez: 如果事前知道正常硬重多少，秤三次一定找得出來... 01/06 23:17