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

題型與配分

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

「沒有詳細步驟就不給分」（卷首明訂），不可以使用計算機——第 5、8 題的組合數要全部手算。

逐題考點

• 第 1 題（20%）｜巢狀迴圈計數
• (a) 10%：for i := 1 to 567 do / for j := 1 to i do / print 執行幾次 → Σ_i=1⁵⁶⁷ i = 567×568/2 = 161,028
• (b) 10%：把內層上界改掉後重算——考的是能不能正確列出求和式再套公式
• 第 2 題（10%）｜合數必有質因數：證明「若 n 為合數，則存在質數 p 使 p | n」。用良序原理（取 n 的最小非 1 因數，證明它必為質數）
• 第 3 題（20%）｜整除關係的鴿籠
• (a) 10%：從 {1, 2, …, 336} 中選 169 個整數，證明必有兩個 x、y 滿足 x | y 或 y | x。做法是把每個數寫成 2^k·m（m 為奇數），奇數部分只有 168 種 → 鴿籠
• (b) 10%：寫出這個結果的一般化敘述（從 {1,…,2n} 中取 n+1 個必有整除關係）
• 第 4 題（10%）｜真前綴的字串計數：Σ = {v, w, x, y, z}（5 個字母），A = ⋃ Σⁿ，問 A 中有多少字串以 xy 為真前綴（proper prefix）。要注意「真前綴」代表字串長度必須大於 2，以及題目給定的長度上限
• 第 5 題（10%）｜擲骰的機率：公正骰子擲 11 次，和為 35 的機率。分子要用生成函數 (x+x²+…+x⁶)¹¹ 中 x³⁵ 的係數（或排容原理），分母是 6¹¹。禁用計算器所以只需寫出表達式與展開過程
• 第 6 題（10%）｜非齊次遞迴（常數項）：a_n+2 − 4a_n+1 + 3a_n = −360，a₀ = 3000、a₁ = 3300。特徵根為 1 與 3，因為常數項與根 1 重疊，特解要設成 An（而非常數）
• 第 7 題（10%）｜求模反元素：用歐幾里得演算法求 [23]⁻¹ in Z₈₂（即 23x ≡ 1 mod 82）。要寫出完整的輾轉相除與回代
• 第 8 題（10%）｜線性方程的整數解：c₁+c₂+c₃+c₄+c₅ = 37，各 c_i 有下界限制，求解的個數 → 重複組合 C(n+k−1, k−1) 加上變數平移

這份考卷的難點

1. 第 6 題的特解與特徵根重疊：常數項 −360 對應的「根」是 1，而特徵根恰好有 1，所以特解必須乘上 n。這是非齊次遞迴最常見的陷阱，成大、中央也都愛考。
2. 第 3(a) 的「奇數部分」技巧：每個正整數唯一寫成 2^k·(奇數)，{1,…,336} 中的奇數有 168 個，選 169 個必有兩個奇數部分相同 ⇒ 其中一個整除另一個。想不到這個分解就完全無從下手。
3. 第 5 題禁用計算器，6¹¹ = 362,797,056 要手算，而分子的係數還要用排容原理展開。寫出完整表達式並說明推導，比算出小數更重要。
4. 第 4 題的「proper prefix」容易誤解——真前綴不包含字串本身，所以長度為 2 的字串 "xy" 不算。

準備建議

• 巢狀迴圈計數（110 第 1 題、114 第 1 題）連兩次出現，而且 114 加到三層迴圈，要熟 Σi、Σi²、Σ C(i,2) 的封閉式
• {1,…,2n} 取 n+1 個必有整除關係（110 第 3 題）是 Grimaldi 的經典鴿籠題，務必記住「拆成 2^k×奇數」的技巧
• 模反元素與歐幾里得演算法（110 第 7 題、113 第 4 題）連兩次出現，要能寫出完整回代
• 非齊次遞迴的特解設定（110 第 6 題、114 第 9 題）是中山的固定考點，右式與特徵根重疊時要乘 n
• 「真前綴」的字串計數在 112 年第 4 題重出（同樣的 Σ 與 A 定義，只把 xy 換成 xyz）