當前位置: 華文星空 > 體育

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

2017-12-21體育

第一次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)個數)。

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

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