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

題型與配分

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

「沒有詳細步驟就不給分」（卷首明訂），不可以使用計算機。

逐題考點

• 第 1 題（10%）｜多項式展開係數：求 (3a − b + 5c + 3d − 8)²⁵ 中指定單項式的係數。用多項式定理（multinomial theorem）：係數 = 25!/(n₁!n₂!…) × 各項係數的冪次乘積
• 第 2 題（10%）｜互質證明：對任意 n ∈ Z⁺，證明 12n+17 與 8n+11 互質。做法是用輾轉相除找出兩者的整數線性組合等於 1（2(12n+17) − 3(8n+11) = 1）
• 第 3 題（10%）｜遞減子序列的鴿籠：25 個大小互異的倉庫，問最少能找出多長的連續遞減序列。這是 Erdős–Szekeres 定理的包裝：n²+1 個相異數中必有長度 n+1 的單調子序列，25 = 5² ⇒ 至少長度 5
• 第 4 題（10%）｜真前綴的字串計數：Σ = {t, v, w, x, y, z}（6 個字母），求 A 中以 xyz 為真前綴的字串個數。與 110 年第 4 題同型（該年是 5 個字母、前綴 xy）
• 第 5 題（10%）｜數列卷積：a_n = (−1)ⁿ、b_n = (−1)ⁿ、c_n = 1ⁿ，求三個數列的卷積公式。用生成函數相乘：A(x) = 1/(1+x)、C(x) = 1/(1−x)，乘起來後展開
• 第 6 題（20%）｜旗幟訊號的計數：60 面旗（紅白藍黑各 15 面），選 15 面掛在旗桿上排成訊號
• (a) 10%：黑旗奇數面且紅旗偶數面的訊號數 → 用指數生成函數（EGF）與 roots of unity filter
• (b) 10%：至少 5 面白旗 或 完全沒有藍旗的訊號數 → 排容原理
• 第 7 題（20%）｜停車位的遞迴（經典 Grimaldi 題）
• (a) 10%：n 個車位排成一排，機車佔 1 格、汽車佔 3 格，求停法數的遞迴式並解出 → a_n = a_n−1 + a_n−3
• (b) 10%：汽車有 4 種顏色（視為不同）時的遞迴 → a_n = a_n−1 + 4a_n−3
• 第 8 題（10%）｜同餘保持 gcd：證明 a ≡ b (mod n) ⇒ gcd(a,n) = gcd(b,n)。這題與 109 年第 9 題一字不差

這份考卷的難點

1. 第 6(a) 的「黑旗奇數、紅旗偶數」要用指數生成函數處理有限供應量（各色只有 15 面，但恰好等於要選的總數，所以上限不構成限制），再用 roots of unity filter 取出奇偶項。這是中山最進階的計數技巧。
2. 第 3 題認不出 Erdős–Szekeres 就完全不會：題目用「物流集貨點的空間必須遞減」包裝，實際上問的是「25 個相異數中保證存在多長的單調子序列」。
3. 第 7(b) 的 4a_n−3：汽車有四種顏色時，每次「放一台車」都有 4 種選擇，所以係數是 4 而不是 1。很多人會誤寫成 a_n−1 + a_n−3 + 4。
4. 第 1 題的多項式定理要小心每一項的係數也要取冪次（3ⁱ × (−1)^j × 5^k × 3^l × (−8)^m），只算 25!/(…) 是不完整的。

準備建議

• 第 8 題與 109 年第 9 題完全相同，第 4 題與 110 年第 4 題同型——中山的重複率是八所之冠
• Erdős–Szekeres 定理（112 第 3 題）與 114 年第 4 題「找出長度 10 且無長度 3 單調子序列的數列」是同一個定理的正反兩面，一起準備
• 停車／鋪磚型遞迴（112 第 7 題）是 Grimaldi Chapter 10 的招牌題，變體包括「帶顏色」「帶限制」，要能快速寫出遞迴式
• roots of unity filter 處理奇偶計數（111 第 5 題、112 第 6(a) 題、114 第 8 題）三年連續出現，是中山的核心技巧
• 排容原理（109 第 5 題、112 第 6(b) 題、113 第 8 題）同樣年年有