111 中山資工所數學考點分析
8 題各 10 分。第 1 題直接重出 108 年的鴿籠題、第 7 題用 COVID 疫情包裝遞迴式還要換算成實際日期，是十年來最特別的一題。
題型與配分
科目名稱「離散數學」【資工系碩士班甲組】，題號 434004，考試時間 100 分鐘，「不可以」使用計算機（問答申論題），全卷試題僅 1 頁、8 題、100 分，每題整齊 10 分。
| 題號 | 主題 | 配分 |
|---|---|---|
| 1 | 子集和相異性（鴿籠） | 10% |
| 2 | 有限狀態機的狀態圖 | 10% |
| 3 | 整除關係的有序對個數 | 10% |
| 4 | 迴文計數 | 10% |
| 5 | 三進位序列的奇偶機率 | 20%（10+10） |
| 6 | 二進位字串的遞迴 | 20%（10+10） |
| 7 | COVID 疫情包裝的遞迴 | 10% |
| 8 | 相異彈珠放入相異罐 | 10% |
「沒有詳細步驟就不給分」（卷首明訂），不可以使用計算機。
逐題考點
- 第 1 題（10%）｜子集和不可能全相異：S 是七個正整數的集合、最大值不超過 21，證明所有非空子集的和不可能兩兩相異。這題是 108 年第 5 題的原題換數字（原為五個數、最大值 9）。做法：非空子集有 27−1 = 127 個，但和的範圍最多是 15+16+…+21 = 126 < 127 ⇒ 鴿籠
- 第 2 題（10%）｜有限狀態機：畫出狀態圖，接受語言 **{0,1}\{11} ∪ {0,1}\{01}，也就是「以 11 或 01 結尾」= 「倒數第一位是 1**」。看穿這一點只需兩個狀態
- 第 3 題（10%）｜整除關係的有序對個數：A 是 6680 的所有正因數集合，R 定義為 xRy ⟺ x | y，求 |R|。先分解 6680 = 23 × 5 × 167，因數個數 4×2×2 = 16；有序對數要對每個因數 d 計算「d 的倍數且仍是 6680 因數」的個數再加總
- 第 4 題（10%）｜迴文計數：固定 n ≥ 5，若 1 ≤ t ≤ ⌊n/2⌋，以 t 開頭的長度 n 迴文有幾個——要分 n 為奇／偶討論中間位置
- 第 5 題（20%）｜三進位序列的奇偶性機率：隨機產生 26 位三進位（0,1,2）序列
- (a) 10%：0 的個數為偶數且 2 的個數為偶數的機率
- (b) 10%：三種數字都是偶數個的機率（26 是偶數，所以這是可能的）
- 解法是生成函數／根的濾波（roots of unity filter）：
[(3ⁿ + 1ⁿ + 1ⁿ + (−1)ⁿ)/4]型公式 - 第 6 題（20%）｜二進位字串的遞迴
- (a) 10%：長度 n 且無連續兩個 0 的字串個數 an，求並解出遞迴式 → an = an−1 + an−2（Fibonacci），a1 = 2、a2 = 3
- (b) 10%：長度 n、無連續兩個 1 且最後一位是 0 的字串個數 bn，求並解出遞迴式
- 第 7 題（10%）｜用疫情包裝的二階遞迴：pn = pn−1 − 0.3pn−2、p0 = 0、p1 = 1，問第一例記錄在 2019 年 12 月 27 日的情況下，機率首度降到 小於 0.01 是哪一天。要先解出封閉式（特徵根為複數或無理數），再逐週代入找出最小 n，最後換算成實際日期
- 第 8 題（10%）｜相異物放入相異容器：20 顆顏色都不同的彈珠放入 6 個相異罐子 → 每顆彈珠獨立有 6 種選擇 → 620。陷阱在於「same size」讓人誤以為彈珠相同，但題目明寫「each marble is a different color」
這份考卷的難點
- 第 7 題要算到「具體日期」：先解遞迴、再找最小的 n 使 pn < 0.01、最後從 2019/12/27 起算 n 週。禁用計算器的情況下要手算 0.3 的冪次，是十年來最耗時的一題。
- 第 5 題的 roots of unity filter 是生成函數的進階技巧。若不會這招，只能用遞迴慢慢推 26 步，時間上不可行。
- 第 3 題的 6680 要先質因數分解（23×5×167，167 是質數），然後計算整除關係的有序對數 = ∏(ei+1)(ei+2)/2，很多人會誤算成因數個數的平方。
- 第 8 題的文字陷阱：「20 marbles of the same size」與「each marble is a different color」並列，要抓到顏色不同 ⇒ 彈珠可區分，答案是 620 而不是重複組合。
準備建議
- 第 1 題是 108 年第 5 題的原題換數字——中山的重複率相當高，把 108–115 八份全部寫過一次是最有效率的準備
- 有限狀態機（111 第 2 題、114 第 5 題）連兩次出現在中山離散，是其他學校數學科少見的考點
- roots of unity filter（111 第 5 題、114 第 8 題）連兩次出現，要背下「偶數個某符號」的標準公式
[(k+1)ⁿ + (k−1)ⁿ]/2型 - 二進位字串的無連續 0／1 遞迴（111 第 6 題）是 Fibonacci 的標準變形，中正也連三年考同類題
- 中山的題目幾乎全部出自 Grimaldi《Discrete and Combinatorial Mathematics》，該書的 Chapter 1（計數）、Chapter 8（排容）、Chapter 9（生成函數）、Chapter 10（遞迴）是命題主戰場