115 中山資工所數學考點分析
題型大改版：A1–A10 只寫答案（每題 7 分共 70 分），B1–B3 才要寫推導（每題 10 分共 30 分）。是八年來第一次出現「不必寫過程」的題目。
題型與配分
科目名稱「離散數學」【資工系碩士班甲組】，題號 434004，考試時間 100 分鐘，「不可以」使用計算機（問答申論題），全卷試題僅 1 頁、13 題、100 分。
| 區段 | 題號 | 配分 | 作答要求 |
|---|---|---|---|
| Simple-Answer Questions | A1–A10 | 70%（每題 7 分） | 只寫答案，一行一題（A1) Answer） |
| Computation Questions | B1–B3 | 30%（每題 10 分） | 要寫答案＋推導過程（B1) Answer. Inference/deduction process） |
這是中山離散八年來最大的一次改版。 108–114 年每一年都印著「you should write down detailed steps… otherwise, no credits」，115 年把它拆成兩段：前 70 分只要答案、後 30 分才要過程。
A 區只寫答案代表沒有部分分數——算錯一步整題 7 分全沒。不可以使用計算機。
Simple-Answer Questions（A1–A10，各 7%，只寫答案）
- A1｜ENGINEERING 的無相鄰 E 排列數：11 個字母（E×3、N×3、I×2、G×2、R×1），先排非 E 的 8 個字母（8!/(3!2!2!)），再從 9 個空隙選 3 個放 E → × C(9,3)
- A2｜有界整數解：x+y+z = 10、x, y, z ∈ {1,2,3,4,5} 的三元組個數。用排容原理（先平移下界成 0，再扣掉超過 4 的情形）
- A3｜排容原理：100 到 999 之間能被 3 或 5 或 7 整除的三位數有幾個 → |A∪B∪C| 的七項排容
- A4｜歐幾里得演算法：求 gcd(1,066,601, 343,033)。禁用計算器，要手算輾轉相除
- A5｜格路徑計數：5×5 棋盤上，石頭每步可向右、向上、或右上斜走，求 (1,1) 到 (5,5) 的路徑數。這是 Delannoy 數（中央 Delannoy 路徑），要用遞迴表 D(i,j) = D(i−1,j) + D(i,j−1) + D(i−1,j−1) 逐格填
- A6｜無相鄰整數的子集：S = {1,…,9}，求不含連續整數的 3 元素子集個數 → C(9−3+1, 3) = C(7,3) = 35
- A7｜乘法階數：求最小正整數 x 使 2x ≡ 1 (mod 13)。2 的冪次 mod 13 為 2,4,8,3,6,12,11,9,5,10,7,1 → x = 12（2 是模 13 的原根）
- A8｜帶原像限制的函數計數：A = {1,…,9}，求滿足 f−1({1,3}) = ∅、f−1({4,6}) = {1,3,7}、f−1({7,9}) = {8,9} 的函數 f : A → A 個數。分別計算三組限制下各元素的可選值再相乘
- A9｜含指定子字串的字串計數：Σ = {a, b, x, y}，L = ⋃ Σn，求 L 中含有子字串 bay（注意是 substring 不是 prefix）的字串個數。與 110 第 4 題、112 第 4 題的「真前綴」是對照組——substring 的計數要用排容避免重複
- A10｜賭徒破產問題：Adam 與 Eve 各有 5 元，每局勝者從敗者拿 1 元，求直到其中一人輸光的期望局數。公平賭局下期望局數 = a × b = 5 × 5 = 25
Computation Questions（B1–B3，各 10%，要寫推導）
- B1（10%）｜擲骰機率：公正骰子擲 5 次，求和為 15 的機率。用生成函數 (x+…+x6)5 取 x15 的係數，或排容原理。與 110 年第 5 題同型（該年是擲 11 次和為 35）
- B2（10%）｜建真值表：對
p → [(q ∧ r) → (p ∨ r)]建立完整真值表（8 列）。題目明寫「Explanation is not required」——這 10 分只要表格正確就拿滿 - B3（10%）｜證明題：Ramsey 數 R(3,3) = 6。六個人中，任兩人要嘛互相認識、要嘛互為陌生人，證明必存在三人全部互相認識或三人全部互為陌生人。標準做法：任取一人，他與其餘五人的關係中必有至少三個同類（鴿籠），再對這三人討論
這份考卷的難點
- A 區 70 分沒有部分分數。108–114 年的申論格式至少能靠推導拿部分分，115 年改成只填答案後，一個算術錯誤就是 −7 分，而且禁用計算器（A4 的 gcd(1066601, 343033) 全部手算）。
- A5 的 Delannoy 數不是常見的格路徑題——多了「右上斜走」這個動作，不能直接用 C(m+n, n)。要現場建 5×5 的遞迴表格，時間壓力很大。
- A8 的三組原像限制要同時滿足：f−1({1,3}) = ∅ 代表沒有元素映到 1 或 3、f−1({4,6}) = {1,3,7} 代表恰好這三個元素映到 4 或 6、f−1({7,9}) = {8,9}。剩下的 4 個元素只能映到 {2,5,8} 三個值。三段分別計數再相乘。
- B3 的 Ramsey 證明要寫完整：先用鴿籠找出「與某人關係相同的三個人」，再分「這三人中有一對同類」與「這三人兩兩都不同類」兩種情形討論。
準備建議
- 115 年的改版是最重要的訊號：若 116 年延續「A 區只寫答案」的形式，計算的正確率比推導能力更重要，練習時要計時、不開計算機、直接寫答案
- B 區只有 3 題 30 分要寫過程，而 B2 甚至明寫「不需要說明」——真正要寫證明的只剩 B3 一題
- Ramsey R(3,3) = 6（115 B3）、Erdős–Szekeres（112、114）、鴿籠原理（108、109、110、111）顯示中山極度偏愛存在性論證，這一類定理要背熟標準證法
- 賭徒破產（A10）、Delannoy 路徑（A5）、乘法階數（A7） 是 115 年新增的考點，代表出題範圍正在擴大到機率與數論
- 中山離散的命題主軸仍是 Grimaldi《Discrete and Combinatorial Mathematics》：計數、排容、生成函數、遞迴四大塊八年不變