榕城老應

用調侃去書寫思考,以故事來敘述理論。
個人資料
正文

稱球問題(1)

(2011-02-14 20:10:16) 下一個


       榕城老應

我同學中一位才女給朋友的孩子出個練腦題:"有十三個球,其中十二個重量相同,隻有一個次品不知是輕還是重了。請用天平稱三次,將這個次品找出來。"
 
這題我在念研究生午餐時聽說過,當時想了一小時。暈。不了了之。後來這麽多年也見過不少稱球題,都沒這道題難度高。雖然她是給小孩喂招的,考慮到這道題的難度,咱大老爺來接也不丟份。
 
題中球數目有限,隻要有耐心在紙上寫寫畫畫並不難得解。所以考大人的是不借外物,虛空冥想,心智澄明的功力。智力的一項成分是思考堆棧(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個球三次足矣。反過來設計考題:稱四次可以分辨最多幾個球呢?有沒有一般性的答案,這留給大家傷腦筋,我下次再談。

[ 打印 ]
閱讀 ()評論 (0)
評論
目前還沒有任何評論
登錄後才可評論.