在看過這麼多的秤重問題之後,可以看到秤重問題變化很多,是否有一個固定的方式可以解決各種不同的類題?

這一篇文章將說明利用一些數學或其他的方法來補助我們解決相關的類題。

首先你會發現我的解法都是利用了兩個基本的方法來進行:

  1. 編號法,將每個測量物都給定編號,甚至分組。
  2. 窮舉法,進行比較,並將所有可能列出。

當題目較簡單的時候,可以利用簡單的文字說明就可以講出正確答案,但是問題一旦變得複雜,可能性變化很大,就沒辦法三言兩語說得清楚,這時候利用上面兩個方法,就可以講得很完整,思路也比較清楚,相對的可能需要寫得很冗長。

即便是利用上面的方法進行推論,也可能不知道到底要如何進行比較才是正確的,這時候可以用數學的方法來協助推論,我們知道每次的比較最多會得到三個結果,這意味著每一個回合最多能給出三種可能,例如下面的例子:

三顆球,一顆較輕。

將球編號1, 2, 3進行比較,

  1. 1=2,則3輕。
  2. 1>2,則2輕。
  3. 1<2,則1輕。

利用編號和窮舉可以寫出上面的結果,這個題目只有三個可能性,所以我們能在一個回合得到答案;並且要注意的是,利用編號和窮舉法的推論結果,每個編號組合都一定會出現在推論中,上面1輕2輕3輕都存在一條路徑,如果有漏掉的,表示你的推論不正確。

如果今天題改成四顆球,四顆球則有四個可能,但一個回合最多三個可能,意即無法在一次秤重中找到答案,至少要兩次。

現在我們知道一個回合可以得到三種可能,進一步探討兩個回合可以得到幾個可能?答案是3 * 3 = 9,9個可能,其他3個回合或是4個回合也是一樣的算法。

所以如果一道題目如果可能性有10種,有沒有可能在兩次秤重找到答案?答案是否定的。

遇到難題的時候你可能會覺得:『這根本無解吧』,不過現在我們學會了找出一個題目的最少秤重次數,也就能判斷到底有沒有可能達成,前提是如果你能算出題目的可能性數目的話。

如何將上面的數學方法應用在推論?可以看下面的例子:

六顆球,一顆較輕,兩次內找到答案。

將球編號1~6進行比較,而這時我們使用一個錯誤的推論:

  1. 1=2,則3, 4, 5, 6其中一個較輕。
  2. ...

這個例子我們將1, 2作為第一回合比較,我們可以看到相等時候的情況,它意味著有問題的球在其他四顆球,這時有四個可能性,但我只剩下一次秤重機會,也就表示這個推論是錯的,再往下走也不可能找到答案了。

上面的推論也可用另一個角度來看,如果繼續往下走的意思是:在ㄧ次秤重中,從四顆球中找到一顆較輕,根據之前的說明,這個問題是不可能的;這相當於是一個子問題。

總而言之就是,當題目的可能性大於秤重最大可能性時,就是無解,或者說當子問題的可能性大於剩餘秤重次數最大可能性時,就表示推論錯誤

我們拿最難的智力測驗 - 秤重問題(五)來作簡易的分析:

9個金幣當中有2個假幣,7個真金幣每個重 500 克,其中一個假幣輕了 100 克 ,即 400 克,另外一個假幣重了 100 克,即 600 克,1 個沒有刻度的天秤秤四次找出 2 個假幣,而且要分出哪個重了,哪個輕了。

首先我們來判斷一下到底能不能在四次之內找到答案,四次的可能性為3 * 3 * 3 * 3 = 81,而題目的可能性為9 * 8 = 72,所以是可以的。

將球編號並分堆如下:

A = [1, 2, 3, 4]

B = [5, 6, 7, 8]

C = [9]

  1. 如果A=B,則A或B有問題。(剩下3次,27種可能性;A或B有問題,4 * 3 + 4 * 3 = 24種可能行,可以找出答案)
  2. 如果A>B,則[A重, B或9輕]或[A或9重, B輕]。(4 * 4 + 2 * 4 = 24,可以找出答案)
  3. 如果A<B,則[A輕, B或9重]或[A或9輕, B重]。(4 * 4 + 2 * 4 = 24,可以找出答案)

每條路都可以找出答案,表示這回合的推論是正確的,再往下走用同樣的方式即可逐步找到全部答案。

最後還有一個技巧是,大於和小於的是剛好完全相對,也就是說,大於的路徑找得到答案,小於就找得到,所以每回合推論和檢驗的時候,只需要針對等於和大於小於其中一個進行就可以了。

延伸閱讀

上一篇 智力測驗 - 秤重問題(五)

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()