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

題型與配分

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

「沒有詳細步驟就不給分」（卷首明訂），不可以使用計算機——第 5 題要對六位數做質因數分解，全部手算。

逐題考點

• 第 1 題（10%）｜相同球放入相異桶：9 顆相同白球放入 3 個相異桶，第三個桶必須放偶數顆。用生成函數 (1/(1−x))² × (1/(1−x²)) 取 x⁹ 的係數。與 109 年第 1(b) 題同型
• 第 2 題（10%）｜三位數迴文的總和：200 到 999 之間的迴文（如 222、363、505、989），不列舉而直接求總和。迴文形如 aba = 101a + 10b，對 a = 2..9、b = 0..9 求和
• 第 3 題（10%）｜證明質數有無限多個：Euclid 的經典反證法——假設只有有限個質數 p₁…p_n，考慮 N = p₁p₂…p_n + 1
• 第 4 題（10%）｜歐幾里得演算法求模反元素：說明如何用擴展歐幾里得求 a⁻¹ (mod b)。題目直接給提示「若 c = gcd(a,b)，則存在 ax + by = c」——要寫出貝祖等式的回代流程
• 第 5 題（10%）｜三因數無序分解：389,298 有多少種「三個因數且每個都大於 1」的無序分解？先質因數分解 389298 = 2 × 3 × 11 × 17 × 347，再用第二類 Stirling 數／分堆處理，最後除以排列重複
• 第 6 題（10%）｜封閉二元運算的性質（f : Z×Z → Z）
• (a) 5%：f(x,y) = x + y − 119xy 是否可交換／可結合
• (b) 5%：f(x,y) = x + y + xy（或類似形式）——可交換但要驗算結合律
• 第 7 題（10%）｜對稱關係的計數：A = {3,5,9,11,13,17}（6 個元素）
• (a) 5%：恰含三個有序對的對稱關係有幾個
• (b) 5%：恰含六個有序對的有幾個
• 關鍵：對稱關係由「對角線元素（6 個，各貢獻 1 對）」與「非對角線的無序對（C(6,2) = 15 個，各貢獻 2 對）」組成，要依奇偶拆 case
• 第 8 題（10%）｜有上下界的分配：2800 本相同的書以 50 本為一包分給 5 組，每組至少 200、最多 600。換算成 56 包、每組至少 4 包最多 12 包，再用排容。與 109 年第 5 題同型
• 第 9 題（10%）｜解遞迴式：a_n+2 + a_n = 0、a₀ = 1、a₁ = 5。特徵方程 x² + 1 = 0 有複數根 ±i，解要寫成三角形式或分奇偶討論
• 第 10 題（10%）｜用生成函數解遞迴：a_n+2 − 8a_n+1 + 15a_n = 0、a₀ = 1、a₁ = 6。特徵根 3 與 5，但題目明確要求用生成函數——必須列出 G(x) 的方程、部分分式拆解、再展開

這份考卷的難點

1. 第 5 題的 389,298 要手算質因數分解（= 2 × 3 × 11 × 17 × 347），而且 347 是質數需要驗證。分解完之後還要處理「無序三因數分解」的重複計算，是全卷最花時間的一題。
2. 第 7 題的對稱關係計數要看穿結構：對稱關係的「基本單位」是對角線上的單點（貢獻 1 個有序對）與非對角線的無序對（貢獻 2 個有序對）。要湊出恰好 3 個或 6 個有序對，得分別列出所有組合方式。
3. 第 9 題出現複數特徵根，在中山八年裡是唯一一次。答案是週期為 4 的振盪數列，要能正確處理 iⁿ 的展開。
4. 第 10 題指定用生成函數——即使你能直接用特徵方程秒殺，不照指定方法做會不給分。

準備建議

• 113 有三題是舊題重出：第 1 題（109 第 1(b)）、第 4 題（110 第 7 題）、第 8 題（109 第 5 題），把 109、110 兩份練熟等於先拿 30 分
• 遞迴式一定要會兩種解法：特徵方程與生成函數。中山 113 年連考兩題，第 10 題明文指定生成函數
• 質數無限多的證明（113 第 3 題）與數學歸納法的良序證明（114 第 2 題）顯示中山近年開始考「課本定理的證明」，Grimaldi 的定理證明要讀過
• 有上下界的分配用排容原理是中山最愛（109、113 兩度出現），標準流程：換單位 → 平移下界 → 排容扣除超上界
• 「不可以使用計算機」意味著大數的質因數分解、冪次計算都要手算，練習時不要開計算機