2009年10月4日

用模型來解決問題—組合數學與代數

作者/翁志文(任教交通大學數學建模與科學計算所)

為解決複雜的問題,數學家常常會運用符號,將問題轉換成簡單的數學式。本文以點燈問題為例,介紹如何運用圖形與線性代數建模,來幫助解題。

中學生最先碰到的代數問題,可能是利用未知數x、y等符號,將「雞兔同籠」此類生活上的問題寫成數學式(此過程稱為「代數建模」),然後求解。好的代數建模不但容易理解,也有助於解題。在工程應用上,一個代數建模可能出現一萬個未知數,因此盲目利用電腦去求解是不可行的。通常我們必須為這些未知數安排某種組合結構,然後利用此結構去解釋代數建模的正確性及一般性,同時也看出如何簡化求解步驟。

本文試著以一個「點燈問題」為例,來看它的「組合模型」如何給人數學的直觀,以利推廣,並且探討「代數模型」如何幫助求解。文中將出現一些線性代數及組合數學的名詞,我們將試著以口語解釋或舉例,讓未學過這些名詞的讀者能明瞭;另一方面也希望僅從教科書學過這些名詞的讀者,在讀完文章後,能感受它們對解題的幫助,而有更深刻的印象。最後我們將介紹點燈問題與代數中「群論」研究的關聯,及將來可能的研究方向。

點燈問題

假設有m 個房間排成一直線,其中有些房間燈亮,有些房間燈暗。每一個房間都有一個控制燈的開關,這個開關能同時改變所有相鄰房間的明暗,但無法改變不相鄰及這個開關本身所在房間的明暗。現在有一個人,他每走進燈暗的房間,就會動一下開關,去改變相鄰房間燈的明暗,而且他只在走入燈暗的房間時會去改變開關。試問他能把所有暗的房間的燈都點亮嗎?這個答案很明顯是不可能的,因為每次他動開關的時候,他所在房間的燈還是保持暗的。

另一個問題是:能夠只留下一個房間燈暗,而點亮其他所有房間的燈嗎?以下稱此問題為「點燈問題」。換句話說,點燈問題是問:如果剛開始m 個房間中至少有一房間是暗的,最後能剛好點亮m-1盞燈嗎?看點燈問題的解答之前,讀者可以試解底下圖一的情形。

圖型建模

對以上的點燈問題,我們可以用m+1個點和m 條邊所構成的直線圖型,來描述這些房間的相鄰關係。此時邊代表的是房間,而每條邊的兩端都各有一個點,且不同邊可共用點;當兩邊共用一個點,表示它們所代表的房間相鄰。我們還可以用邊的粗細分別表示房間的暗明(粗是暗、細是明),如圖二。

這種以「邊」代表房間的圖型,能推廣到許多種房間相鄰的狀態,但無法描述所有的情形——像是一個房間連接到其他三個獨立房間的情形便無法作圖。讀者試試看能否畫出一個有四條邊的圖型,其中三條邊兩兩不能有共用點,但每一邊又必須與第四條邊有共用點。

點燈問題的另一種圖型建模是以「點」為房間,兩點以邊連接代表房間相鄰,並以點的虛實分別代表房間的明暗,如圖三。

不管房間相鄰的狀態如何,都能以點為房間的圖模型來表示。讀者應該可以輕易地畫出上述「四個房間為點,僅以一個房間連接到其他三個獨立房間」的圖模型。此時讀者亦可想想看,自己喜歡哪種模型。稍後讀者會發覺,以邊為房間的圖模型在求解時較直觀,也能領悟「圖模型」是一種很有用的「組合模型」。

線性代數建

模點燈問題的另一種建模,是以一個只填入0 、1 兩數字的m維向量,來代表m個房間的明暗狀態,其中0 代表燈亮, 1 代表燈暗。圖一的例子中,所有房間只有2 、3 、5 號三間房間燈亮,因此向量建模如下:(1, 0, 0, 1, 0, 1, 1, 1,..., 1)

如果房間不是剛好排成一直線,這一種建模沒辦法看出房間的連接關係,所以必須有圖模型輔助。【更詳細的內容,請參閱第478期科學月刊】

回本期目錄

沒有留言: