n鐵球稱重問題（12個鐵球3次找出壞的擴展）？

12-30

問大牛們一個問題，有一個天平，沒有砝碼，只能對比兩邊物品誰輕誰重或一樣，n個鐵球，有一個壞的，不知鐵球比正常的輕還是重，但肯定不同，最少多少次能稱出那個壞的

這個問題可以用計算離散無記憶信源的信息熵的來證明是否可以在給定次數內有界存在，但這和證明5次方程有5個根一樣，不一定能找出解。

12個重量未知的鐵球中包含的信息熵可以用信息熵公式計算：

H=-12*(1/12)*log2(1/12)-log2(1/2)=4.5850bit

每次稱重有三種結果，獲得的信息熵是：

H=-log2(1/3)=1.5850bit

兩個結果相除然後向上取整就行，但你如果想不出具體解決方法的話，知道也意義不大……

根據香農公式X=log3(2n)向上取整。（感謝 @肖進同學指出錯誤）

============大家好，我是分割線===========

有12個鐵球，其中有一個壞球，可能輕也可能重。所以總事件數是12*2=24

每稱一次表面上看，只會出現兩種情況，天平平衡或不平衡。但在不平衡中隱含的信息有壞球比好球重，或壞球比好球輕（一次測量無法得出，但經過多次測量後可得出）在知道了哪一個球是壞球的同時，你也必然知道了壞球是輕是重。所以你每次稱量得到的信息量是3。

（具體操作及證明過程，贊過100就給出~~~~~）

這個問題，網上答案很多呀，我之前寫過一個可視化的答案，可惜搞丟了。等我回家找找吧。

我來答一下這道題。這道題是我個人的驕傲。我所認識的所有人當中，在從未接觸過十二球3次找壞球這道題的情況下將其解出的人，只有我一個，解出時間是高中，用時45分鐘（一整節晚自習的時間）。

我很喜歡目前首答 @poem garden先生的答案，高屋建瓴，給了一個非常良好的視角，讓我受到很大啟發。

但我覺得還是有另外的解讀角度的，我從地板開始給大家解讀起，用一個小白都能理解的方式，同時，也會給出一個和 @poem garden先生所給的完全不同的公式。先假設有在題目開始時，存在1個已知標準球可供使用（已知標準球不計進球數中，比如，12球問題的話，則由12個可能是壞球的球，和1個已知標準球）。

我們從倒數第二次稱重開始考察起：倒數第二次稱重後，最多允許有多少個從未被稱過的球？答案是 $3^0=1$ 個。因為最壞情況，這個球是壞球的話，那麼最後一次稱重需要拿這個球與標準球進行對比，得出壞球是偏輕還是偏重的結論。那麼最多能有多少個不確定是否是壞球的球留在天平上？答案是 $3^1=3$ 個。設它們為1號球，2號球和3號球，1，2號球在左邊，3號球和一個已知標準球在右邊。無論1，2號球是偏輕還是偏重。最後一次稱時，將3號球和多餘標準球移除，1號球位置保持不變，2號球位置換到對立面。則：天平平衡，壞球是3號球，偏輕或偏重從倒數第二次測量中可以得知；天平結果不變，則壞球是1號球；天平結果逆轉，則壞球是2號球。換言之，在最後一次測量中，懷疑範圍至少要被縮小到 $3^1=3$ 個已被稱重過的球上（這句話很重要！）。所以，只有兩次測量機會的情況下，我們最多能夠測出 $3^0+3^1=4$ 個球中的一個壞球。
我們再考察倒數第三次稱重：由1.可知，倒數第三次稱重後，最多能有 $3^0+3^1=4$ 個從未被稱過的球。這樣一來如果最壞情況，這組球是壞球的話，則可以回到1.。而最多能有 $3^2=9$ 個球在天平上被稱量。這樣，倒數第二次分組時，仍能把9個球分為3組：3個球被互換位置、3個球被保持原位，3個球被取下天平，這樣，根據結果的不同——天平平衡，天平傾斜方向和上次相同，天平傾斜方向和上次相反——在最後一次測量時，將懷疑範圍縮小到已被稱重過的某一組、3個球內，從而回到1.的情況（到最後一次稱量時，只剩3個被稱重過的可疑球）。故如果只有3次稱重機會的情況下，我們最多能夠測出 $sum_{i=0}^{3-1}3^i=13$ 個球中的一個壞球。
根據數學歸納法，設在有n次稱重機會的情況下，最多能夠測出 $sum_{i=0}^{n-1}3^i$ 個球中的一個壞球，且如果壞球在第一次稱重的球中，第二次（倒數第n-1次）稱重時至少要將懷疑範圍縮小到已稱重過的 $3^{n-1}$ 個球內。則：如有 $n+1$ 次稱重機會時，第一次稱重最多允許有 $sum_{i=0}^{n-1}3^i$ 個球未被稱重，而天平上最多可以有 $3^n$ 個球處於被稱重狀態，這樣一來，第倒數第n次測量時，把球分為等分的三組：一組位置不變，一組被拿下天平，還有一組被調換位置，使得在倒數第n-1次測量時，把懷疑範圍縮小到 $3^{n-1}$ 個已被稱量過的球內。由此可以得出：在有 $n+1$ 次稱量機會的情況下，最多可以確定 $sum_{i=0}^{n}3^i$ 個球中的一個壞球。

從而，給予 $n$ 次測量機會，最多能夠測出 $sum_{i=0}^{n-1}3^i$ 個球中的一個壞球。

那麼如果在問題開始的時候不允許配置1個標準球呢？其實也很簡單，給予 $n$ 次測量機會，最多能夠測出 $sum_{i=0}^{n-1}3^i-1$ 個球中的一個壞球。由於 $3^n$ 必然是奇數，在第一次稱量時如果不允許配備已知標準球（從第二次稱量開始，必然有足夠的已知標準球可供使用），那麼只能減掉一個球，來讓天平兩邊的球數相等。

我的這個公式，實際上與 @poem garden先生的公式是等價的。理由很簡單，由等比數列求和公式我們有：給予 $n$ 次測量機會，最多能夠測出x個球中的一個壞球，其中 $x=sum_{i=0}^{n-1}3^i=frac{1 imes(3^n-1)}{3-1}=frac{3^n-1}{2}$ 。這個公式中的n，其實是先生的公式中的X，而先生公式中的n，即是這個公式中的x。兩個公式互為反函數。不得不說的是，我很遺憾自己沒有學過資訊理論，對於這個問題，只有小聰明，卻沒有 @poem garden先生那種高屋建瓴的眼光。

看到這道題下面其他高人和我的答案相比，深深體會到孔老夫子的那句話：思而不學則殆，以及荀夫子的那句話：吾嘗終日而思矣，不如須臾之所學也。

上面的演算法對我來說太深奧了，看不懂，我自己的結果是4次（是不是太多了？），一定能找到。

我的方法如下：2014-09-25

1、12個球依次編號b1到b12；

2、b1到b6，3對3稱重，通過平不平衡可以確定包含壞球的6個，重新編號b1到b6（一次）；

3、b1到b4，2對2稱重，如果不平衡，則重新編號b1到b4，進入步驟4（二次）；如果平衡則包含環球的2球編號b1，b2，進入步驟5；

4、b1和b2，1對1稱重，確定不平衡的一對，編號b1和b2（三次）；

5、用其他球b和b1對比，平衡則壞球是b2，否則是b1（四次）；

則，兩種情況：1-2-3-4-5（四次）；1-2-3-5（三次），所以這方法最少三次，最多四次。

12個球，一共24種可能（1重，1輕，2重，2輕。。。。）

每稱一次只剩下1/3的可能，因為天平可以有左重，又重和平衡三種狀態

最後就是log3(2 * 12)向上取整了。

參考：劉未鵬數學之美番外篇：快排為什麼那樣快

http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/

裡面講了類似的思維解釋其他問題。

打了一大堆發現自己算錯了，丟人

鏈接: https://pan.baidu.com/s/1pLa9VQF 密碼: t8bm 一個安卓的模擬稱球的APP，直接下載安裝就可以用。歡迎試用，不足之處，請多指正。