111 年 國立政治大學資訊科學系碩士班《計算機數學》

這題考驗的是鴿籠原理（Pigeonhole Principle）。題目敘述「如果 50 位學生被分到 $n$ 個教室，則必定有一個教室至少有 $k$ 位學生」，這句話可以用數學方式表達為：若有 $N$ 個物品分給 $k$ 個盒子，則至少有一個盒子包含 $\lceil N/k \rceil$ 個物品。在這裡，學生是物品，教室是盒子。因此，題目等價於問，對於給定的 $(n, k)$，是否成立 $\lceil 50/n \rceil \ge k$。

我們逐一檢驗選項：
(a) $(n, k) = (3, 15)$：$\lceil 50/3 \rceil = \lceil 16.67 \rceil = 17$。因為 $17 \ge 15$，所以此選項成立。
(b) $(n, k) = (70, 3)$：$\lceil 50/70 \rceil = \lceil 0.71 \rceil = 1$。

核心觀念

漸近記號描述函數在 $N$ 趨近無窮大時的成長速度。令

$$f(N)=3N^3\log N+4N\log N$$

若兩個函數的比值趨近正的有限常數，則兩者為 $\Theta$；若比值有界，則為 $O$；若比值有正的下界，則為 $\Omega$。

解題方法

比較兩項的成長速度：

$$\frac{4N\log N}{3N^3\log N}=\frac{4}{3N^2}\longrightarrow 0$$

因此，$4N\log N$ 相較於 $3N^3\log N$ 的影響逐漸消失，主導項是 $3N^3\log N$。常數因子不影響漸近階，所以

$$f(N)=\Theta(N^3\log N)$$

選項分析

• (a) $\Theta(N^2\log N)$：錯誤。 比較 $f(N)$ 與 $N^2\log N$：

  $$\frac{f(N)}{N^2\log N}=3N+\frac{4}{N}$$

  此比值趨近無窮大，兩者不是同階，因此不成立。

• (b) $O(N^3)$：錯誤。 比較 $f(N)$ 與 $N^3$：

本題考查條件機率（Conditional Probability）的定義。
條件機率的定義是：$P(B|A) = \frac{P(A \cap B)}{P(A)}$，前提是 $P(A) > 0$。

題目中提到 A 和 B 是「disjoint events」，這意味著 A 和 B 是互斥事件，也就是說它們不可能同時發生。

本題要求使用遞迴樹（Recursion Tree）方法來找出遞迴關係式 $T(n) = 3T(n/2) + n$ 的漸進上界。

遞迴樹的建構步驟如下：

1. 根節點 (Root): 代表 $T(n)$。它的成本是 $n$。它有 3 個子節點，每個代表 $T(n/2)$。
2. 第一層 (Level 1): 根節點有 3 個子節點，每個子節點代表 $T(n/2)$。每個子節點的成本是 $n/2$。這一層的總成本是 $3 \times (n/2) = \frac{3}{2}n$。
3. 第二層 (Level 2): 第一層的每個節點又有 3 個子節點，總共有 $3 \times 3 = 9$ 個節點。每個節點代表 $T(n/4)$。每個節點的成本是 $n/4$。這一層的總成本是 $9 \times (n/4) = \frac{9}{4}n$。
4. 第 $k$ 層 (Level k): 這一層有 $3^k$ 個節點。每個節點代表 $T(n/2^k)$。每個節點的成本是 $n/2^k$。這一層的總成本是 $3^k \times (n/2^k) = n (3/2)^k$。

遞迴何時終止？當遞迴的參數 $n/2^k$ 變為常數（例如 1）時。假設 $n/2^k = 1$，則 $2^k = n$，所以 $k = \log_2 n$。
遞迴樹的總高度大約是 $\log_2 n$。

遞迴樹的總成本是所有層級成本的總和：
$T(n) = n + \frac{3}{2}n + \frac{9}{4}n + \dots + n \left(\frac{3}{2}\right)^k + \dots$
最後一層的節點是 $3^k$ 個，其中 $k = \log_2 n$。所以最後一層有 $3^{\log_2 n}$ 個節點。
$3^{\log_2 n} = n^{\log_2 3}$。
最後一層的成本是 $3^k \times T(n/2^k)$。假設 $T(1) = c$ (一個常數)。
則最後一層的成本是 $n^{\log_2 3} \times c$。

總成本 $T(n)$ 是所有層級成本的總和：
$T(n) = \sum_{i=0}^{\log_2 n - 1} n \left(\frac{3}{2}\right)^i + n^{\log_2 3} \cdot c$

這個總和是一個幾何級數。
$T(n) = n \left[ \sum_{i=0}^{\log_2 n - 1} \left(\frac{3}{2}\right)^i \right] + c \cdot n^{\log_2 3}$

本題要求使用數學歸納法（Mathematical Induction）證明對於所有正整數 $n$，乘積 $n(n+1)(n+2)$ 恆為 3 的倍數。

設 $P(n)$ 為敘述「$n(n+1)(n+2)$ 可被 3 整除」。

1. 基本情況 (Base Case):
當 $n=1$ 時，我們要驗證 $P(1)$ 是否成立。
$1(1+1)(1+2) = 1 \times 2 \times 3 = 6$。
因為 6 可以被 3 整除 ($6 = 3 \times 2$)，所以 $P(1)$ 成立。

2. 歸納假設 (Inductive Hypothesis):
假設對於某個正整數 $k \ge 1$，敘述 $P(k)$ 成立。也就是說，$k(k+1)(k+2)$ 可以被 3 整除。
這表示存在一個整數 $m$，使得 $k(k+1)(k+2) = 3m$。

3. 歸納步驟 (Inductive Step):
我們需要證明 $P(k+1)$ 也成立。也就是說，$(k+1)((k+1)+1)((k+1)+2)$ 可以被 3 整除。
考慮 $(k+1)((k+1)+1)((k+1)+2) = (k+1)(k+2)(k+3)$。

展開這個式子：
$(k+1)(k+2)(k+3) = (k+1)(k+2) \times k + (k+1)(k+2) \times 3$
$= (k+1)(k+2)k + 3(k+1)(k+2)$

本題要求利用期望值（Expected Value）和變異數（Variance）的定義，證明兩個獨立連續隨機變數和的期望值與變異數的性質。

定義回顧：
對於一個連續隨機變數 $Y$，其機率密度函數為 $f_Y(y)$：

• 期望值：$E[Y] = \int_{-\infty}^{\infty} y f_Y(y) dy$
• 變異數：$Var[Y] = E[(Y - E[Y])^2] = \int_{-\infty}^{\infty} (y - E[Y])^2 f_Y(y) dy$
  同時，$Var[Y] = E[Y^2] - (E[Y])^2$

已知條件：
$X$ 和 $Z$ 是統計獨立的連續隨機變數。
設 $f_X(x)$ 和 $f_Z(z)$ 分別是 $X$ 和 $Z$ 的機率密度函數。
由於 $X$ 和 $Z$ 獨立，它們的聯合機率密度函數為 $f_{X,Z}(x, z) = f_X(x) f_Z(z)$。

---

(a) 證明 $E[X + Z] = E[X] + E[Z]$

根據期望值的定義，對於兩個隨機變數的函數 $g(X, Z)$，其期望值為：
$E[g(X, Z)] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} g(x, z) f_{X,Z}(x, z) dx dz$

令 $g(X, Z) = X + Z$。
$E[X + Z] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} (x + z) f_{X,Z}(x, z) dx dz$

因為 $X$ 和 $Z$ 獨立，$f_{X,Z}(x, z) = f_X(x) f_Z(z)$。
$E[X + Z] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} (x + z) f_X(x) f_Z(z) dx dz$

我們可以將積分拆開：
$E[X + Z] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} x f_X(x) f_Z(z) dx dz + \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} z f_X(x) f_Z(z) dx dz$

對於第一個積分：
$\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} x f_X(x) f_Z(z) dx dz = \int_{-\infty}^{\infty} x f_X(x) \left( \int_{-\infty}^{\infty} f_Z(z) dz \right) dx$
因為 $\int_{-\infty}^{\infty} f_Z(z) dz = 1$ (機率密度函數的總積分為 1)，所以：
$\int_{-\infty}^{\infty} x f_X(x) (1) dx = \int_{-\infty}^{\infty} x f_X(x) dx = E[X]$

對於第二個積分：
$\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} z f_X(x) f_Z(z) dx dz = \int_{-\infty}^{\infty} f_X(x) \left( \int_{-\infty}^{\infty} z f_Z(z) dz \right) dx$

核心觀念

本題考查：

• 整除的基本性質；
• 質因數分解；
• 費馬小定理。

將 $222$ 分解為

$$222=2\times 3\times 37.$$

因此，只要證明差值 $2^a-2^b$ 同時被 $2$、$3$、$37$ 整除，即可推出被 $222$ 整除。

取 $a>b$，則

$$2^a-2^b=2^b\left(2^{a-b}-1\right).$$

由於 $b$ 為正整數，$2^b$ 本身含有因數 $2$。問題轉化為選擇 $a-b$，使得 $2^{a-b}-1$ 同時被 $3$ 與 $37$ 整除。

解題方法

取

$$a-b=36.$$

例如令

$$b=1,\qquad a=37.$$

此時

$$2^a-2^b=2^{37}-2=2\left(2^{36}-1\right).$$

接著分別檢查 $3$ 與 $37$：

被 $3$ 整除

因為

$$2^2=4\equiv 1\pmod 3,$$

且 $36$ 是 $2$ 的倍數，所以

$$2^{36}=(2^2)^{18}\equiv 1^{18}\equiv 1\pmod 3.$$

因此

$$3\mid (2^{36}-1).$$

被 $37$ 整除

由費馬小定理，因為 $37$ 是質數且 $37\nmid 2$，所以

本題要求解一個二階線性齊次遞迴關係式（Second-order linear homogeneous recurrence relation）$a_n = 5a_{n-1} - 6a_{n-2}$，並給定了初始條件 $a_0 = 1$ 和 $a_1 = 0$。

步驟 1：找出特徵方程式 (Characteristic Equation)
對於形如 $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ 的遞迴關係式，其特徵方程式為 $r^2 = c_1 r - c_2$。
在本題中，$c_1 = 5$，$c_2 = -6$。
所以，特徵方程式為：
$r^2 = 5r - 6$
$r^2 - 5r + 6 = 0$

步驟 2：解特徵方程式
我們可以分解這個二次方程式：
$(r - 2)(r - 3) = 0$
因此，特徵根為 $r_1 = 2$ 和 $r_2 = 3$。

步驟 3：寫出通解 (General Solution)
由於特徵根是兩個不相等且實數的根，遞迴關係式的通解形式為：
$a_n = c_1 r_1^n + c_2 r_2^n$
$a_n = c_1 (2)^n + c_2 (3)^n$
其中 $c_1$ 和 $c_2$ 是待定常數。

步驟 4：利用初始條件求出常數 $c_1$ 和 $c_2$
我們有初始條件 $a_0 = 1$ 和 $a_1 = 0$。

將 $n=0$ 代入通解：
$a_0 = c_1 (2)^0 + c_2 (3)^0$
$1 = c_1 (1) + c_2 (1)$
$1 = c_1 + c_2$ (方程式 1)

將 $n=1$ 代入通解：
$a_1 = c_1 (2)^1 + c_2 (3)^1$
$0 = 2c_1 + 3c_2$ (方程式 2)

核心觀念

本題考查模運算中的一次同餘方程組。主要使用：

• 同餘式中的係數可先對模數取餘數。
• 若 $\gcd(a,m)=1$，則 $a$ 在模 $m$ 下具有乘法反元素，可用來解 $ax\equiv b\pmod m$。
• 聯立同餘式必須同時滿足所有條件；若各同餘式對 $x$ 的要求互相矛盾，則無解。

解題方法

原方程組為

$$7x\equiv14\pmod6$$ $$5x\equiv3\pmod6$$

第一道同餘式

將係數與常數對 $6$ 取餘數：

$$7\equiv1\pmod6,\qquad 14\equiv2\pmod6$$

因此

$$7x\equiv14\pmod6$$

等價於

$$x\equiv2\pmod6$$

所以第一道方程要求 $x$ 的模 $6$ 餘數為 $2$。

第二道同餘式

因為

$$5\cdot5=25\equiv1\pmod6$$

所以 $5$ 在模 $6$ 下的乘法反元素仍為 $5$。兩邊同乘以 $5$：

本題為判斷題，需要對線性代數中的矩陣性質有清晰的理解。

(a) If a rectangle matrix A is invertible, A could have a zero singular value.
False.
一個矩陣是可逆的（invertible）充要條件是它的所有奇異值（singular values）均為非零。如果一個矩陣至少有一個奇異值為零，則該矩陣是奇異的（singular），不可逆。
嚴格來說，可逆性通常定義在方陣上。如果題目中的 "rectangle matrix" 指的是方陣，那麼可逆矩陣的所有奇異值都必須大於零。
如果 "rectangle matrix" 指的是非方陣，那麼非方陣（$m \times n$ 且 $m \ne n$）定義上就不是可逆的。
無論如何解釋，一個可逆矩陣不可能有零奇異值。

(b) If a matrix B is similar to A, then B has the same eigenvectors as A.
False.
如果矩陣 $B$ 與矩陣 $A$ 相似，則存在一個可逆矩陣 $P$ 使得 $B = P^{-1}AP$。
相似矩陣共享許多性質，例如它們有相同的特徵值（eigenvalues）。
但是，它們不一定有相同的特徵向量（eigenvectors）。
如果 $v$ 是 $A$ 的一個特徵向量，對應於特徵值 $\lambda$，即 $Av = \lambda v$。
那麼，對於 $B = P^{-1}AP$，我們可以計算 $B(P^{-1}v) = P^{-1}AP(P^{-1}v) = P^{-1}A(PP^{-1})v = P^{-1}Av = P^{-1}(\lambda v) = \lambda (P^{-1}v)$。
這表示 $P^{-1}v$ 是 $B$ 的一個特徵向量，對應於相同的特徵值 $\lambda$。
因此，如果 $v$ 是 $A$ 的特徵向量，則 $P^{-1}v$ 是 $B$ 的特徵向量。
除非 $P$ 是單位矩陣 $I$ (此時 $B=A$)，否則 $P^{-1}v$ 通常與 $v$ 不同。
所以，相似矩陣不一定有相同的特徵向量。

(c) Any symmetric matrix is similar to a diagonal matrix.
True.
這是譜定理（Spectral Theorem）的一個重要結論。對於實對稱矩陣（real symmetric matrix），它總是正交相似於一個對角矩陣。也就是說，存在一個正交矩陣 $P$ (使得 $P^{-1} = P^T$) 和一個對角矩陣 $D$，使得 $A = PDP^T$。對角矩陣的對角線元素就是該對稱矩陣的特徵值。

核心觀念

本題考查最小平方解、正交投影與矩陣的基本子空間。當線性方程 $Ax=b$ 無法精確成立時，最小平方解 $\tilde{x}$ 使殘差 $A\tilde{x}-b$ 的長度最小。

以下依題意採用 $A\in\mathbb{R}^{m\times n}$、$m\ge n$ 且 $A$ 滿列秩的設定。此時 $A^TA$ 可逆，最小平方解唯一。

解題方法

(a) 推導最佳最小平方解

選取 $\tilde{x}$ 使平方誤差最小：

$$\tilde{x}=\arg\min_x \|Ax-b\|_2^2$$

將目標函數展開：

$$\begin{aligned} \|Ax-b\|_2^2 &=(Ax-b)^T(Ax-b)\\ &=x^TA^TAx-2x^TA^Tb+b^Tb \end{aligned}$$

對 $x$ 求梯度並令其為零：

$$\nabla_x\|Ax-b\|_2^2=2A^TAx-2A^Tb=0$$

因此得到正規方程：

$$A^TA\tilde{x}=A^Tb$$

因為 $A$ 滿列秩，$A^TA$ 可逆，故

$$\boxed{\tilde{x}=(A^TA)^{-1}A^Tb}$$

(b) 投影向量與殘差所屬子空間

令 $p=A\tilde{x}$。由於 $p$ 是 $A$ 的欄向量的線性組合，

$$\boxed{p\in\operatorname{Col}(A)}$$

正規方程也可寫成

$$A^T(A\tilde{x}-b)=0$$

所以 $p-b=A\tilde{x}-b$ 與 $A$ 的每一個欄向量都正交，亦即

$$\boxed{p-b\in N(A^T)}$$

因此，$p$ 是 $b$ 在 $\operatorname{Col}(A)$ 上的正交投影；$p-b$ 是其投影誤差，位於左零空間 $N(A^T)$。若使用常見殘差定義 $b-p$，它同樣位於 $N(A^T)$。

(c) 求投影矩陣

投影到 $\operatorname{Col}(A)$ 的矩陣為

$$P=A(A^TA)^{-1}A^T$$

本題的矩陣為

核心觀念
本題的重點在於把給定的線性遞迴式寫成矩陣乘法的形式，從而得到遞迴矩陣 $A$；再利用 $M^{T}M$ 的特性（對稱、半正定）推導 $A$ 的特徵值與特徵向量，最後以特徵值的大小討論 $x_n$ 的長期行為。第 (d) 則是利用遞迴式的特殊條件直接得到 $M^{T}M$ 的特徵值，進而求出奇異值。

---

(a) 求遞迴矩陣 $A$

遞迴式

$\bigl(M^{T}M+4I\bigr)x_{n+1}= \bigl(M^{T}M-4I\bigr)x_{n}$

左乘 $\bigl(M^{T}M+4I\bigr)^{-1}$（此矩陣必為可逆，因 $M^{T}M$ 為半正定且 $+4I$ 加上正定矩陣）得到

$x_{n+1}= \bigl(M^{T}M+4I\bigr)^{-1}\bigl(M^{T}M-4I\bigr)x_{n}.$

若寫成 $x_{n}=A^{n}x_{0}$，則

$\boxed{A=\bigl(M^{T}M+4I\bigr)^{-1}\bigl(M^{T}M-4I\bigr)}.$

此 $A$ 與任意的起始向量 $x_{0}$ 無關，只與矩陣 $M$ 有關。
【答案】$A=(M^{T}M+4I)^{-1}(M^{T}M-4I)$

---

(b) 由 $M^{T}M$ 的特徵對應 $A$ 的特徵

設 $\lambda$ 為 $M^{T}M$ 的特徵值，對應特徵向量 $v\;(v\neq0)$，即

$M^{T}M\,v=\lambda v .$

將 $v$ 代入 $A$ 的定義：

$$\begin{aligned} A v &=\bigl(M^{T}M+4I\bigr)^{-1}\bigl(M^{T}M-4I\bigr)v \\ &=\bigl(M^{T}M+4I\bigr)^{-1}\bigl(\lambda-4\bigr)v \\ &=\frac{\lambda-4}{\lambda+4}\,v . \end{aligned}$$

因此 $v$ 同時也是 $A$ 的特徵向量，對應的特徵值為

$\boxed{\mu=\frac{\lambda-4}{\lambda+4}}.$

【答案】特徵對為 $\bigl(v,\;\dfrac{\lambda-4}{\lambda+4}\bigr)$。

---

(c) 大 $n$ 時 $x_{n}$ 的可能行為

因 $x_{n}=A^{n}x_{0}$，長期行為完全由 $A$ 的特徵值 $\mu$ 的模長 $\lvert\mu\rvert$ 決定。
對於任意 $\lambda\ge0$（$M^{T}M$ 為半正定）：

$$\mu=\frac{\lambda-4}{\lambda+4},\qquad \lvert\mu\rvert=\frac{|\,\lambda-4\,|}{\lambda+4}.$$