N 個乒乓球中有一個和其他的質量不同，用天平最少幾次一定能稱出來？

11-16

註：原題描述中n為999
很有趣的一道題？！知友們，問的是「最少」啊！

答案是七次。
@洪濤給的文獻是靠譜的，只是沒有給出具體操作，具體操作在文獻的參考里。
The Problem of the Pennies, F. J. Dyson, The Mathematical Gazette , Vol. 30, No. 291 (Oct., 1946), pp. 231-234

我現在把具體操作寫出來：
最重要的一步是給球編碼。

我們取所有 7 位三進位數，共有 $3^7$ 個編碼，去掉所有位數都一樣的情況，共有 $3^7-3$ 個編碼。
其中有一半，首次出現鄰位不同的情況是 01, 12 或 20，這樣的編碼叫「正序」的，否則是「逆序」的。
正序碼共 $(3^7-3)/2$ 個。把一個正序碼中的 1 換成 2，2 換成 0，0 換成 1，結果仍然是正序的。我們把可以通過這種方式相互轉換的三個碼作為一組。
現在把正序碼一組一組的分配給乒乓球。因為此題中是 999 個球，正好分完 333 組，沒有不完整的組。否則還要調整。
對每一個球，將其正序碼中的 0 和 2 對換，得到相應的逆序碼。因此每個球有兩套編碼。

接下來稱球。

在第 k 次稱球中，將正序碼第 k 位為 0 的 333 個球放在天平左邊，正序碼第 k 位為 2 的 333 個放在右邊，其他球放在旁邊。
如果左邊重，記 0。如果右邊重，記 2。如果平衡，記 1。這樣我們得到一個 7 位三進位碼。
這個三進位碼編號的球就是與眾不同的球，如果該碼是正序的，該球較重；如果逆序，該球較輕。

下面以 6 個球舉例。取 3 位三進位正序碼，共 12 個。
取其中兩組 (010, 121, 202) 和 (012, 201, 120)，依次分配給六個球。
第一次稱 010, 012 - 202, 201
第二次稱 202, 201 - 121, 120
第三次稱 010, 120 - 202, 012
結果舉例：012 說明第四個球比較重，021 說明第五個球比較輕。

加一個 12 球的例子，見這個網頁（英語）http://www.cut-the-knot.org/blue/weight3.shtml

補充：
幾個新答案做出 2 次最多稱 4 個，3 次最多稱 13 個這樣的歸納。
如果需要知道次品的輕重，n 次最多稱 (3^n-3)/2 個球。
4 個球必須稱 3 次才能確定找出壞球，並知道輕重。
我開頭引用的文獻嚴格證明了這是最優的，多於 (3^n-3)/2 無解。
如果不關心輕重，n 次最多的確可以稱 (3^n-1)/2 個球，將多出的那個編號為 111...11 即可。

下載文獻可能不方便，我把證明截圖貼在下面。

@洪濤的文獻和@陳浩的解析太贊了，集精巧和嚴謹於一身，可以說小球稱重問題已經得到了圓滿的解決。
為了更直觀、更易懂、讓PDF恐懼症患者都能弄明白，我做了個小程序來演示：點擊進入。

支持3~999個球；
用戶自行選擇哪個球是特殊球，是輕還是重，然後由電腦自動分組稱量；
用綠色代表輕，紅色代表重；
演示界面大致是這麼個效果：

希望能幫助大家更好地理解。

PS：知乎要是能嵌入代碼我就不至於把它放到單獨的網站上了，不過這大概不太可能……

樓上給的具體實現方法基本已經很清楚了。
這裡從信息量角度解釋一下原因以及稱量次數的一般計算方法。
為什麼999個球是7次？12個球是3次？為什麼6個球還是3次？？？

每一次稱量，帶來的結果有3種，左邊重，右邊重，一樣重，給我們帶來的信息量是 $log_{2}3$ 大約是1.58 bit 的樣子。
999個球有一個球重量不一樣，那麼總共可能有 999*2 種結果（1號球輕，1號球重，2號球輕，2號球重......999號球輕，999號球重）。判斷出結果需要的信息量是 $log_{2}1998$ 大約是10.96 bit。
所以需要的次數就是10.96/1.58 大約是6.94，向上取整需要7次。

12個球需要的次數就是 $log_{2}24/log_{2}3$ 大約是2.89，向上取整為3次。
6個球還是3次，為毛？因為 $log_{2}12/log_{2}3$ 大約是2.26，所以取整了還是3次。

這個東西除了估算需要的次數有什麼用呢？答案是沒有什麼用，而且有時候可能還會因為一些問題引起誤差。
比如說按這種方法計算的次數，4個球兩次就能稱出來。先試著想一下，你會發現想破腦袋也想不出來。
怎麼稱呢？1.33個球放左邊，1.33個放右邊，剩下1.33個不稱。
1.33個球要怎麼放在天平上？？？這怎麼玩兒？
所以4個球稱兩次稱出來，這是沒有可操作性的。

「哥只告訴你們這種方法一定存在，你們慢慢去找，找得到是哥的水平高，找不到是你們太蠢。」
——克勞德·艾爾伍德·香農

開始成為堅定的資訊理論黑香農黑了吧？所以說沒有學過資訊理論的人和學過資訊理論的人怎麼可能在一起？

————————————————這裡是2012年3月18日的分割線
首先說一下什麼叫香農定理是存在性定理，就是香農定理會指出最理想化的編碼演算法能達到的位數底線，就是這樣的理想演算法理論上存在，但是這種理想的演算法不一定能在現實中被發現或實現。

我寫這個答案的初衷是單純從資訊理論的角度上來看待一下這個問題，換句話就是給出可能的理想情況編碼位數下限，而前面@陳浩的答案則是一種現成的演算法。
這個演算法美不美？很美，三進位的思路可能是借鑒前人的，但是利用正向序列映射，通過天平的結果記錄直觀得出哪個球輕了還是重了，非常巧妙。
（P.S.可以去看下那個給1000隻老鼠喝毒藥的問題，就是這個映射的二進位版本，因為天平有三種情況，「左偏」「右偏」「平」，老鼠只有「死」「活」）
這可能是人類可以找出的最完美的演算法了，但是這是理想的演算法嗎？不是。
為什麼？理想情況下的三次稱量結果帶來的信息量是 $log_{2}27$ ,而這裡呢？ $log_{2}24$ 。
因為三次稱量「全是大於」，「全是小於」，「全是等於」的情況在這種演算法里是不可能出現的。
這就是不完美的地方，單從天平而言，這三種情況本來可以帶給我們信息量，但是由於演算法設計不可能出現，就降低了天平能傳達的信息量。

一句題外話，這也就是為什麼12個球3次的情況在這裡顯得這麼完美。因為12個球的每個可能有輕重，這個信息量是多少？ $log_{2}24$ ！剛好是這種演算法稱三次的理想情況。

討論一下完美的情況有什麼要求。
信源熵是 $log_{2}2N$ 應該沒疑問了，N代表球數。
次數 m= $log_{2}2N$ / $log_{2}3$ 的條件是，每次稱量的信息量都為 $log_{2}3$ ，也就是每次稱量的結果都要是獨立且出現概率均為1/3。
這也就是為什麼4個球兩次不能出輕重，具體計算難度不高篇幅太大打公式太麻煩，但是是無法在每次稱量中得到 $log_{2}3$ 的信息量。
怎麼樣才能做到每次稱量得到 $log_{2}3$ ？整數個的球是沒辦法做到的。
但是如果你允許我放0.5個球，或者0.33個球在天平上呢？

每個球切兩半，4個記為AA BB CC DD。
先稱AB CC，
AB=CC，必為D異常，隨便拿個ABC跟D稱一下好了。
AB& AA=BD C+
AA&>BD B-
AB&>CC, D一定正常，A或B重，或C輕，稱AA BD：AA& AA=BD C-
AA&>BD A+

這裡其實已經有偷換概念在裡面了，這個問題的信息量計算起來麻煩一些（粗看了下結果好像沒錯，不過要是錯了就掉大了！！！）但是我想體現的是，這種看起來很完美的演算法，也是受到了整數的局限。

最後是吐槽部分：你們都以為我是資訊理論吹么？我是資訊理論黑啊！問題可以討論不出來立場必須擺正啊！
這也就是說的資訊理論各大定理的存在性，完美的演算法不一定等於理想的情況，理想的情況不一定取得到，就是這樣。至於怎麼搞完美演算法？別找我，我只負責算理想情況。
所以說資訊理論有啥用呢？過去聽過一個笑話，養雞場的雞蛋老是被壓碎，找了一群物理學家研究，他們得出了一個完美的解決方案，但是只對真空中的球形雞蛋有效。
以上。

7次
http://www.math.sinica.edu.tw/math_media/d223/22303.pdf
第 22 卷第 3 期 PDF
用文章末最後的結論（第八節）
update
＝＝＝＝＝＝＝
這篇文章出自數學傳播這本雜誌，只給出了理論上的下界，沒有給出具體的方法，雜誌由台灣主辦在網上可以免費閱讀。
一個更具體的例子是12個球，大部分人的方法要稱4次，這篇文章中通過編碼的方法，只用了三次Weighing 12 coins, an Odd Ball (A Sellection of Treatments) puzzle
更一般的方法見陳浩的答案。用這個方法理論上的下界總是可以達到的，
應投稿給matrix67，我想他會很喜歎。

7次是正確的， @陳浩說的非常清楚了，這裡給PDF恐懼症患者做一下補充說明，不太嚴謹，不過比較直觀。
題目中999個球中含有一個特殊的球，一共有（999 * 2 =）1998種不同的情況（每個球都可能特殊*輕或重兩種可能），而天平每次稱量存在左邊輕、右邊輕、兩邊一樣三種可能。

我們唯一能做的，就是通過稱量可以排除稱量結果矛盾的情況（比方說左邊放球0~332,右邊放333~665，666~998不放，左邊輕可以排除0~332中有個球重、333~665有個球輕，666~998存在特殊球共（333 + 333 + 666 =）1332種情況，還剩餘（1998 - 1332 = ）666種情況待確定），一直排除到僅剩1個（某個球輕/重）或2個（某個球特殊，輕重未定，如果題目作進一步要求，那麼極端情況還要多稱量一次），既然要保證一定有解，我們假定每次稱量的結果都是對我們最壞的，也就是排除情況最少的，那麼我們就要儘可能的平均分配天平每個結果蘊含的情況，基本上每次可以排除掉原來的2/3，如果能夠找到這樣的分配方法，我們就可以斷定n次稱量最多在約3^n個球中找到一個特殊球（由於存在剩餘情況總數並非3的倍數的時刻，有時剩餘的可能性略多於原來的1/3）。

至於具體的操作實現，需要利用一個很妙的事實：第一次均分之後至少有1/3的球可確認做標準球，用於輔助以後的稱量（如果每次稱量之後就把沒問題的球扔在一邊，次數是無法保障的呦~），從可能的情況而非球的個數考慮，才能得到正確的解。
————————————————————————————————
這個問題不是開放性問題，也已經有了幾個優秀的解答，為什麼還是不斷重複出現錯誤答案？

7次（感謝洪濤的提醒，我算錯了兩次....)
雖然我贊同了洪濤的答案，但是我依然想要佔據一個答案位
為什麼這麼做，因為洪濤答案中推薦的文章非常的值得一讀，因為那個文章普及了資訊理論的基礎知識
所以我這個答案出現的原因是想要再推薦一下洪濤答案中的文章

但是還是很多人有pdf恐懼症，那麼如果有pdf恐懼症的話，那麼就看這兩個文章吧
數學之美番外篇：快排為什麼那樣快
知其所以然（三）：為什麼演算法這麼難？

PS: 所有講快排的時候不講解空間的都是耍流氓.......

如果再補充條件：並確定次品是輕還是重。
需要多少次？

樓上說的很多的解法，看著挺繞的。發現一個用矩陣的方式求解的一個解法。貌似容易懂很多。
看到那個矩陣的時候，瞬間就可以明白了。

A Compressed Sense of Compressive Sensing (II)

有一種解法是用信息熵來解答的
999個球，其共有W=1998種可能，其信息熵為 S=log W /log 2 (bit) S=10.97 bit
稱重有三種結果，大於，小於，等於，每次可獲得的最大信息熵為 S=1.58 bit
然後假定每次操作均可獲得最大信息熵則需要操作 10.97/1.58=6.9=7次
——在物理書上剽竊來的

@張恆同學，注意樓主說的是＂一定＂能稱出來，你的情況屬於偶然，並不一定。先分ABC份，一份333個，稱AB，AB平衡，則說明不同質量的在C中；不平衡，要注意了：再稱一次AC。
1、A兩次都往下，說明不同質量的在A中，且質量較重；同理都往上，說明質量較輕
2、AC平衡，說明不同質量的在B中，且B往下，質量重，B往上，質量輕
因為要＂一定＂，我們就得按次數多的算，兩次了。接下去就簡單了，繼續三分，（假設質量不同的是較輕的）
三、每份111個
四、每份37個
五、每份13個
六、每份五個
七、每份兩個
八、每份一個
所以，應該是八次。

不知道題中「一次」是如何定義的，如果是「不把之前的球拿下來」的話，兩次就夠了。
1.一個一個的將球同時放到兩邊的托盤中，如果一次，托盤不能平衡了，則其必然在剛剛加入托盤了兩個球之中。
2.取出剛才放入的兩個球，再隨便拿一個球出來，與兩個球中的一個對比，若質量不同，則就是它，若相同，則是另一個。

1、分成 a b c 三份每份 333 個稱a b 如果相同不同的那個肯定在c里稱重 共稱1次
2、將c 重新分成 abc 三份每份 111 個和第一步一樣稱重稱重1次 共稱2次
3、重新分每份37 個稱重1次 共稱3次
4、重新分每份12個稱重2次共5次如果三份重量相同質量不同的就是剩下的那一個 共稱5次否則第五步
5、將找出的12個分三份每份四個稱重1次 共6次
6、將最後剩下的4個拿出三個和第4步相同的方法稱2次 共8ci
-------------------------------------------------------------------------------------------------
以上的結論是最少5次
可。。。。。如果你敢想像第4步的運氣那為什麼不直接拿出一個說就這個和其它不同。。。。稱重0次如果沒人反對你贏了共稱0次概率 1/999

但是這不科學所以我們拿三個 稱兩次 概率1/333

可以利用離散數學中決策樹的思想來解決問題，n將是決策樹的根。在本題中，由於每次稱重會有三種結果，分別是左邊輕、右邊輕、以及相等，因此題中的決策樹將是一個三叉樹。在n = 999的情況下稱重的結果就是log3 999的上界，答案是7次。同樣的道理也可以用在以兩兩對比為基礎的排序演算法的次數上，即對一個長度為n的數組進行排序的次數就是log2 n。

額。。。題主，你確定是「最少」，我怎麼覺得最少一次就算出來了？和@張恆同學想的一樣。

一共999個，那麼先左右都放499個，如果足夠幸運，會發現此時天平持平

那剩下沒放上去的那一個...不就是質量不對的那個嗎？

333稱333，有輕重就111輕111重稱111重111輕，以此類推，有輕重再稱1次-2/3
數目不夠可以填平的，例如18輕18重稱9輕9重18平，最多是（3的N次方-1）/2，可以知道輕重，例如13個，是4稱4，平是2平+1稱3個，3（重或輕）。1稱1知輕重，如果左4重右4輕，2輕2重稱1輕2平是2重1輕有問題，左輕是2輕有問題，左重是2重1輕有問題，在稱2個的就知道輕重

排名第一的使用的正逆序編碼可能不太直觀，而且沒有針對無法完整分配編碼的情況進行具體的說明(當然提到的文獻可能有解釋，沒仔細看)。

我從網上搜到的一篇《用三進位解決小球稱量問題》解釋的更加清楚和完整，使用的編碼方式也更加直觀。整理的網頁版本在此：用三進位解決小球稱量問題。

高中的2分法在知乎大神眼裡簡直什麼都不是了

根據資訊理論來解

鏈接: https://pan.baidu.com/s/1pLa9VQF 密碼: t8bm 一個安卓的模擬稱球的APP，直接下載安裝就可以用。歡迎試用，不足之處，請多指正。 (可設置球數不多於13，否則難度太大，人難以給出具體方案，多於13的適合理論分析)

從資訊理論的角度來看的話，用天平稱重一次，我們能得到1比特的信息。所以理論上來講要找出1000個球中的一個，至少需要稱10次(2^10=1024)。也就是說理論上至少需要稱10次。