中山資工所考古題解答數學十年大統整（106–115）

各章配分

表中數字是各題的卷面配分，依主題加總。有子題的照子題分，沒有子題的整題算在主要考點。章與細項依十年合計排序，顏色越深，占當年總分的比例越高。巢狀迴圈執行次數的題目算在 Other，生成函數求奇偶個數的機率題算在 Probability。

章／細項	106	107	108	109	110	111	112	113	114	115	合計	占比	年數
Counting	30		40	32	40	30	30	30	20	52	304	30%	9
Permutations & Combinations			28		10	20	10	10		28	106	11%	6
Pigeonhole Principle	20		12	10	20	10	10		10	10	102	10%	8
Integer Solutions & Distributions				22	10			20	10	7	69	7%	5
Binomial Identities	10						10				20	2%	2
Inclusion-Exclusion & Derangements										7	7	<1%	1
Recurrences & Generating Functions	10	60	14	22	10	30	50	20	30		246	25%	9
Linear Recurrence Relations		20		10	10	30	20	10	30		130	13%	7
Generating Functions	10	40	14	12			30	10			116	12%	6
Number Theory	20		10	22	20		20	30		14	136	14%	7
Divisibility & GCD	20			10	10		10	20		7	77	8%	6
Modular Arithmetic			10	12	10		10	10		7	59	6%	6
Sets, Relations & Functions				12		10		20	10	7	59	6%	5
Functions				12				10	10	7	39	4%	4
Relations						10		10			20	2%	2
Probability					10	20			10	17	57	6%	4
Logic & Proofs	10		24						10	10	54	5%	4
Propositional & Predicate Logic			24							10	34	3%	2
Proof Techniques & Induction	10								10		20	2%	2
Graph Theory	30			12							42	4%	2
Bipartite Graphs & Matching	30			12							42	4%	2
Algebraic Structures		40									40	4%	1
Groups		40									40	4%	1
Automata & Languages			12			10			10		32	3%	3
Finite State Machines						10			10		20	2%	2
Regular Expressions & Grammars			12								12	1%	1
Other					20				10		30	3%	2

八校各章配分比較 →

Counting 合計 304 分、Recurrences & Generating Functions 246 分，兩章加起來佔十年總分的一半以上。Graph Theory 只有 106 年第 4 題（k-cube 與 bipartite graph）與 109 年第 8 題（complete bipartite graph），115 年 B3 的六人問題以人群敘述，沒有用圖的名稱。Algebraic Structures 只有 107 年第 4 到 6 題的 group，共 40 分。線性代數 106 到 115 年都沒有出現。

重複出題清單

同一類題目在不同年度反覆出現。109 第 9 題與 112 第 8 題的敘述相同，108 第 5 題與 111 第 1 題只差數字。

題目	出現年度
a ≡ b (mod n) ⇒ gcd(a,n) = gcd(b,n) 的證明	109 第 9 題、112 第 8 題（敘述相同，配分 12 與 10）
子集和不可能全相異（pigeonhole）	108 第 5 題（五個數、最大 9）、111 第 1 題（七個數、最大 21）
字串的 proper prefix 計數	110 第 4 題（5 字母、前綴 xy）、112 第 4 題（6 字母、前綴 xyz）、115 A9（改問 substring）
有上下限的分配	109 第 5 題（信封）、113 第 8 題（書）
相同球放入相異容器加偶數限制	109 第 1(b) 題、113 第 1 題、114 第 7 題
停車、排程型 recurrence（含帶顏色版本）	112 第 7 題（機車與汽車）、114 第 6 題（P1 與 P2）
奇偶個數的計數與機率	111 第 5 題（三進位 26 位）、112 第 6(a) 題（旗幟）、114 第 8 題（八進位 28 位）
巢狀迴圈的執行次數	110 第 1 題（兩層）、114 第 1 題（三層）
finite state machine 的 state diagram	111 第 2 題、114 第 5 題
擲骰子求和的機率	110 第 5 題（11 次和 35）、115 B1（5 次和 15）
用 generating function 解二階齊次 recurrence	106 第 2 題（題目要求先求 generating function）、113 第 10 題（指定用 generating function）
modular inverse	107 第 5(b) 題（Z∗₁₉₆ 中 25 的 inverse）、110 第 7 題（用 Euclidean algorithm 求 Z₈₂ 中 [23] 的 inverse）、113 第 4 題（說明如何用 Euclidean algorithm 求）
decreasing 與 monotonic subsequence	112 第 3 題（倉庫排列）、114 第 4 題（構造數列）
nonhomogeneous recurrence	110 第 6 題、114 第 9 題
palindrome 的計數	111 第 4 題（整數 n 的 palindrome）、113 第 2 題（三位數的 palindrome）
經典定理的證明	106 第 4(b)(c) 題（bipartite graph 與奇數長度 cycle）、110 第 2 題（合數有質因數）、113 第 3 題（質數無限多）、114 第 2 題（well-ordering principle 與 induction）、115 B3（六人互識或互不識）

優先準備的四個主題

1. 分配計數與 generating function

106 到 115 年每年都有分配計數或 generating function 的題目：

球放容器加偶數限制（109 第 1(b) 題、113 第 1 題、114 第 7 題）
有上下限的分配（109 第 5 題、113 第 8 題）
整數解（110 第 8 題、115 A2）
彈珠放入相異罐子（111 第 8 題）
求 generating function 或冪級數的係數（107 第 1 題、108 第 7 題、109 第 6 題）
exponential generating function 與 onto 函數（107 第 2 題）
convolution（112 第 5 題）
用 generating function 解 recurrence（106 第 2 題、113 第 10 題指定）

2. 奇偶個數的計數與機率（111、112、114）

111 年考三進位（n = 26），112 年是旗幟訊號，114 年考八進位（n = 28）。

3. Recurrence 的建模與求解（106、107、109 到 114 年）

一階與二階齊次 recurrence（106 第 2 題、109 第 7 題、113 第 9 題）
字串集合 A∗ 的 recurrence（107 第 3 題）
停車、排程型（112、114），物件有顏色時有帶顏色的版本
nonhomogeneous recurrence（110 第 6 題、114 第 9 題）
二進位字串的 recurrence（111 第 6 題）與疫情包裝的 recurrence（111 第 7 題）
106 年第 2 題與 113 年第 10 題要用 generating function，113 年第 9 題沒有指定方法

4. Pigeonhole 與存在性論證

連續子序列的和被 k 整除、正方形內的 5 個點（106 第 1、5 題）
子集和不可能全相異（108、111）
姓名首字母的 pigeonhole（109）
整除關係的 pigeonhole（110）
decreasing subsequence（112 求最少長度、114 求構造數列）
六人互識或互不識（115 B3）

題型演變

年度	題數	形式	內容
106	7	全申論，第 4 題 30 分、第 7 題 20 分，其餘各 10 分	連續子序列和的 pigeonhole、k-cube 與 bipartite graph、質數整除 binomial coefficient，七題中六題是證明
107	6	全申論，第 4、5 題各 10 分，其餘各 20 分	onto 函數的 exponential generating function、A∗ 的字串計數、Z₈、Z∗₁₉₆ 與 Z×Z 上的 group
108	8	全申論	formal language A² = A 的證明、棋盤方格個數
109	9	全申論	integer partition 的 generating function、closed binary operation 的個數、complete bipartite graph
110	8	全申論，第 1、3 題各 20 分，其餘各 10 分	巢狀迴圈的次數、整除關係的 pigeonhole、modular inverse
111	8	全申論，第 5、6 題各 20 分，其餘各 10 分	子集和相異性、COVID 疫情包裝的 recurrence，答案要寫成日期
112	8	全申論，第 6、7 題各 20 分，其餘各 10 分	倉庫遞減排列、旗幟訊號、停車 recurrence
113	10	全申論	質數無限多的證明、三因數分解、兩題 recurrence
114	9	全申論，第 6 題 20 分	用 well-ordering principle 證明 induction、構造沒有 monotonic subsequence 的數列
115	13	A 區 10 題只寫答案（70 分），B 區 3 題寫推導（30 分）	賭徒輸光的期望局數、斜走格路徑、六人互識或互不識

106 到 114 年卷首都印著每題要寫詳細步驟，否則該題不給分。115 年改成 A、B 兩區，A 區只寫答案。

給 116 年考生的準備方向

115 年 A 區 10 題只寫答案、B 區 3 題才寫推導。練習時照這個形式計時作答，不開計算機。
Graph theory 只有 106、109 年各一題，group 只有 107 年，線性代數十年沒有出現。
106 年七題中六題是證明，證明題除了 107 年每年都有，要練到能把步驟寫完整。
106 到 115 年十份可以全部手寫一次，109 與 112 的 gcd 證明敘述相同。
106、107 年是 7 題與 6 題，108 到 115 年各是 8 到 13 題；108 年起卷面印考試時間 100 分鐘。
數學考哪一組要先確認：甲組考離散數學，乙組考工程數學，資安碩班考離散數學與演算法，三份卷子不同。

本頁的題型、配分、作答規定都取自各年度試卷上的標示，各章配分與重複題是逐題整理的。如果發現有誤，歡迎來信指正。

中山資工所考古題詳解數學十年大統整（106–115）