Quod Erat Demonstrandum

2008/05/05

習,數飛也 – 四階拉丁方及四階數獨

Filed under: Additional / Applied Mathematics,Junior Form Mathematics,Teaching — johnmayhk @ 1:59 下午


習,數飛也(參考《說文解字》全文檢索測試版

香港數學課改『總舵手』李柏良先生(教育局總課程發展主任(數學)個人網頁)在 29/4 的數學教育研討會上,把『數飛』,聯想到數算麻將的『飛數』,即係『呢副牌可以叫幾多飛』。台下的聽眾雀躍,大概是因為看到『生活的數學』吧。我慘,我是火星人,不懂麻將(其實初中時,家父教過在下,但自己沒有『操練』,所以現在已不懂了),如果將來的數學考卷問什麼『大四喜』,『十三么』之類,我的情況同看『會考潮文』一樣,死得。

隨後,香港教育學院數學系高級講師鄭振初先生提到『數數』(counting)是很好的數學思考題,他問我們有多少個『四階數獨解』?
A. 4! \times 4 \times 4 \times 4
B. 4! \times 12
(大家先想想,答案是 A 還是 B?)

下圖為四階數獨一例

聞說,數獨沿於拉丁方(Latin Square),是瑞士數學家歐拉於 1779 年發表的一篇題為《有關一類新幻方》引進的概念(參考蕭文強教授著的《1,2,3……以外-數學奇趣錄》P.144)。有關拉丁方的數目及詳情可看 mathworld 的介紹。

必須指出,拉丁方不一定是數獨解。下面的拉丁方就不是四階數獨的解了。

上面 mathworld 的連結,已經給出數算 n 階拉丁方的公式,見下
n!(n - 1)!L(n,n)

所以,四階拉丁方的數目,共有 4!3!L(4,4) = 4!3!\times 4 = 576。現在讓我 down-to-earth,真的去計算一下四階拉丁方的數目。

對某一拉丁方,例如

(原始圖)

把其中兩行對調,結果也是一個拉丁方。比如把上述拉丁方的第 2 和第 3 行對調,仍是拉丁方,見下

所以,對於(原始圖),把 4 行『排隊』,即我們可以產生 4! 種拉丁方。

現在著眼(原始圖)的第一行。固定第一個數,即 1,其餘 3 個數(即 2,3 及 4)也可『排隊』,共有 3! 種可能性。考慮其中一種可能性,比方說 1324。即把(原始圖)中的第一行改變為 1324,那麼,其餘的 3 行,也進行對應的變換,即是說:所有 2 變成『3』;所有 3 變成『2』,那麼,我們可以產生新的拉丁方,見下:

亦即是說,一種可能性,對應著一個拉丁方,於是,當固定第一行第一個數,我們可產生 3! 個拉丁方。

總結上述兩點,由(原始圖)出發,我們已可數算出 4!3! 個不同的拉丁方。

好了,跟著是比較煩的問題:有多少種所謂的(原始圖)?即是說,還有多少拉丁方,不能由上文提及的方法(即進行行的置換,及第一行的 2,3,4 位置的變換)得出?讓我『暴力』地處理。

先固定第一行,再固定第二行第一個數(即 2),見下

那麼第二行其餘空格,我們只可填上:143,341 及 413;即
 
 

現在餘下兩行填上 3,即
 
 

填 4,得
 
 

到填 1,2;大家留意,除了下圖可以有兩種不同的方法外,其餘只得一種。

於是我們得到以下 4 個不同『結構』的所謂(原始圖):

 
 
 

如前的討論,每個(原始圖)可以產生 4!3! 個不同的拉丁方。剛剛得到 4 個『不同結構』的(原始圖)(亦即是 mathworld 說的 L(4,4) = 4。),所以四階拉丁方的數目共有 4!3!\times 4 個。

拉丁方還有很多有趣的性質和應用(最常見是有關實驗設計,強烈建議未知的同學看看《1,2,3……以外-數學奇趣錄》一書的簡介。研究拉丁方,可以有很多數學內容。嗯,或許參考下文,有關應用圖論證明『拉丁長方必可擴充成拉丁方』
http://www.math.ucsb.edu/~mckernan/Teaching/04-05/Spring/137B/l_18.pdf

好了,現在數算『四階數獨解』的數目。『四階數獨解』比拉丁方多了些規限,數的時侯要小心。以下又以『暴力』解之。

先填左上角的四小格,見下

共有 4! 種填法。

到右上角的兩個位,可放 34 或 43 兩種;比方放34,見下。

好了,這裡要小心,頗易數錯。我們要分兩個情況。

情況一:在 34 下放 21
情況二:在 34 下放 12

它們表面好像差不多,但數法其實不同的。

情況一:在 34 下放 21

隨即考慮把餘下的兩個 1 分別放在左及右下角的大格,可以有 2 種情況,見上圖。

跟著,我們便可順利填滿餘下小格。即

情況二:在 34 下放 12

類似地,考慮把餘下的兩個 1 分別放在左及右下角的大格,可以有 2 種情況,見上圖。

但和情況一不同,上述 2 種情況各自衍生另外 2 種情況,即情況二共有以下 4 種情況:

所以,上述兩個情況共 6 種;因開始時我們可以選擇 34 或 43 兩種;即是,當固定左上角四小格的數字,可衍生 6 \times 2 = 12 種不同情況,所以,四階數獨解共有 4! \times 12 個。即鄭講師問題的答案是 B。(答案 A 的錯誤在於包括一些不可能的數獨解)

上文是用暴力法的結果,毫不漂亮,期望組合學高手以一兩句解之。

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: