113 年 國立成功大學工程科學系碩士班乙組《計算機數學》

這題考的是集合論中的包含排斥原理。我們使用符號 E, H, G 分別代表修習英文、歷史、地理的學生集合。

已知條件：
總學生數 $N = 100$
$|E| = 45$
$|H| = 30$
$|G| = 20$
至少兩門課的學生數 $|E \cap H| + |E \cap G| + |H \cap G| - 3|E \cap H \cap G| = 10$ (此為直接計算至少兩門課的公式，但題目給的是「10 in at least two of three courses」，這句話的解釋有兩種可能：
解釋一：至少有兩門課的學生總人數是 10。
解釋二：所有兩兩交集的總和減去三者交集的總和是 10。
根據後面的「just 1 student is enrolled in all three courses」，通常此類題目給的「at least two」是指「exactly two」的總和加上「exactly three」的總和。
但更標準的說法是 $|(E \cap H) \cup (E \cap G) \cup (H \cap G)| = 10$。
然而，若我們假設「10 in at least two of three courses」指的是 $|E \cap H| + |E \cap G| + |H \cap G| = 10$ 且 $|E \cap H \cap G|=1$ 是不合理的。
這裡我們採用一個更常見的解釋，即：
$|(E \cap H) \setminus G| + |(E \cap G) \setminus H| + |(H \cap G) \setminus E| + |E \cap H \cap G| = 10$ (恰好兩門課的學生數加上三門課的學生數)
或者，另一種更常見的理解是：
$|E \cap H| + |E \cap G| + |H \cap G| = 10$ (所有兩兩交集的總和，但這也包含了三者交集的部分)
不過，最常見的題目敘述為「10 students are enrolled in at least two courses」。
根據題目給的 10 in at least two of three courses 和 just 1 student is enrolled in all three courses，更合理的解釋是：
$|(E \cap H) \cup (E \cap G) \cup (H \cap G)| = 10$
並且 $|E \cap H \cap G| = 1$。
根據包含排斥原理，我們知道：
$|E \cup H \cup G| = |E| + |H| + |G| - (|E \cap H| + |E \cap G| + |H \cap G|) + |E \cap H \cap G|$
另外，我們也知道：
$|(E \cap H) \cup (E \cap G) \cup (H \cap G)| = |E \cap H| + |E \cap G| + |H \cap G| - 2|E \cap H \cap G|$
代入已知條件：
$10 = |E \cap H| + |E \cap G| + |H \cap G| - 2(1)$
所以 $|E \cap H| + |E \cap G| + |H \cap G| = 10 + 2 = 12$。

(a) 求至少修習一門課的學生數：
使用包含排斥原理：
$|E \cup H \cup G| = |E| + |H| + |G| - (|E \cap H| + |E \cap G| + |H \cap G|) + |E \cap H \cap G|$
$|E \cup H \cup G| = 45 + 30 + 20 - (12) + 1$
$|E \cup H \cup G| = 95 - 12 + 1 = 84$

【答案】(a) 84

這題考驗機率的基本計算，特別是事件的獨立性以及「至少一個」事件發生的機率。
假設學生 A、B、C 解決問題的事件分別為 $S_A, S_B, S_C$。
已知條件：
$P(S_A) = 1/2$
$P(S_B) = 1/3$
$P(S_C) = 1/4$
假設這三個學生解決問題的事件是獨立的。

要求的是問題被解決的機率，這意味著至少有一個學生解決了問題。
我們可以計算「問題沒有被解決」的機率，然後用 1 減去它。
問題沒有被解決的機率，就是 A 沒解決、B 沒解決、C 也沒解決的機率。
令 $S_A^c, S_B^c, S_C^c$ 分別代表學生 A, B, C 未解決問題的事件。
$P(S_A^c) = 1 - P(S_A) = 1 - 1/2 = 1/2$
$P(S_B^c) = 1 - P(S_B) = 1 - 1/3 = 2/3$
$P(S_C^c) = 1 - P(S_C) = 1 - 1/4 = 3/4$

因為事件是獨立的，所以：
$P(\text{problem is not solved}) = P(S_A^c \cap S_B^c \cap S_C^c) = P(S_A^c) \times P(S_B^c) \times P(S_C^c)$
$P(\text{problem is not solved}) = (1/2) \times (2/3) \times (3/4) = 6/24 = 1/4$

這題是關於機率的基本計算，涉及樣本空間、事件以及質數的定義。
當兩個骰子被投擲時，樣本空間的大小是 $6 \times 6 = 36$ 種可能結果。
我們需要找出點數總和為質數的組合。
質數是只能被 1 和本身整除的大於 1 的正整數。
在兩個骰子點數總和的範圍 (2 到 12) 中，質數有：2, 3, 5, 7, 11。

我們列出總和為這些質數的組合：
總和為 2：(1, 1) - 1 種組合
總和為 3：(1, 2), (2, 1) - 2 種組合
總和為 5：(1, 4), (4, 1), (2, 3), (3, 2) - 4 種組合

核心觀念

本題考查：

1. 重複字母的排列
2. 分組法（將連續出現的母音視為一個整體）
3. 機率定義
   $P(E)=\frac{\text{符合事件 }E\text{ 的排列數}}{\text{所有可能排列數}}$

單字 AFFLIATION 共 10 個字母：

• 母音：$A,A,I,I,O$，共 5 個
• 子音：$F,F,L,T,N$，共 5 個

其中 $A$、$F$、$I$ 各重複 2 次。

---

解題方法

1. 計算所有不同排列數

10 個字母中，$A$、$F$、$I$ 各出現 2 次，因此不同排列總數為

$$N_{\text{total}} =\frac{10!}{2!2!2!}$$

---

2. 計算所有母音連在一起的排列數

要求 5 個母音全部相鄰，先將母音視為一個整體：

$$(A,A,I,I,O)$$

此時需排列的物件為：

• 1 個母音區塊
• $F,F,L,T,N$ 共 5 個子音

合計 6 個物件，其中 $F$ 重複 2 次，因此外部排列數為

$$\frac{6!}{2!}$$

母音區塊內部的排列為 $A,A,I,I,O$ 的不同排列數：

$$\frac{5!}{2!2!}$$

所以符合條件的排列數為

這題考查線性代數中矩陣的秩 (rank) 與線性方程組 $Ax=b$ 解的性質。

已知條件：
矩陣 $A$ 的維度是 $3 \times 5$。
矩陣 $A$ 的秩 (rank) $r = 3$。

我們知道，對於一個 $m \times n$ 的矩陣 $A$，其秩 $r$ 滿足 $r \le \min(m, n)$。
在這裡，$m=3, n=5$，所以 $\min(m, n) = 3$。
秩 $r=3$ 意味著矩陣 $A$ 達到了其行數的最大值，這表示 $A$ 的行是線性獨立的，並且 $A$ 的列空間的維度是 3。

線性方程組 $Ax=b$ 的解的性質與矩陣 $A$ 的秩以及增廣矩陣 $[A|b]$ 的秩有關。
一個線性方程組 $Ax=b$ 有解的條件是 $rank(A) = rank([A|b])$。
如果方程組有解，那麼：

• 如果 $rank(A) = n$ (其中 $n$ 是變數的個數)，則解是唯一的。
• 如果 $rank(A) < n$，則有無限多個解 (many solutions)。

在本題中，矩陣 $A$ 是 $3 \times 5$，所以變數的個數 $n=5$。
我們已知 $rank(A) = 3$。

首先考慮方程組是否有解。
$rank(A) = 3$。
增廣矩陣 $[A|b]$ 的維度是 $3 \times 6$。
$rank([A|b])$ 的最大值是 $\min(3, 6) = 3$。
因為 $rank(A) = 3$，且 $rank([A|b])$ 的最大值也是 3，所以 $rank([A|b])$ 可能等於 3。
如果 $rank(A) = rank([A|b]) = 3$，則方程組有解。
如果 $rank(A) < rank([A|b])$，則方程組無解。
由於 $A$ 是 $3 \times 5$ 且 $rank(A)=3$，這意味著 $A$ 的行是線性獨立的。

這題是關於求解二階線性齊次遞迴關係式，並給定初始條件。

遞迴關係式為：$A_n = 2A_{n-1} + 15A_{n-2}$
初始條件為：$A_0 = 1$, $A_1 = -4$

首先，我們寫出對應的特徵方程式 (characteristic equation)：
$r^2 = 2r + 15$
$r^2 - 2r - 15 = 0$

接著，我們解這個二次方程式以找到特徵根。
可以使用因式分解法：
$(r-5)(r+3) = 0$
所以，特徵根為 $r_1 = 5$ 和 $r_2 = -3$。

因為特徵根是兩個不同的實數，所以遞迴關係式的通解形式為：
$A_n = c_1 r_1^n + c_2 r_2^n$
$A_n = c_1 (5)^n + c_2 (-3)^n$

接下來，我們利用初始條件來求解常數 $c_1$ 和 $c_2$。
當 $n=0$ 時，$A_0 = 1$：
$1 = c_1 (5)^0 + c_2 (-3)^0$
$1 = c_1 + c_2$ (方程式 1)

當 $n=1$ 時，$A_1 = -4$：
$-4 = c_1 (5)^1 + c_2 (-3)^1$
$-4 = 5c_1 - 3c_2$ (方程式 2)

現在我們解這個聯立方程式來找出 $c_1$ 和 $c_2$。
從方程式 1，我們得到 $c_2 = 1 - c_1$。
將其代入方程式 2：
$-4 = 5c_1 - 3(1 - c_1)$
$-4 = 5c_1 - 3 + 3c_1$

核心觀念

本題考查齊次線性方程組

$$A\mathbf{x}=\mathbf{0}$$

的解法，以及以下概念：

• 自由變數：對應矩陣中非主元欄的變數，可任意指定。
• 特殊解（special solution）：每次令一個自由變數為 $1$，其餘自由變數為 $0$ 所得到的非零解。
• 零空間（nullspace）：

$$N(A)=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{0}\}$$

所有特殊解所張成的集合，就是矩陣 $A$ 的零空間。

---

解題方法

令

$$\mathbf{x}= \begin{bmatrix} x_1\\x_2\\x_3\\x_4 \end{bmatrix}$$

由 $A\mathbf{x}=\mathbf{0}$ 得到方程組

$$\begin{cases} x_2+2x_3+2x_4=0,\\ 3x_2+8x_3+7x_4=0,\\ 4x_3+2x_4=0. \end{cases}$$

先由第三式求出 $x_3$：

$$4x_3+2x_4=0$$

因此

$$x_3=-\frac{1}{2}x_4.$$

代入第一式：

$$x_2+2\left(-\frac{1}{2}x_4\right)+2x_4=0$$

整理得

$$x_2-x_4+2x_4=0,$$

所以

$$x_2=-x_4.$$

第二式會自動滿足，因為

$$3(-x_4)+8\left(-\frac{1}{2}x_4\right)+7x_4 = -3x_4-4x_4+7x_4 =0.$$

矩陣的第一欄全為 $0$，因此 $x_1$ 沒有受到任何限制；此外 $x_4$ 也可自由指定。令

$$x_1=s,\qquad x_4=t.$$

則

$$x_2=-t,\qquad x_3=-\frac{1}{2}t.$$

所以所有解可寫成

$$\mathbf{x} = \begin{bmatrix} s\\ -t\\ -\frac{1}{2}t\\ t \end{bmatrix}.$$

將其拆成參數線性組合：

$$\mathbf{x} = s \begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} + t \begin{bmatrix} 0\\-1\\-\frac12\\1 \end{bmatrix}.$$

---

特殊解

自由變數為 $x_1$ 與 $x_4$。

令 $x_1=1,\ x_4=0$

此時

$$\mathbf{x}^{(1)} = \begin{bmatrix} 1\\0\\0\\0 \end{bmatrix}.$$

令 $x_1=0,\ x_4=1$

此時

$$\mathbf{x}^{(2)} = \begin{bmatrix} 0\\-1\\-\frac12\\1 \end{bmatrix}.$$

核心觀念

本題考查兩部分：

1. 特徵值與特徵向量

   • 特徵值滿足
     $\det(A-\lambda I)=0$
   • 對應特徵向量滿足
     $A\mathbf{x}=\lambda\mathbf{x}$

2. 奇異值分解

   • 若
     $A=U\Sigma V^T$
     則 $A^TA$ 的特徵值是奇異值的平方。
   • $V$ 的欄向量是 $A^TA$ 的標準正交特徵向量。
   • 若 $\sigma_i>0$，則
     $\mathbf{u}_i=\frac{A\mathbf{v}_i}{\sigma_i}$

已知

$$A= \begin{bmatrix} -1&1\\ 4&0 \end{bmatrix}$$

---

(a) 特徵值與特徵向量

求特徵值

計算特徵方程式：

$$\det(A-\lambda I) = \det \begin{bmatrix} -1-\lambda&1\\ 4&-\lambda \end{bmatrix}$$ $$=(-1-\lambda)(-\lambda)-4 =\lambda^2+\lambda-4$$

因此

$$\lambda^2+\lambda-4=0$$

由公式解得

$$\lambda_1=\frac{-1+\sqrt{17}}{2}, \qquad \lambda_2=\frac{-1-\sqrt{17}}{2}$$

---

求對應特徵向量

由

$$(A-\lambda I) \begin{bmatrix} x\\y \end{bmatrix} = \mathbf{0}$$

取第一列：

$$(-1-\lambda)x+y=0$$

所以

$$y=(1+\lambda)x$$

令 $x=1$，可取特徵向量

$$\mathbf{x}= \begin{bmatrix} 1\\ 1+\lambda \end{bmatrix}$$

因此：

對於

$$\lambda_1=\frac{-1+\sqrt{17}}{2}$$

有

$$1+\lambda_1=\frac{1+\sqrt{17}}{2}$$

可取

$$\mathbf{x}_1= \begin{bmatrix} 1\\[2pt] \dfrac{1+\sqrt{17}}{2} \end{bmatrix}$$

對於

$$\lambda_2=\frac{-1-\sqrt{17}}{2}$$

有

$$1+\lambda_2=\frac{1-\sqrt{17}}{2}$$

可取

$$\mathbf{x}_2= \begin{bmatrix} 1\\[2pt] \dfrac{1-\sqrt{17}}{2} \end{bmatrix}$$

特徵向量可乘上任意非零常數，因此上述答案不唯一。

---

(b) 奇異值分解 $A=U\Sigma V^T$

第一步：由 $A^TA$ 求 $V$ 與 $\Sigma$

先計算

$$A^T= \begin{bmatrix} -1&4\\ 1&0 \end{bmatrix}$$

因此

$$A^TA= \begin{bmatrix} -1&4\\ 1&0 \end{bmatrix} \begin{bmatrix} -1&1\\ 4&0 \end{bmatrix} = \begin{bmatrix} 17&-1\\ -1&1 \end{bmatrix}$$

令 $A^TA$ 的特徵值為 $\mu$，則

$$\det(A^TA-\mu I) = \det \begin{bmatrix} 17-\mu&-1\\ -1&1-\mu \end{bmatrix}$$ $$=(17-\mu)(1-\mu)-1 =\mu^2-18\mu+16$$

所以

$$\mu_1=9+\sqrt{65}, \qquad \mu_2=9-\sqrt{65}$$

奇異值為特徵值的正平方根：

$$\sigma_1=\sqrt{9+\sqrt{65}}, \qquad \sigma_2=\sqrt{9-\sqrt{65}}$$

通常依大小排列，故 $\sigma_1>\sigma_2$。

---

求右奇異向量與矩陣 $V$

對 $\mu_1=9+\sqrt{65}$，解

$$(A^TA-\mu_1I)\mathbf{v}_1=\mathbf{0}$$

由第一列：

$$(17-\mu_1)x-y=0$$

而

$$17-\mu_1=8-\sqrt{65}$$

故可取未正規化向量

$$\widetilde{\mathbf{v}}_1= \begin{bmatrix} 1\\ 8-\sqrt{65} \end{bmatrix}$$

其長度為

$$N_1=\sqrt{1+(8-\sqrt{65})^2}$$

所以

$$\mathbf{v}_1= \frac{1}{N_1} \begin{bmatrix} 1\\ 8-\sqrt{65} \end{bmatrix}$$

對 $\mu_2=9-\sqrt{65}$，同理可取

$$\widetilde{\mathbf{v}}_2= \begin{bmatrix} 1\\ 8+\sqrt{65} \end{bmatrix}$$

其長度為

$$N_2=\sqrt{1+(8+\sqrt{65})^2}$$

所以

$$\mathbf{v}_2= \frac{1}{N_2} \begin{bmatrix} 1\\ 8+\sqrt{65} \end{bmatrix}$$

注意到

核心觀念

本題考查：

• 離散時間的狀態轉移矩陣。
• 由轉移比例建立矩陣方程。
• 利用遞迴關係或特徵值判斷長期穩定狀態。
• 機率（比例）向量的總和在每次轉移後仍為 $1$。

令

$$\mathbf{v}_k= \begin{bmatrix} x_k\\ y_k \end{bmatrix}, \qquad x_k+y_k=1.$$

其中 $x_k$ 表示偏好微積分的比例，$y_k$ 表示偏好線性代數的比例。

解題方法

在第 $k+1$ 年偏好微積分的學生包括：

1. 原本偏好微積分且沒有改變想法者：比例為 $\frac45x_k$。
2. 原本偏好線性代數但改偏好微積分者：比例為 $\frac1{10}y_k$。

因此，

$$x_{k+1}=\frac45x_k+\frac1{10}y_k.$$

在第 $k+1$ 年偏好線性代數的學生包括：

1. 原本偏好微積分但改偏好線性代數者：比例為 $\frac15x_k$。
2. 原本偏好線性代數且沒有改變想法者：比例為 $\frac9{10}y_k$。

因此，

$$y_{k+1}=\frac15x_k+\frac9{10}y_k.$$

整理成矩陣形式：

$$\begin{bmatrix} x_{k+1}\\ y_{k+1} \end{bmatrix} = \begin{bmatrix} \frac45 & \frac1{10}\\ \frac15 & \frac9{10} \end{bmatrix} \begin{bmatrix} x_k\\ y_k \end{bmatrix}.$$

所以矩陣 $A$ 為

$$A= \begin{bmatrix} \frac45 & \frac1{10}\\ \frac15 & \frac9{10} \end{bmatrix}.$$

求長期極限

由於 $x_k+y_k=1$，可令 $y_k=1-x_k$。代入 $x_{k+1}$ 的遞迴式：

$$\begin{aligned} x_{k+1} &=\frac45x_k+\frac1{10}(1-x_k)\\ &=\frac7{10}x_k+\frac1{10}. \end{aligned}$$

其穩定值 $x$ 滿足

$$x=\frac7{10}x+\frac1{10}.$$

因此

$$\frac3{10}x=\frac1{10}, \qquad x=\frac13.$$

相對地，

$$y=1-x=\frac23.$$

若初始狀態為

這題是關於圖論的基本概念，包括圖的繪製、樹、歐拉圖和哈密頓圖的判定。

給定的鄰接矩陣 A 是 $5 \times 5$ 的，表示一個有 5 個頂點的圖。我們將頂點標記為 $v_1, v_2, v_3, v_4, v_5$。
矩陣 $A_{ij} = 1$ 表示頂點 $v_i$ 和 $v_j$ 之間有邊相連，$A_{ij} = 0$ 表示沒有邊。矩陣是對稱的，且對角線元素為 0，表示這是個無向圖，沒有自環。

部分 (a): 繪製圖 G

我們根據鄰接矩陣來繪製圖。
頂點：$v_1, v_2, v_3, v_4, v_5$。
邊：
$A_{12}=1 \implies (v_1, v_2)$
$A_{13}=1 \implies (v_1, v_3)$
$A_{14}=1 \implies (v_1, v_4)$
$A_{23}=1 \implies (v_2, v_3)$
$A_{25}=1 \implies (v_2, v_5)$
$A_{35}=1 \implies (v_3, v_5)$
$A_{45}=1 \implies (v_4, v_5)$

繪製圖：
頂點 $v_1$ 連接到 $v_2, v_3, v_4$。
頂點 $v_2$ 連接到 $v_1, v_3, v_5$。
頂點 $v_3$ 連接到 $v_1, v_2, v_5$。
頂點 $v_4$ 連接到 $v_1, v_5$。
頂點 $v_5$ 連接到 $v_2, v_3, v_4$。

一個可能的繪製方式（通常將頂點盡量均勻分佈）：
將 $v_1, v_2, v_3, v_4, v_5$ 放置在一個圓上。
$v_1$ 連接 $v_2, v_3, v_4$。
$v_2$ 連接 $v_1, v_3, v_5$。
$v_3$ 連接 $v_1, v_2, v_5$。
$v_4$ 連接 $v_1, v_5$。
$v_5$ 連接 $v_2, v_3, v_4$。

【答案】(a) 繪製一個有 5 個頂點的圖，頂點間的連接關係如上所述。

部分 (b): 判斷是否為樹

一個圖是樹的條件是：

1. 它是一個連通圖 (connected graph)。
2. 它沒有環 (cycle)。
   對於一個有 $n$ 個頂點的圖，如果它是樹，則它恰好有 $n-1$ 條邊。

頂點數 $n=5$。
計算邊數：
從鄰接矩陣的非對角線元素總和除以 2。
非對角線元素總和：
(1+1+1) + (1+1) + (1+1) + (1) + (1+1+1) = 3+2+2+1+3 = 11
總和是 11。
邊數 = $11 / 2 = 5.5$。這不對。
我們應該計算矩陣中 1 的個數，然後除以 2。
矩陣中 1 的個數是：3 (第一行) + 3 (第二行) + 3 (第三行) + 2 (第四行) + 3 (第五行) = 14。
邊數 = $14 / 2 = 7$。

邊數 $m=7$。
頂點數 $n=5$。
對於樹，邊數應為 $n-1 = 5-1 = 4$。
由於邊數是 7，大於 4，所以這個圖不是樹。
此外，我們可以觀察到圖中存在環。