十二個乒乓球特徵相同，其中只有一個重量異常，如何用一部沒有砝碼的天平稱三次，將重量異常的球找出來?

02-05

有十二個乒乓球特徵相同，其中只有一個重量異常，現在要求用一部沒有砝碼的天平稱三次，將那個重量異常的球找出來。

第一次1234vs5678

第二次19ABvs2345

第三次269Cvs137A

（十二個球記作123456789ABC，解法不唯一）

大家可以驗證一下每個球異常對應的結果都不同，這就意味著這樣稱可以辨別出來。那麼這種稱法是怎麼得到的呢？

注意總共有24種情況，稱三次每次三種結果共27種（以0代表左邊重，1代表右邊重，2代表平，那麼結果就是一個三進位三位數），我們只要讓每種情況都對應上不同的結果就能從結果辨別出到底是哪一種情況。我們把x號球偏重的情況記作「x重」，偏輕類似。

顯然，假如情況「1重」對應結果001，那麼「1輕」就會對應110。類似地，我們只需要把重的情況對應的結果設置一下就行了，這樣輕的情況對應的結果自然也就確定了（只要把01反過來2不變即可）。這樣我們就只用設置12種情況對應的結果了。

另外，假如「x重」對應結果012，那x號球肯定第一次上左邊盤，第二次上右邊盤，第三次不上天平。所以我們不能隨便設置對應，必須保持每次天平左右盤球數相等，也就是0在任一位出現次數與1在那一位出現次數相等。

為達到此目標，我們可以考慮設置這12種情況對應的結果使得每一位恰出現四個0四個1四個2。那麼到底怎麼設置呢？

可以用如下方法。比如我想讓「1重」對應001，那麼我也要讓「x重」對應112，「y重」對應220，對某個x，y。（在我的答案中「5重」對應112，「C重」對應220）現在已經有三個了。還要九個。比如我想讓「2重」對應010（為什麼不能對應002？因為它已經被「5輕」對應了，要避開），那麼我也讓「7重」對應121，「B重」對應202。（知道我的辦法了嗎？）這樣，只要一設置一個情況對應的結果，就把那個結果加上111不進位後得到的結果也讓某個情況對應，這樣就能保證每一位012各有4個啦（要注意避開已經被那些「x輕」對應了的情況喔）。接下來的過程我不再贅述，最後得到的對應是：

1—001

2—010

3—011

4—012

5—112

6—120

7—121

8—122

9—200

A—201

B—202

C—220

再把每一位的0放到左盤1放到右盤就得到一開始那個答案啦！

這種方法看上去比較麻煩，但是它可以推廣到任何(3^n-3)/2稱n次得出答案，而且還可以O(n3^n)實現喲（不能更少，因為你總共就要輸出O(n3^n)個數）。

-----------------------------------------

我也能用嚴格的數學語言寫 = = 然而這樣子應該更不容易看懂 = =

現有12個金幣，其中有一枚假幣，試問能否通過三次稱量就找到這枚假幣？（註：真幣假幣孰輕孰重未知）

我費盡波折終於還是做出來了，我的解答如下：

解：

首先給這十二個小球依次編號為1.2.3.4.5.6.7.8.9.10.11.12

現將這12個球分為1.2.3.4、5.6.7.8、9.10.11.12三堆，第一步先稱量1.2.3.4和5.6.7.8 ............a

（一）如果a式平衡，那麼確定假幣一定在9.10.11.12中，第二步：稱量1.9.10.11和5.6.7.8 ............b

如果該式平衡，那麼假幣一定是12；如果該式不平衡，那麼假幣一定在9.10.11之間，且由b式可得真假幣孰輕孰重，下面只需稱量9和10即可輕易得到答案。

（二）如果a式不平衡，那麼9.10.11.12一定是真幣，第二步：稱量1.2.9.10和3.4.7.11 ............c

1.如果c式平衡，那麼可以確定假幣就在5.6.8之中，而且此時可由a式得到真假幣孰輕孰重，下面可以稱量5和6即可得到答案；

2.如果c式不平衡，那麼繼續分類：

x:如果a式和c式傾斜方向相同，那麼表明從a式到c式假幣一定沒有移動，從而確定假幣一定在1.2.7中

下面：稱量1和2 ............d

如果d式平衡，那麼7一定是假幣；

如果d式傾斜方向與a式和c式相同，那麼說明假幣自始至終都沒有移動，即1是假幣；

如果d式傾斜方向與a式和c式不同，那麼說明假幣在c式到d式過程中移動了，即2是假幣

y:如果a式和c式傾斜方向不同，那麼表明a式到c式假幣一定移動了，從而確定假幣一定在3.4中，且此時可以

由a式和c式得到真假幣孰輕孰重，從而第三步簡易稱量可得出結論。

綜上所述，可以通過三步就確定出假幣是哪個

---------分割線是這麼用的么---------

話說這個問題是花旗銀行瑞士分行的面試題目，貌似要求兩分鐘之內做出來。

第一次肯定是分成3堆，每堆4個，取兩堆上稱。

然後需要兩次之內從四個之中找出異常的那一個，而異常又不知道是輕還是重。

所以肯定是信息沒有利用完全——第一次上稱不止得到了一個問題堆（或者說未必能得到），同時可以肯定得到了至少一個沒問題的堆，換句話說通過第一次測量至少得到了四個沒問題的乒乓球，而這四個球絕對是解題關鍵。

百度得到結果發現果然如此（懶）。

http://jingyan.baidu.com/article/0964eca2252bc58285f5362a.html

貼吧上發現這個問題，想了有倆小時，沒想到又在知乎上看到了。

關鍵問題是，第三步能一次稱出異常球來，不外乎是2種情況：

1）知道異常球是輕是重，最多有3個球有疑問；

2）未知異常球是輕是重，最多有2個球有疑問；

————————思路如下——————

第一步，我考慮了2種稱法：

1）分4組，每組3球；稱任意兩組；可排除6個正常球。
這個思路將在第二步時，會有6個疑問球且完全沒有參與過稱重；
2）分3組，每組4球；稱任意兩組；
可排除8個正常球；剩下4個球完全沒有參與過稱重；
或排除4個正常球；剩下8個球參與過稱重；

4個沒有參與過稱重的疑問球，可以由2次跟正常球比對來輕鬆找出異常球；

6個沒有參與過稱重的疑問球，就很難做到。所以第一種稱法沒法繼續。

再說第二種稱法第2種情況，剩下8個參與過稱重的球；

第二步，已知2組共8個異常球的輕重關係；有4個正常球可供比對；

我們最終的目的，是將8個球劃分為2種情況：

1）知道異常球是輕是重，最多有3個球有疑問；
2）未知異常球是輕是重，最多有2個球有疑問；

現在至少我們可以知道，輕的一側如果有疑問，那異常球一定是輕球；反之重側亦然。但兩側都是4個球，沒有滿足我們最多3球的最終目標，所以我們要做調整。

輕的一組（或重的一組也行）可以取下3個來，放外面；如果他們有疑問了，就是說明異常球輕；

重的一組不變位置，但只能留3個，如果有疑問了說明異常球重；

我們把多餘了1個重組球和1個輕組球，互換位置，有問題了的話就2個，不知輕重也木有關係；

此時一側4球（原重側），一側1球。

然後把正常球取3個放原來輕的一組所在位置；

這樣第二步怎麼稱就出來了。

第三步沒疑問，不提。

最後我把稱重過程貼過來：

————————解題過程——————

1）分3組，每組4個。選2組放天平，平衡則說明選中的2組共8球正常。這種情況最簡單，直接排除8個，不提；

如果不平衡，則說明2組共8個中有1個異常球；我們說這種情況。

2）原來輕的一側拿下3個來，換上另外3個正常球；剩下的一個，跟重的一邊互換1個；3種情況：重側依然重（沒動的3個重組有問題且異常球重）；平衡（外面的3個有問題且異常球輕）；重側變輕（重輕互換的倆有問題，不知輕重）；

3）變成2個問題：已知異常球輕重，3個球；或未知異常球輕重，2個球；

其一，3個球選倆稱，平衡則第3個球，如果不平衡則根據異常球是輕還是重來選擇；

其二，2個球，選一個跟正常球稱，平衡則另外一個，不平衡則所選這個；

數學作業題就不要上知乎找答案了

三進位

謝邀找個球館打一會就全分出來了順便拿天平秤一下我的幾塊新買的板

來湊個熱鬧~也不知道對不對...

先分成：

3組 x 4個，編號組1，2，3。

第一次稱：組1和2稱。

===============如果兩組等重=============

說明異常球在3裡面。

從1和2中隨便拿3個球，編號A。

從3裡面拿3個球，編號B。

3裡面剩下一個球，編號C。

第二次稱：A和B稱。

-----------------------如果兩組等重-----------------

說明C是異常球。

第三次稱：C和隨便另一個球稱。可得C球輕重。

----------------------如果B比A重--------------------

說明異常球在B里，並且是重的。

第三次稱：B里隨便拿兩個球稱。

如果等重，剩下最後一個球是異常球。

如果不等重，重的一邊是異常球。

----------------------如果B比A輕-------------------

跟上邊同理。

回到第一次稱：組1和2稱。

==============如果組1比組2重==========

說明異常球是組1和2里共8個球中的一個。

組3共4個球是正常的。

從組1 和組2中分別拿3個球，編號X和Y。

組1剩下一個球編號M，組2剩下一個球編號N。

現在的可能性是：X或M中有一個球重，或者Y或N中有一個球輕。

把X拿下來，用組3中3個正常球代替。

M和N換位。

Y不動。

現在一邊是3個正常球+N，編號alpha。

另一個是M+Y，編號beta。

第二次稱：alpha和beta稱。

----------------兩組等重-----------------

說明異常球在X中，根據上面剩下的可能性，是重的。

第三次稱：X里隨便拿兩個球稱。

如果等重，剩下最後一個球是異常球。

如果不等重，重的一邊是異常球。

-------------alpha更重------------------

說明的可能性是：

N重，或者M或Y輕。

跟第一次稱後的可能性相比：

X或M中有一個球重，或者Y或N中有一個球輕。

一致的只有Y中有一個球輕。

第三次稱：Y里隨便拿兩個球稱。

如果等重，剩下最後一個球是異常球。

如果不等重，輕的一邊是異常球。

-------------beta更重------------------

說明的可能性是：

N輕，或者M或Y重。

跟第一次稱後的可能性相比：

X或M中有一個球重，或者Y或N中有一個球輕。

一致的是M重或者N輕。

第三次稱：M和除了N以外隨便一個球稱。

如果等重，說明是N輕。

如果不等重，就是M重。

我記得有一本書叫《演算法謎題》，可以看一看哦！

下面是目錄：

講解的很詳細，自己動手查一下答案也是極好的。

第一次1,2,3,4,和7，8,9,10

第二次2,3,4,5和8,9,10,11,

第三次3，4,5,6和9,10,11,12

三次都平不可能，一共有26種組合，每種組合都對應唯一解

444，4個球，2次

總共3次

補充一下，對於更一般的問題

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

這個在知乎幾年前就討論過，而且有了很好的答案了。

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

第一步，四對四稱重，平衡簡單不論，不平下步。第二步，各選兩重一輕稱，平衡簡單不論，不平則重側兩重或輕側一輕有問題，下步。弟三步，兩重互稱，平則余球，不平則重球。

第一次：分兩堆，各六個，置於天平兩端，取重一側六個做第二次稱量；

第二次：又分兩堆，各三個，如第一次方法稱量，得重一側三個；

第三次：隨意取兩個並分置於天平兩側：若平衡，則剩下的為重球；若不平，則下降一端為重球。

若異常球為輕，將如上方法反之即可。