Q2　三步找出臥底

某工廠生產了一批玩具人偶，外觀完全一樣，但是在進行稱重時，發現其中一個玩偶的重量不合格（或輕或重）。我們假定給每個玩偶都定義一個號碼以示區別，現在有一架天平（只有托盤，沒有砝碼，精度足夠），請問如何在三次之內找出這個“臥底玩偶”呢？

參考答案

網絡上很多類似的題目，大部分是給4次使用天平的機會，這使得題目的難度大大降低。如果只給三次使用天平的機會，使其變成了一個幾乎不可能完成的任務，你敢挑戰這個難度嗎？

正常人的解題思路

首先要考慮的是第一次在天平上放幾個玩偶。

如果一邊放6個，還剩下1個。如果第一次就出現不平衡的狀態，似乎不可能在兩次內找到臥底。

如果一邊放5個，還剩下3個。如果第一次出現不平衡，那么在5個玩偶中兩次找出臥底似乎還是有可能的。

如果一邊放4個，還剩下5個。機會看上去和上面的情況有些類似。

如果一邊放3個呢？剩下7個。感覺剩下的有點多……

反復嘗試以后，似乎總有些情況下找不到臥底在哪里。

牛人的解題思路

根據上面的思路，可以推理出一個結論。

第一次使用天平，一邊放4個或者一邊放5個才有可能找到臥底。

而且經過反復嘗試，可以得到一邊放4個才是最佳的方案。

第一次使用：1234⊥5678。

那么會出現兩種情況，見下圖。

由上圖得知，必須再使用一次天平，才能確認誰是臥底。

難道此題真的無解了嗎？

外星人的解題思路

我們在上面的解題思路中一直忽略了一個問題：如果事先知道臥底是偏重還是偏輕，那么有些情況就可以得出答案了。

在我們第三次使用天平，一邊只放一個玩偶的時候，如果出現不平衡的情況，我們可以根據玩偶的輕重來得出結論。但是這個假設是不存在的，題目說得非常清楚“或輕或重”。所以在第二次使用完天平以后，不僅要將臥底圈定在一個盡可能小的范圍內，還要能夠推測出臥底比標準的玩偶是偏輕還是偏重。

由此而見，第二次使用天平的方案非常關鍵，因為第三次使用基本是采取一邊放一個的思路。

最關鍵的一點：不管哪一次稱重，我們都可以確認幾個標準的玩偶。如果兩邊平衡，那么該次被稱的所有玩偶都是標準玩偶；如果不平衡，那么沒有參與本次稱重的玩偶都是標準玩偶。

有了這么一個思路以后，我們重新調整第二次稱重的方案。

先來看上面的第一種情況：

當1234⊥5678時，天平出現平衡的情況。

這時候可以確認1～8這8個玩偶是標準玩偶。

所以第二次使用天平時，我們可以采取這樣的方案：

9x⊥AB

（注：x為1～8號玩偶中的任意一個，即x為一個標準玩偶。）

最難理解的部分到了。只要你能理解這一步，思路就完全被打開了。

情況一：平衡。

當9x⊥AB時，如果出現平衡，那么臥底肯定是C、D中的一個。那么第三次拿C、D中任意一個與x去稱重，就很容易找出臥底了。

如果C與x平衡，那D就是臥底；如果C與x不平衡，那么C就是臥底。

情況二：不平衡。

當9x⊥AB時，如果不平衡，那么我們需要做一個特別的工作——記錄下AB是重還是輕，即記錄下天平的傾斜方向。

然后進行第三次稱重：A⊥B。

這時候會出現三種情況：

情況一：A=B。

很明顯，AB都是標準玩偶，得出臥底是9號玩偶。

情況二：A重B輕。

可以確認臥底為A、B中的一個。但究竟是A還是B呢？這就要用到我們剛才做的記錄了。如果剛才記錄的是AB重9x輕，可以確認臥底偏重。所以A為臥底；相反，如果剛才記錄的是AB輕9x重，可以確認臥底偏輕。所以B為臥底。

情況三：A輕B重。

推理過程同上。

如果你能理解這一步，那么這個問題的解決思路就出來了。

我們可以用兩次天平從5個未知身份的玩偶中找到臥底在哪里，然后只需每次都遵循這個思路，就可設計出這道題目的整個解題過程了。

那么如何兩次從1～8這8個玩偶中找出臥底呢？

第二次這樣來稱重：

125⊥34x

（注：x為9A、B、C、D號玩偶中的任意一個，即x為一個標準玩偶。）

為什么要這樣設計呢？就是要把臥底范圍縮小到3個玩偶之內。

我們把3、4、5這三個玩偶分別從天平的一側移到另一側，目的很快你就知道了。

對了，我們忘了一件事情，就是第一次使用天平1234⊥5678的時候，也需要記錄下天平的傾斜方向。

下面這一步也很關鍵，慢慢來理解。

同樣，125⊥34x會出現三種情況：

情況一：125=34x。

1、2、3、4、5都是標準玩偶，臥底在6、7、8號玩偶中。剩下第三次使用天平的方法就和上面講到的從9、A、B中找出臥底是一樣的道理了。

第三次：6⊥7。

如果6=7，則8號是臥底；如果不平衡，那么根據第一次使用天平時我們記錄下的傾斜方向，即第一次使用天平時6、7號玩偶在同一側，因此很容易判斷出哪一個是臥底了。

情況二：125≠34x。

這時候最關鍵是要注意天平的傾斜方向有沒有改變。

如果沒有改變，說明3、4、5號玩偶是標準件，因為天平沒有因為它們的換位而改變傾斜方向。這時可以確認臥底是1、2號中的一個，那么第三次隨便拿一個與x進行對比就可以得到答案了。

如果天平的傾斜方向發生了改變，就可以確認臥底就是3、4、5號中的一個。第三次就拿3號和4號進行稱重，剩下的推理過程和上面的情況就完全一樣了。

現在我們來整理一下整個的解題思路，如下圖：

解開此題有三個關鍵點：

1.每次使用天平都要合理分配數量（其實每次都是黃金分割的數量）。

2.利用天平傾斜的方向給我們帶來的有用信息，判斷出臥底的重量是偏輕還是偏重。

3.通過對未知身份玩偶交換位置，判斷出臥底所在的范圍。