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

題型與配分

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

逐題考點

• 第 1 題（10%）｜x₁, x₂, …, x_n 是 n 個整數的序列，連續子序列定義為 x_i, x_i+1, …, x_j（1 ≤ i ≤ j ≤ n），證明對任意 k（1 ≤ k ≤ n）都存在一個和可被 k 整除的連續子序列
• 第 2 題（10%）｜數列由 x₀ = 0、x₁ = 1 與 x_n + 2x_n−1 = 15x_n−2（n > 1）定義，求這個數列的 generating function，再求 x_n 的一般式
• 第 3 題（10%）｜證明 C(n,k) = C(n−1,k) + C(n−1,k−1)，並給出這個等式的 combinatorial interpretation
• 第 4 題（30%）｜題目先定義 bipartite graph（頂點分成 X、Y 兩個子集，每條邊一端在 X、一端在 Y）、cycle 與 cycle 的長度，以及 k-cube（頂點是長度 k 的二進位字串，恰好差一個位元的兩個頂點相鄰）：(a) 10% 把 k-cube 的頂點分成 X 與 Y，再證明每條邊都連接 X 與 Y 的頂點，藉此證明每個 k-cube 都是 bipartite graph (b) 10% 證明 bipartite graph 沒有奇數長度的 cycle (c) 10% 證明沒有奇數長度 cycle 的圖是 bipartite graph
• 第 5 題（10%）｜邊長 2 的正方形內任選 5 個點，證明一定有兩點 p、q 的距離不超過 √2
• 第 6 題（10%）｜Fibonacci 數定義為 f₀ = 0、f₁ = 1、f_n = f_n−1 + f_n−2（n > 1），證明對每個正整數 k，f_3k 都是偶數
• 第 7 題（20%）｜m、n 為正整數且 m ≤ n，C(n,m) = n!/(m!(n−m)!)：(a) 10% 證明若 n 是質數，則 n 整除每個 C(n,i)（1 ≤ i < n） (b) 10% 證明若 n 是合數，則存在某個 i（1 ≤ i < n）使 n 不整除 C(n,i)

作答時要注意的地方

1. 7 題中除了第 2 題，其餘六題都是證明題，卷首規定沒有詳細步驟該題不給分。
2. 第 2 題題目要求先求 generating function，再求 x_n 的一般式。
3. 第 3 題除了證明等式，還要寫出 combinatorial interpretation。
4. 第 4 題 30 分，(b)(c) 是同一個敘述的兩個方向，各 10 分。
5. 第 4(a) 題卷面指定了證明的寫法：先把頂點分成 X 與 Y，再證明每條邊都連接 X 與 Y。

準備方向

• pigeonhole 與存在性論證（106 第 1、5 題），108 第 5 題、109 第 4 題、110 第 3 題、111 第 1 題、112 第 3 題、114 第 4 題、115 B3 也有。
• 用 generating function 解遞迴（106 第 2 題），113 第 10 題指定用 generating function 解二階遞迴，107 第 1、2 題、108 第 7 題、109 第 6 題、112 第 5 題也有 generating function。
• combinatorial identity 與 combinatorial interpretation（106 第 3 題），108 到 115 年每年都有計數題。
• 圖論（106 第 4 題的 k-cube 與 bipartite graph），109 第 8 題考 complete bipartite graph K_m,n。
• 遞迴數列的性質（106 第 6 題的 Fibonacci 數），107 第 3 題、109 到 114 年也有 recurrence relation。
• 數論與整除的證明（106 第 7 題），108 第 8 題、109 第 2、9 題、110 第 2 題、112 第 2、8 題、113 第 3 題也有。