108 中山資工所數學考點分析

題型與配分

科目名稱「離散數學」【資工系碩士班甲組】，題號 434004，考試時間 100 分鐘，「不可以」使用計算機（問答申論題），全卷試題僅 1 頁、8 題、100 分。

卷首明訂：「you should write down detailed steps for the solution to each problem; otherwise, no credits for that problem will be given.」

只寫答案不給分——這點與成大「計算機數學」完全一致，和台大、中央的選擇題形式相反。

中山離散數學是甲組專屬科目（乙組考的是「工程數學」，資安碩班考的是「離散數學與演算法」，是不同的卷子）。

逐題考點

• 第 1 題（14%）｜委員會組合計數：從 10 男 10 女中選 14 人
• (a) 7%：恰好 7 男 7 女 → C(10,7) × C(10,7)
• (b) 7%：至少 8 位男性 → 依男性人數 8、9、10 分case 相加。注意男性最多只有 10 人、女性至少要 4 人
• 第 2 題（10%）｜命題邏輯等價驗證：驗證 ¬[(r → p) ∧ (p → q) ∧ (q → r)] ⟺ ...，用真值表或邏輯律逐步化簡
• 第 3 題（14%）｜真子集的形式化
• (a) 7%：把 A ⊂ B（真子集）寫成帶量詞的敘述 → ∀x(x∈A → x∈B) ∧ ∃x(x∈B ∧ x∉A)
• (b) 7%：取否定得到 A ⊄ B 的條件 → ∃x(x∈A ∧ x∉B) ∨ ∀x(x∈B → x∈A)
• 第 4 題（14%）｜棋盤上的正方形計數
• (a) 7%：9×9 棋盤中有幾個 3×3 正方形（答案 7×7 = 49）
• (b) 7%：推廣到 n×n 棋盤中的 k×k 正方形（(n−k+1)²）
• 第 5 題（12%）｜子集和不可能全相異：S 是五個正整數的集合、最大值不超過 9，證明所有非空子集的和不可能兩兩相異。鴿籠原理：非空子集有 2⁵−1 = 31 個，但和的範圍最多是 1..(9+8+7+6+5) = 35，再細算可行範圍就會撞鴿籠
• 第 6 題（12%）｜形式語言的證明：A ⊆ Σ* 且 A 非空，證明若 A² = A 則 λ（空字串）∈ A。用「取 A 中長度最短的字串」論證
• 第 7 題（14%）｜生成函數求係數
• (a) 7%：求 (1 + x + x² + x³ + …)⁷ 中 x⁶ 的係數 → 即 1/(1−x)⁷ 的展開，係數為 C(6+7−1, 6) = C(12,6)
• (b) 7%：推廣到 n 個因式的一般情形
• 第 8 題（10%）｜同餘與整除：設 k, d, p, q ∈ Z 且 p, q > 0，證明「若 k ≡ d (mod q) 且 p | q，則 k ≡ d (mod p)」。核心是 q | (k−d) 與 p | q ⇒ p | (k−d)

這份考卷的難點

1. 100 分鐘要寫完 8 題全申論，平均一題只有 12 分鐘，而且每題都要完整推導。時間壓力是中山離散最大的門檻。
2. 第 5 題的鴿籠要同時處理「子集個數」與「和的可能範圍」兩邊，並且證明範圍小於子集數。光說「用鴿籠原理」沒有具體數字不給分。
3. 第 6 題的形式語言證明在多數離散課本屬於自動機章節的邊角，沒讀過就完全不會下筆。技巧是取 A 中最短的字串 w，由 A² = A 推出 w = uv 且 u, v ∈ A，再用長度矛盾推出 u 或 v 為 λ。
4. 第 3 題要寫「量詞敘述」再「取否定」，兩步都要正確，而且否定要把 ∀ 換 ∃、∧ 換 ∨。

準備建議

• 中山離散的題目幾乎全部出自 Grimaldi《Discrete and Combinatorial Mathematics》——第 1、4、5、7 題都是該書的課後習題原型。準備中山，讀 Grimaldi 比讀 Rosen 有效率
• 「子集和相異性」的鴿籠題在 111 年原封不動重出（只把「五個正整數、最大值 9」換成「七個正整數、最大值 21」），是最明顯的重複題
• 同餘的證明題（108 第 8 題、109 第 9 題、112 第 8 題）三度出現，其中 109 與 112 是同一題
• 生成函數求係數是中山每年必考，要熟 1/(1−x)ⁿ 的展開係數 C(n+r−1, r)
• 作答必須寫完整推導，練習時就要按申論格式書寫，不能只算出答案