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

題型與配分

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

逐題考點

• 第 1 題（10%）｜S 是七個正整數的集合，最大值不超過 21，證明 S 所有非空子集的元素和不會全部相異
• 第 2 題（10%）｜畫出 finite state machine 的 state diagram，I = O = {0,1}，辨識語言 {0,1}{11} ∪ {0,1}{01} 中的所有字串
• 第 3 題（10%）｜n ∈ Z⁺ 且 n > 1，A 為 n 的正因數集合，關係 R 定義為 xRy 若 x（整除）y，n = 6680 時 R 有幾個有序對
• 第 4 題（10%）｜n 為固定的正整數且 n ≥ 5，1 ≤ t ≤ ⌊n/2⌋，n 的迴文（palindromes of n）中有幾個以 t 開頭
• 第 5 題（20%）｜隨機產生 26 位的三進位（0、1、2）序列：(a) 10% 0 的個數為偶數且 2 的個數為偶數的機率 (b) 10% 0 的個數為奇數、1 的個數為奇數且 2 的個數為偶數的機率
• 第 6 題（20%）｜n ≥ 1：(a) 10% a_n 為長度 n、沒有連續兩個 0 的二進位字串個數，求並解 a_n 的 recurrence relation (b) 10% b_n 為長度 n、沒有連續兩個 1 且最後一位是 0 的二進位字串個數，求並解 b_n 的 recurrence relation
• 第 7 題（10%）｜某國出現第一例 COVID-19 後，在疫苗至少兩劑接種率達 70% 的情況下，第 n 週至少通報一例的機率為 p_n，p_n = p_n−1 − 0.3p_n−2（n ≥ 2），p₀ = 0、p₁ = 1。若第一例（新一波）記錄於 2019 年 12 月 27 日，新增病例發生的機率第一次小於 0.01 是在哪一天
• 第 8 題（10%）｜把 20 顆大小相同的彈珠放入 6 個相異罐子，每顆彈珠顏色都不同，有幾種放法

作答時要注意的地方

1. 第 5、6 題各 20 分，各分成兩個 10 分的小題。
2. 第 7 題的答案要寫成日期，卷面要求的是機率第一次小於 0.01 的那一天。
3. 第 8 題題目說彈珠大小相同、顏色各不相同。
4. 第 5 題的 (b) 與 (a) 的條件不同，(b) 有三個符號的奇偶限制。

準備方向

• 子集和的相異性（111 第 1 題），108 第 5 題同型，另有 pigeonhole 題 109 第 4 題、110 第 3 題、112 第 3 題。
• finite state machine（111 第 2 題），114 第 5 題也有。
• 整除關係與因數集合（111 第 3 題），110 第 3 題也用整除關係。
• 符號個數的奇偶限制與機率（111 第 5 題），112 第 6 題、114 第 8 題也有。
• 二進位字串的遞迴（111 第 6 題），112 第 7 題、114 第 6 題也是遞迴建模。
• 遞迴與機率包裝（111 第 7 題），109 第 7 題、110 第 6 題也有 recurrence relation。
• 迴文與彈珠分配的計數（111 第 4、8 題），113 第 2 題也有迴文，但那題是三位數的迴文，111 第 4 題是整數 n 的迴文。