中山資工所數學考古題八年大統整（108–115）
命題來源：Grimaldi 課本
中山離散的題目幾乎全部出自 Grimaldi《Discrete and Combinatorial Mathematics》，很多題目連文字都沒改：
| 中山題目 | Grimaldi 對應章節 |
|---|---|
| 委員會選取、球放容器、重複組合 | Ch.1 Fundamental Principles of Counting |
| 量詞敘述與否定、真值表 | Ch.2 Fundamentals of Logic |
| 數學歸納法、良序原理 | Ch.4 Properties of the Integers |
| 函數計數、滿射與排容 | Ch.5 Relations and Functions |
| 鴿籠原理 | Ch.5.5 The Pigeonhole Principle |
| 封閉二元運算、對稱關係計數 | Ch.5 / Ch.7 Relations |
| 排容原理與有界分配 | Ch.8 The Principle of Inclusion and Exclusion |
| 生成函數、分割、卷積 | Ch.9 Generating Functions |
| 遞迴關係（停車、鋪磚、字串） | Ch.10 Recurrence Relations |
| 完全二分圖、有限狀態機 | Ch.6 / Ch.11 |
準備中山，讀 Grimaldi 比讀 Rosen 有效率得多。 重點是 Ch.1、Ch.8、Ch.9、Ch.10 四章。
題型演變
| 年度 | 題數 | 形式 | 特色 |
|---|---|---|---|
| 108 | 8 | 全申論 | 形式語言 A2 = A 的證明、棋盤方格計數 |
| 109 | 9 | 全申論 | 分割的生成函數對偶、封閉二元運算 749 |
| 110 | 8 | 全申論，每題 10 分 | 巢狀迴圈計數、{1..2n} 取 n+1 必有整除 |
| 111 | 8 | 全申論，每題 10 分 | COVID 疫情包裝的遞迴要算到具體日期 |
| 112 | 8 | 全申論，每題 10 分 | Erdős–Szekeres 包裝成倉庫排序、停車遞迴 |
| 113 | 10 | 全申論 | 題數最多；質數無限多的證明、複數特徵根 |
| 114 | 9 | 全申論 | 用良序原理證明數學歸納法、構造反例 |
| 115 | 13 | A 區 10 題只寫答案（70 分）＋ B 區 3 題寫推導（30 分） | 八年來最大改版；新增賭徒破產、Delannoy 路徑 |
重複出題清單
中山是八所裡重複率最高的學校之一——有些題目連文字都一字不改。
| 題目 | 出現年度 |
|---|---|
| 「同餘 ⇒ gcd 相等」的證明 | 109 第 9 題、112 第 8 題（一字不差） |
| 子集和不可能全相異（鴿籠） | 108 第 5 題（五個數、最大 9）、111 第 1 題（七個數、最大 21） |
| 字串的真前綴計數 | 110 第 4 題（5 字母、前綴 xy）、112 第 4 題（6 字母、前綴 xyz）、115 A9（改問 substring） |
| 有上下界的分配（排容） | 109 第 5 題（信封）、113 第 8 題（書本），解法完全相同 |
| 相同球放入相異容器＋偶數限制 | 109 第 1(b) 題、113 第 1 題、114 第 7 題 |
| 停車／排程型遞迴（含帶顏色版本） | 112 第 7 題（機車＋汽車）、114 第 6 題（P1＋P2） |
| roots of unity filter 求奇偶個數的機率 | 111 第 5 題（三進位 26 位）、112 第 6(a) 題（旗幟）、114 第 8 題（八進位 28 位） |
| 巢狀迴圈的執行次數 | 110 第 1 題（兩層）、114 第 1 題（三層） |
| 有限狀態機的狀態圖 | 111 第 2 題、114 第 5 題 |
| 擲骰子求和的機率 | 110 第 5 題（11 次和 35）、115 B1（5 次和 15） |
| 歐幾里得演算法求模反元素 | 110 第 7 題、113 第 4 題 |
| Erdős–Szekeres 定理 | 112 第 3 題（求存在）、114 第 4 題（求構造） |
| 二進位字串的無連續 0／1 遞迴 | 111 第 6 題 |
| 課本定理的證明 | 113 第 3 題（質數無限多）、114 第 2 題（良序 ⇒ 歸納）、115 B3（Ramsey R(3,3)=6） |
結論很直接：把 108–115 八份全部手寫一次，116 年至少四成的題目你已經寫過。
主題出現年度一覽
| 主題 | 出現年度 |
|---|---|
| 生成函數 | 108、109、110、111、112、113、114、115 |
| 遞迴關係 | 110、111、112、113、114 |
| 鴿籠原理 | 108、109、110、111、112、114、115 |
| 排容原理 | 109、112、113、115 |
| 數論（同餘、gcd、質數、模反元素） | 108、109、110、112、113、115 |
| 組合計數（排列、重複組合、多項式定理） | 108、109、110、111、112、113、114、115 |
| 函數與關係的計數 | 109、113、114、115 |
| 機率 | 110、111、112、114、115 |
| 邏輯與量詞 | 108、115 |
| 證明技巧（歸納、反證、良序） | 108、109、112、113、114、115 |
| 有限狀態機與形式語言 | 108、110、111、112、114 |
| 圖論 | 109（完全二分圖）——八年僅此一次 |
注意最後一列：中山離散幾乎不考圖論。 八年只有 109 年第 8 題問了完全二分圖的頂點與邊數。這與中央、成大把圖論當主戰場的做法完全相反——準備中山時，時間應該全部投在計數、生成函數與遞迴上。
必守的四個技巧
1. 生成函數（八年全中）
中山每一年都有生成函數，而且用法固定：
- 球放容器＋偶數／奇數限制 →
1/(1−x²)取代1/(1−x)（109、113、114） - 整數分割 →
∏ 1/(1−x^k)（109） - 有上下界的分配 →
(1 + x + … + x^u)的乘積（109、113） - 求特定係數 → 1/(1−x)n 展開係數 C(n+r−1, r)（108、110）
- 卷積 → 兩個生成函數相乘（112）
2. roots of unity filter（111、112、114 三年連續）
求「某符號出現偶數次」的計數，標準公式是把生成函數在 x = 1 與 x = −1 取值後平均：
k 個符號的 n 位序列中，指定兩種各出現偶數次的個數 = [kn + 2(k−2)n + (k−4)n] / 4
111 年考三進位（k=3, n=26）、114 年考八進位（k=8, n=28），公式完全一樣。
3. 遞迴式的建模與求解（110、111、112、113、114）
- 停車／排程型：一格一秒的物件 + 佔 k 格的物件 → an = an−1 + an−k；若後者有 c 種變化 → an = an−1 + c·an−k（112、114）
- 非齊次的特解：右式底數與特徵根重疊要乘 n（110 第 6 題的 −360 與根 1 重疊）、不重疊直接設常數倍（114 第 9 題的 9n）
- 113 年明文指定用生成函數解——兩種解法都要會
4. 鴿籠與存在性論證（幾乎每年）
中山特別愛考「證明某種東西必然存在」：
- 子集和不可能全相異（108、111）：比較子集個數與和的範圍
- {1,…,2n} 取 n+1 個必有整除關係（110）：把每個數寫成 2k × 奇數
- Erdős–Szekeres（112 求存在、114 求構造）：n2+1 個相異數中必有長度 n+1 的單調子序列
- Ramsey R(3,3) = 6（115 B3）：六人中必有三人全熟或全陌生
給 116 年考生的策略
- 115 年的改版是最重要的訊號。 若 116 年延續「A 區 10 題只寫答案、B 區 3 題寫推導」的格式，計算的正確率會比推導能力更關鍵——A 區沒有部分分數，錯一步就是 −7 分。練習時要計時、不開計算機、直接寫答案。
- 讀 Grimaldi，不要只讀 Rosen。 中山八年的題目幾乎全部是 Grimaldi 的習題原型，重點是 Ch.1、Ch.8、Ch.9、Ch.10。
- 不要花時間準備圖論與線性代數。 中山甲組離散八年只考過一題圖論（109 完全二分圖），完全沒考過線代。時間應該全部投在計數、生成函數、遞迴、數論上。
- 把 108–115 八份全部手寫一次。 重複出題清單顯示至少四成題目會重出，109 與 112 的 gcd 證明甚至一字不差。
- 100 分鐘寫 8–13 題，平均一題 8–12 分鐘。時間是真正的敵人，練習時一定要計時。
- 確認自己考的是哪一組：甲組考「離散數學」（434004）、乙組考「工程數學」、資安碩班考「離散數學與演算法」——三份完全不同的卷子。
本頁的題型、配分、作答規定均直接取自各年度試卷標示；主題出現年度與重複題比對為逐題整理。若發現有誤，歡迎來信指正。