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

題型與配分

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

「沒有詳細步驟就不給分」（卷首明訂），不可以使用計算機。

逐題考點

• 第 1 題（10%）｜三層巢狀迴圈的累加值：

increment = 0; sum = 0
for i = 1 to 12: for j = 1 to i: for k = 1 to j:
    increment = increment + 1;  sum = sum + increment

迴圈總執行次數是 C(12+2, 3) = C(14,3) = 364，而 increment 每次遞增 1，所以 sum = 1+2+…+364 = 364×365/2 = 66,430。與 110 年第 1 題同型但加到三層

• 第 2 題（10%）｜用良序原理證明數學歸納法：假設 P(1) 為真、且 P(k) → P(k+1)，要證 P(n) 對所有 n 成立。做法是反證——令 S = {n : P(n) 為假}，若 S 非空則由良序原理有最小元素 m，推出矛盾。這是純定理證明，不是計算
• 第 3 題（10%）｜指定值域的函數計數：A = {1,…,9}（9 個元素）、B = {a,…,h}（8 個元素）
• (a) 5%：f(A) = {a,b,c}（值域恰為這三個元素）→ 滿射到 3 個元素：3⁹ − 3·2⁹ + 3（排容）
• (b) 5%：|f(A)| = 3（值域大小為 3，但不指定是哪三個）→ C(8,3) × (3⁹ − 3·2⁹ + 3)
• 第 4 題（10%）｜構造反例：找出十個相異實數排成的數列，使其不存在長度 3 的遞增或遞減子序列。由 Erdős–Szekeres，n²+1 = 10 時必有長度 3 的單調子序列，所以最多只能到 9 個數——但題目問十個，關鍵在於 3²+1 = 10 剛好是臨界值。構造法：把 9 個數分成 3 組遞減區塊、組間遞增（如 3,2,1,6,5,4,9,8,7）
• 第 5 題（10%）｜有限狀態機：畫出接受語言 **{0,0}\{1,0} ∪ {0,1}\{00} 的狀態圖。與 111 年第 2 題同型**
• 第 6 題（20%）｜程式排程的遞迴（停車問題的變體）
• (a) 10%：P1 佔 1 秒、P2 佔 4 秒，n 秒內的排法數 → a_n = a_n−1 + a_n−4
• (b) 10%：P2 有 4 種不同任務（視為不同）→ a_n = a_n−1 + 4a_n−4
• 與 112 年第 7 題結構完全相同（只是把「停車」換成「排程」、3 格換成 4 秒）
• 第 7 題（10%）｜買肉的生成函數：從豬、雞、牛三種中買 n 盒，牛肉必須是偶數盒。生成函數 1/(1−x) × 1/(1−x) × 1/(1−x²)，取 xⁿ 的係數。與 109 第 1(b)、113 第 1 題同一招
• 第 8 題（10%）｜八進位序列的奇偶機率：隨機產生 28 位八進位（0–7）序列，求 3 的個數為偶數且 7 的個數為偶數的機率。用 roots of unity filter：(8ⁿ + 2·6ⁿ + 4ⁿ)/4 ÷ 8ⁿ。與 111 年第 5 題同型（該年是三進位 26 位）
• 第 9 題（10%）｜非齊次遞迴：a_n+2 − 7a_n+1 + 12a_n = 9ⁿ、a₀ = a₁ = 1。特徵根 3 與 4，右式 9ⁿ 的底數 9 不與特徵根重疊，所以特解直接設 A·9ⁿ

這份考卷的難點

1. 第 2 題是純數學基礎題：用良序原理證明數學歸納法。這在 Grimaldi 第 4 章是定理而非習題，沒讀過證明就寫不出來，而且要清楚區分「良序原理」與「歸納原理」是等價但不同的敘述。
2. 第 4 題要「造出反例」而非「證明存在」：多數人練的是 Erdős–Szekeres 的存在性證明，突然要反過來構造臨界例子會卡住。標準構造是分成 ⌈√n⌉ 個遞減區塊、區塊之間遞增。
3. 第 1 題的三層迴圈要看出執行次數是「從 12 個中取 3 個可重複的組合」= C(14,3)，而不是硬加三層 Σ。sum 的累加還要再做一次等差級數求和。
4. 第 3(a) 與 (b) 的差別是「值域指定為哪三個」與「值域大小為 3」，後者要多乘一個 C(8,3) = 56。漏掉這個係數是最常見的失分點。

準備建議

• 114 有四題是舊題的同型變體：第 1 題（110 第 1 題）、第 5 題（111 第 2 題）、第 6 題（112 第 7 題）、第 8 題（111 第 5 題）——把 110、111、112 三份練熟，114 等於先拿 40 分
• roots of unity filter 三年連續出現（111、112、114），必背公式：k 個符號中「某兩種各為偶數個」的計數為 [kⁿ + 2(k−2)ⁿ + (k−4)ⁿ]/4
• Erdős–Szekeres 的正反兩面（112 第 3 題求存在、114 第 4 題求構造）要一起練
• 非齊次遞迴的特解設定：右式底數與特徵根重疊要乘 n（110 第 6 題）、不重疊直接設常數倍（114 第 9 題）——兩種都要會
• 課本定理的證明（113 第 3 題質數無限、114 第 2 題歸納原理）是中山近兩年的新趨勢，Grimaldi 的定理證明不能跳過