115 交大資工所考古題解答｜數學考點分析

線代與離散各 50%。第 1 題四組是非題與 107 年第 11–14 題是同一套題幹，離散部分有五個獨立小題與兩題 induction 證明。

題型與配分

全卷 3 頁、9 題、100 分，不可使用計算機。

題號	主題	配分
1	線代是非題（四組）	20%
2	A² = −I 的一般條件	5%
3	determinant 計算	5%
4	SVD	8%
5	‖x‖ = 1 下的 least squares 解（有倒扣）	12%
6	五個獨立數學小題	25%
7	三條互相耦合的數列	10%
8	模關係的交集與聯集	8%
9	K_n − S 的 Hamiltonian cycle induction 證明	7%

第 1 題（20%，四組各 5%）｜是非題，假的要給反例：
1.1｜nonsingular 矩陣的四個定義（不可逆？存在 AB=BA=I？determinant 非零？Ax=0 有非零解？）
1.2｜elementary matrix 的四個定義（交換兩列、乘非零常數、加倍數、重排行）
1.3｜determinant 的性質（det(A)=det(B) ⟹ A=B？det(rA+B) 的分配？row equivalent 矩陣的 determinant？）
1.4｜n 個 column vector 與 A = [a₁…a_n]（linearly independent 與 singularity？Ax=0？rank + nullity？rank(A) 與 rank(A^T)？）
這四組與 107 年第 11–14 題是同一套題幹，但每組少了第 5 個小項，部分敘述也改寫（例如 1.1(2)、1.3(2)、1.4(1)），不是一字不差。
第 2 題（5%）｜找出滿足 A² = −I 的 2×2 實矩陣的一般條件
第 3 題（5%）｜求一個大型 sparse matrix 的 determinant
第 4 題（8%）｜求給定矩陣的 SVD 並驗證答案
第 5 題（12%）｜A 為 m×n、x 為 n×1：(a) 4% 在 ‖x‖ = 1 的限制下，Ax = 0 的 least squares 解是什麼 (b) 8% 證明你的答案。卷面寫著「不會寫請留白，答錯最多倒扣 5 分，扣至 3、4、5 題 0 分為止」

第 6 題（25%，五個獨立小題各 5%）｜
6.1｜判斷 ∃a∀b(b∈a ↔ b∉b) 是 tautology、contradiction 還是兩者皆非，要嚴格證明
6.2｜求 x，使無窮級數 Σ_r=2^∞ 2^x−r = √(1+3×2^x−2)，要說明過程
6.3｜求 √5+√6+√7+√8+√9+√10+√11+√12+√13 的整數部分，要說明如何得到
6.4｜T 為 243 個 1 組成的數（重複單位數 R₂₄₃），問 T 是否能被 243 整除，要說明理由
6.5｜嚴格遞增函數 f : N → N 滿足 f(f(x)) = 2x + 1，求 f(6)
第 7 題（10%）｜三條互相耦合的數列 x_n、y_n、z_n：(a) 3% 令 u_n = x_n+y_n+z_n，用 induction 證明 u_n 的通式 (b) 3% 由 (a) 導出 y_n 與 y_n−1 的關係 (c) 4% 解出 y_n 的 closed form 並驗證初始條件。題目明訂沒有論證的答案不給分
第 8 題（8%）｜R 為 mod 7 congruence、S 為 mod 13 congruence：(a) 4% R ∩ S 是否為 equivalence relation (b) 4% R ∪ S 是否為 equivalence relation。是的要證明，不是的要指出違反哪一條性質
第 9 題（7%）｜complete graph K_n（n ≥ 5）移除一組失效的節點與連線 S（|S| ≤ n−3，且失效連線不與失效節點相連），用對 n 的 induction 證明 K_n − S 仍含 Hamiltonian cycle。題目明訂不得引用任何 Hamiltonian graph 的判定定理