從ACM回來的數學題（二）

題外話1：大家有留意的話，這個blog是由一班數學資料庫成員合作而寫的。昨日的數學資料庫例會之後，我們的作者名單增加了四個人。可以預料手記的更新將會更為頻密，為廣大網友提供更多的數學資訊。

題外話2：數學資料庫在昨日下午已經換上全新的主頁設計。自己覺得這個設計蠻好的。以往的設計需要網友們scroll down才能見到每一個項目的更新，現在則不用了。而主頁那種顏色的配搭我覺得還真美的。在此要感謝MD的會員Vris花了很多時間去設計這個新主頁。

---

入正題。上回預告，今次講第二題。

越南Danang的ACM/ICPC Problem C。題目是這樣的：我們稱一組連續k個質數為一個「k質數組」。例如(31,37)是一個「2質數組」，(83,89,97)是一個「3質數組」，而(53,61)則不是「2質數組」，因為53和61之間還有一個質數59。而每一個「k質數組」的重量就是該k個質數中最大的質數和最少的質數之差。例如(11,13,17,19,23)就是一個重量為23-11 = 12的「5質數組」。現在給出a,b符合條件1 < a < b < k 和 d ，要找出在 [a,b] 內有多少個重量為d的「k質數組」。

當時想了一想，如果test case當中有 d = 0 ， k = 1，那不就是問我 a和b之間有多少個質數嗎？若然 a 和 b 均是很大的數，那麼要得到一個好的估計還不難（就是用Prime Number Theorem吧），但要無誤差地說出在某個特定的range內有多少個質數，唯一已知的方法就是逐個試。

最後因為a和b太大，我們認為TLE（Programming Contest術語，全寫為Time Limit Exceeded）的可能性非常大，所以我們没有做。比賽完畢後，相信百多隊中只有兩隊能夠完成這題，而其中一隊是相熟的中山大學隊。一問之下，才知道要用一個Radin-Miller Primality Test。

一般情況下，如果給的數n不太大的話，我們慣了用以下的以下的algorithm去驗它是否質數：

1)
If n is even but not 2, then it is NOT prime, done and leave this procedure.

2) for (i=3 ; i<=sqrt(n); i+=2) if (n mod i = 0) then n is NOT prime, done and leave this procedure.

3) n is a prime, terminate.

上面的algorithm的基礎就是基於一個定理：如果 n 是合成數，它最小質因數必然 <= sqrt(n)。稍為認識analysis of algorithm的人都應該知道這個 algorithm的run time是O(sqrt(n))。如果 n 是一個八位數，那麼用這個 algorithm 去驗証 n 是否質數，就需要試最少三千多次。若然只做一兩次還好，但若然有十萬個八位數要你試，最壞情況要試過億次。別以為現在的CPU越來越快，要這樣試，我辦公室內的電腦已經比一般家用電腦快，都要大約8.75秒。而這道比賽題目極有可能有test case需要我們試一千萬個數，所用的時間粗略估計會是8.75秒的20至100倍。而比賽的程式運行時間是有限制的，一般來說不會超過一分鐘。所以這個方法是不可以用來解決這道題目的。

Radin-Miller Primality Test的概念是這樣的。如果 n 是一個質數，那麼根據費馬小定理，對於所有 a < n，都有 a^n-1 = 1 (mod n)。若把 n-1 表成 2^s d（d是奇數），我們可以得到

a^d = 1 (mod n)

或

a^{2^r d} = -1 for some 0 <= r <= s-1

Radin-Miller Primality Test就是使用以上定理的contrapositive。只要我們找出一個 a 使得以上兩條等式均不成立，那麼 n 就不可能是質數。當然，要找出一個這樣的 a 也不見得容易。但後來有人證明了對於少於 2,152,302,898,747 的 n ，只要試 a = 2, 3, 5, 7 或 11，若然對於這五個 a 的數值，都可以符合以上定理中兩組等式的其中一組，那麼 n 就是一個質數了。

就是因為這個結果，對於每個 n 驗證是否質數的時間就變成了 5 lg n。若 n 是一個八位數字，那麼最多大約要做135次，比起上面那個"naive algorithm"的過3000次好太多了。

用了這個Radin-Miller Primality Test後怎樣完成餘下的部分就不算難，有興趣的讀者可以自己想想。

說回比賽。原來我其中一個組員是知道這個primality test的，但他當時覺得用了這個test後程式運行時間仍然太大，所以決定放棄。無言。

從ACM回來的數學題（一）

不經不覺，已經接近一個月未在此作出更新。這種情況在今年八月提出建立「數學資料庫手記」時其實已經預料得到（事後孔明？）。自己認為，如果有一個人一年365天都是清清閒閒的話，他所寫的網誌大概也不會好看。而「數學資料庫手記」這麼精彩（難題：請在日常生活中找出比我這句更為硬銷的廣告），撰寫該網誌的成員年中有些時間比較忙也屬意料中事。

可幸的是，手記成立接近兩個月，充分發揮了"joint blog"的威力，大家你棒接我棒，令手記更新不斷。透過造訪紀錄看到，兩個月內手記已經得到一些老師和學生的推介。當然，我們的目標是令到更多更多的老師和學生認識「數學資料庫」和「數學資料庫手記」，充分利用兩個網站內的數學資源，好好的認識課程以外數學有趣和嚴謹的一面。

---

那麼我在過去一個月忙些甚麼呢？其中有七天，我到了南韓首爾和越南Danang參加ACM/ICPC，全寫為Association of Computing Machinery的International Collegiate Programming Contest，簡單點說就是以大學為單位的電腦編程競賽。每年的題目雖然都以Computer Science的題目為主，但不時亦會加插一些數學題。今天先挑在首爾見到的一條簡單「數學題」說說。

題目是這樣的：有一個 2 x n 的tag，有很多方法用 1 x 2、 2 x 1 和 2 x 2 的小塊去把它密舖。這些 2 x n 的tag可透過閱讀條碼機閱讀，從而確認身份。可是，用者可能將這個tag旋轉了180^o。因此閱讀條碼機認為一個2 x n 的tag和這個tag旋轉了180^o後的2 x n tag是一樣的。舉個例子，以下兩個tags是被認為一樣的：

而程式的工作就是輸入n後輸出不同的tags。

解題的方向分幾步，第一步就是先不考慮旋轉，數有多少個tags。考慮2 x n的tag右上角的正方形，它必然會被覆蓋，而覆蓋它的可能是 1 x 2 、 2 x 1 或者 2 x 2的小塊。若它是被 1 x 2的小塊覆蓋，那麼右下角的正方形也一定是被 1 x 2的小塊覆蓋，那麼餘下的就是一個 2 x (n-2)的tag。同理若右上角的正方形被 2 x 2的小塊覆蓋，餘下的也是一個 2 x (n-2)的tag。若右上角的正方形是被 2 x 1的小塊覆蓋，餘下的則是一個 2 x (n-1)的tag。因此，若定義C_k為（不考慮旋轉時）2 x k的tag不同的覆蓋方法數目，則有遞推關係
C_k = C_k-1 + 2C_k-2

知道C₁ = 1和C₂ = 3後，我們就可以用電腦以O(n)時間找出C_n。當然，這個遞推關係你甚至可以找到C的closed form，方法可參考「數學資料庫」筆記 - 「數列與遞歸關係」第13至15頁（這次感覺不那麼「硬」了吧）。

第二步則是找出經過180^o旋轉後沒有改變的2 x n tags的數目。我們定義D_n為符合這個條件的tags的數目。當k是奇數時，可以証明它中間的兩個正方形一定是被一個2 x 1的小塊覆蓋著。因要符合條件，這些tags的左邊 2 x (k-1)/2的sub-tag覆蓋方法會決定了右邊2 x (k-1)/2的sub-tag的覆蓋方法。因此，
D_k = C_(k-1)/2

當k是偶數時，有點麻煩。考慮中間的4個正方形，因要符合旋轉後不變的條件，它的密舖方法有兩種可能。第一就是被兩個 1 x 2 的小塊覆蓋或被一個 2 x 2 的小塊覆蓋。第二就是沒有小塊橫跨左邊的 2 x k/2 和右邊的 2 x k/2 subtags。這樣考慮下，得
D_k = 2C_(k/2)-1+C_k/2

當用電腦儲存C_k後，D_n可在O(n)時間內求得。

對於任意的n用O(n)時間得到C_n和D_n後，想一想就知道答案是D_n + (C_n - D_n)/2 = (C_n + D_n)/2。

下一次說說兩條在越南Danang見到的題目，一條關於質數，另一條竟然和group theory扯上關係！