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

: 唔...這個結論似乎有待檢討
: 例如這樣好了:
: case 1: case 2:
: 正常一個 1g 正常一個 1.2g
: 輕的一個 0.8g 輕的一個 0.4g
: 四正常 4g 三正常一輕 4g
: 二正常一輕 2.8g 兩正常一輕 2.8g
: 結果你第一次拿四個硬幣秤得 4g 第二次拿三個硬幣秤得 2.8g
: 你不會知道是上面二種 case 的哪一個...
: 這個結論只有一種時候是對的 那就是兩次上去秤的硬幣沒有重覆

: 我這樣證明試試看:
: 第三次秤的結果只會有兩種情形：要嘛有輕幣 要嘛沒有輕幣
: 這代表我們必須在前兩次秤時把可能性減少到剩下兩個
: 於是前兩次秤必須要至少有四種可分辨的結果
: 但是無論如何 三一律告訴我們
: 前兩次的兩個結果的比值和某數比較只會有三個情形
: (許多類似的運算其實都可以化歸為兩個結果的比值)
: 這個比較的基準值只能是在測量前的已知值
: 而這問題中只有這兩次放上去測的硬幣的個數比是這樣的已知值
: 所以不可能有四種可分辨的結果出來 因此無解

這題其實就是一個 8選1 的選擇題，所以分堆上必須要在3次分堆後
展現出8種可能案例。


我做到的方法是把硬幣編號1~8後

依編號分成三堆
(這樣的分堆是設計後的結果，我的意圖是為了讓 8 個Case在分堆中能區辨)

123 5
12 4 6
1 34 7

這個分法是刻意設計的，若假設一般硬幣重r, 特殊硬幣比一般硬幣輕s
那麼如果4堆都是一般硬幣，那會量到4r
如果其中有一個特殊硬幣， 那會量到4r-s
每一次量測都有可能是4r 或 4r-s, 三次量測總共就是8種可能性


現在做案例窮舉，若特殊硬幣為1
則會量測到
Case1:
4r-s
4r-s
4r-s
依序列出每個Case:
Case1: Case5:
4r-s 4r-s
4r-s 4r
4r-s 4r

Case2: Case6:
4r-s 4r
4r-s 4r-s
4r 4r

Case3: Case7:
4r-s 4r
4r 4r
4r-s 4r-s

Case4: Case8:
4r 4r
4r-s 4r
4r-s 4r

假設無法得知r與s的正確數值，那我只能觀察三次量測彼此的大小關係
看似有8個案例，但是Case1 與Case8 其實無法區分

所以會導致最後無法肯定答案為1或8, 其他都能肯定。

=============開始想像別種解法====================
也因此，我知道一口氣量測三次是不智的，如果前兩次重量相等，
那麼第三次仍舊量測1 3 4 7 這四個銅板，必定會導致最後無法區辨是1 或8的結果

所以我想先按照分堆量測第一、第二次，最後一次若重量相等，就用不同抓法。

按照這個案例表，當第一次第二次重量相等時，
案例剩下1 2 7 8 四種硬幣
而實際推廣上，
1 2 代表的是第一次與第二次的共通硬幣
7 8 代表的是前兩次都沒有抓起的硬幣

第三次分堆時，若要取有代表性的硬幣，那只要抓1 2 其中之一，與7 8其中之一即可。
然後就回到了我回答的第一篇的狀況，仍舊無法區辨四種狀況。

簡單的來說，當第一次第二次的重量相等時
以線性代數的角度來說，便是我們喪失了一個限制式

本來若有三個限制式，就能推廣出 2^3 的8種狀況。
但是喪失了一個限制式(或著說兩個限制式合併)，導致無法推導出最後的狀況。

也就很像前一篇您說的，前兩次由於重量相等，導致最後一次量測
的三一律只有可能比第一二次大或著等於或小於，也就是只會區辨出3種狀況。

導致一定有一個狀況是模糊的。

================最後的解法==========
若我能上網得知r的正確值，那我量測三次後，若三個都相等
那我自然能知道重量為4r或著小於4r
那就能判斷硬幣是1 或 8了。

問題是誰說比較重的硬幣一定要所謂的 "法定重量" 呢？
若法定重量是10克，那出題者可以給7個9.9克和一個9.8克

那不管是1或8我都會誤判成8

不過這樣量測三次後，等於猜錯機率只剩下1/8....也算夠準了吧....(這句話是耍賴)

--