從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扯上關係！