稱球問題（1）

來源: ying312 於 2011-02-15 10:17:48 [檔案] [博客] [舊帖] [給我悄悄話] 本文已被閱讀：次 (3352 bytes)

榕城老應

我同學中一位才女給朋友的孩子出個練腦題："有十三個球，其中十二個重量相同，隻有一個次品不知是輕還是重了。請用天平稱三次，將這個次品找出來。"

這題我在念研究生午餐時聽說過，當時想了一小時。暈。不了了之。後來這麽多年也見過不少稱球題，都沒這道題難度高。雖然她是給小孩喂招的，考慮到這道題的難度，咱大老爺來接也不丟份。

題中球數目有限，隻要有耐心在紙上寫寫畫畫並不難得解。所以考大人的是不借外物，虛空冥想，心智澄明的功力。智力的一項成分是思考堆棧（Call Stack）的深度，據說有個天才能夠考慮十七層的深度而不亂套。咱們現在記性不如前，但經驗豐富了，可以想出隻需要記住較少幾層的算法來。

昨晚熟睡，夢中忽得答案。

下麵是思考的過程。

13個球要稱量，肯定要分3堆。放外邊那堆，喵一眼就知道不外乎隻能考慮3，5，7個。若放7個，怕是傻了，剩下兩次怎麽分得清？3個，太天真了。最可能是5個。蒙對了這數目，省你不少力氣，不然要多費一層思考的堆棧來排除了。

放外邊那堆5個，剩下8個，兩邊4個上天平去稱。

先考慮容易的情況，天平稱得一樣重。次品就在放外邊那堆5個中了。再將這5個分3堆，放外邊2個，剩下2個放天平左邊，1個右邊再加上1個第一次稱過已知是正品的球。如果還一樣重，將放外邊2個隨便拿一個上天平與正品相比就能知道是這2個中哪一個了。思考退回一層，如果不一樣重，比如說左重右輕。那麽如果次品在左邊的一定較重，如果在右邊則它較輕。將左邊那2個上天平，它們不平衡，重的那個有問題。若平衡，右邊隻有一個未判明的，那就是它了，而且知道次品是輕的。

好了，容易的情況解決了，思考的堆棧退回一層。第一次稱的8個，兩邊4個的天平，左重右輕的情況。左邊留下4個，右邊留下2個。撤下右邊2個。留在天平的怎麽折騰先不管，如果第二次稱分不出輕重來。次品就在撤下這2個中，再稱一次就能得答案。

回來考慮天平左邊留下4個，右邊留下2個的殘局該怎麽稱？對調左右天平中的各一半的球，再稱一次。結果不外乎：平衡，左重，右重。平衡的上麵已考慮了。還是左重則次品在沒掉換的左邊2個，右邊1個球中，依前麵處理5個球稱過第二次後的邏輯，再稱一次可解決。若是右重了，次品則在交換過的3個球中，稱一次也可解決。

在這個過程中，我們知道了分辨13個球三次足矣。反過來設計考題：稱四次可以分辨最多幾個球呢？有沒有一般性的答案，這留給大家傷腦筋，我下次再談。