110 中山資工所考古題詳解｜數學考點分析

題型與配分

全卷 1 頁、8 題、100 分，不可使用計算機。卷首規定每題都要寫出詳細步驟，否則該題不給分。每個小題 10 分。

逐題考點

• 第 1 題（20%）｜pseudo-code for i := 1 to 567 do / for j := 1 to i do / print i*j：(a) 10% 第三行的 print 執行幾次 (b) 10% 把第二行的上界 i 換成 i² 後，回答 (a) 的問題
• 第 2 題（10%）｜n ∈ Z⁺ 且 n 為合數，證明存在質數 p 使 p | n
• 第 3 題（20%）｜(a) 10% 從 {1, 2, 3, …, 336} 中選 169 個整數，證明所選的整數中必有 x、y 使 x | y 或 y | x (b) 10% 寫出把 (a) 的結果一般化的敘述
• 第 4 題（10%）｜Σ = {v, w, x, y, z}，A = ⋃_n=1⁸ Σⁿ，A 中有多少字串以 xy 為真前綴（proper prefix）
• 第 5 題（10%）｜公正骰子擲 11 次，點數和為 35 的機率
• 第 6 題（10%）｜解 recurrence relation a_n+2 − 4a_n+1 + 3a_n = −360，n ≥ 0，a₀ = 3000，另一個初始條件卷面印成 a₀ = 3300
• 第 7 題（10%）｜用 Euclidean algorithm 求 Z₈₂ 中 [23] 的 inverse [23]⁻¹
• 第 8 題（10%）｜方程式 c₁ + c₂ + c₃ + c₄ + c₅ = 37，每個 c_i ≥ 0，整數解有幾組

作答時要注意的地方

1. 第 1、3 題各 20 分，合計 40 分，其餘 6 題各 10 分。
2. 第 1 題 (b) 的修改是第二行的迴圈上界。
3. 第 4 題的字串長度限定在 1 到 8，且前綴要是真前綴。
4. 第 5 題與第 8 題的數字很大，不能用計算機。
5. 第 6 題的第二個初始條件在卷面也印成 a₀。

準備方向

• 巢狀迴圈的執行次數（110 第 1 題），114 第 1 題加到三層迴圈。
• 整除關係的 pigeonhole（110 第 3 題），108 第 5 題、109 第 4 題、111 第 1 題也有 pigeonhole。
• 字串前綴計數（110 第 4 題），112 第 4 題同一個 Σ 與 A 的寫法，115 A9 改問子字串。
• 擲骰和的機率（110 第 5 題），115 B1 也有。
• 非齊次遞迴（110 第 6 題），114 第 9 題也有。
• modular inverse 與 Euclidean algorithm（110 第 7 題），107 第 5(b) 題、113 第 4 題也有 modular inverse，115 A4 求 gcd。
• 整數解與分配計數（110 第 8 題），109 第 5 題、113 第 8 題、115 A2 也有。
• 質因數的證明（110 第 2 題），113 第 3 題的質數無限多也是數論證明。