111 年 國立中正大學資訊工程學系碩士班甲組《數學》

本題考查向量的分量與正交分量。給定向量 $u$ 和 $a$，我們需要找到 $u$ 在 $a$ 方向上的投影向量（向量分量）以及垂直於 $a$ 的分量。

核心概念：
向量 $u$ 在向量 $a$ 上的投影向量（component of $u$ along $a$）為 $\text{proj}_a u = \frac{u \cdot a}{\|a\|^2} a$。
向量 $u$ 垂直於 $a$ 的分量（component of $u$ orthogonal to $a$）為 $u - \text{proj}_a u$。

解題步驟：

1. 計算內積 $u \cdot a$。
2. 計算向量 $a$ 的模長平方 $\|a\|^2$。
3. 計算向量分量 $\text{proj}_a u$。
4. 計算正交分量 $u - \text{proj}_a u$。

計算過程：
給定 $u = (2, 0, 1)$ 和 $a = (1, 2, 3)$。

1. 計算內積 $u \cdot a$:
   $u \cdot a = (2)(1) + (0)(2) + (1)(3) = 2 + 0 + 3 = 5$。

2. 計算向量 $a$ 的模長平方 $\|a\|^2$:
   $\|a\|^2 = 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14$。

3. 計算向量分量（$u$ 沿 $a$ 的分量）:
   $\text{proj}_a u = \frac{u \cdot a}{\|a\|^2} a = \frac{5}{14} (1, 2, 3) = \left(\frac{5}{14}, \frac{10}{14}, \frac{15}{14}\right) = \left(\frac{5}{14}, \frac{5}{7}, \frac{15}{14}\right)$。

本題考查向量的正交性，要求找出一個同時與兩個已知向量正交的向量。

核心概念：
兩個向量 $a$ 和 $b$ 的叉積（cross product）$a \times b$ 會得到一個同時垂直於 $a$ 和 $b$ 的向量。
對於三維向量 $u = (u_1, u_2, u_3)$ 和 $v = (v_1, v_2, v_3)$，其叉積為：
$u \times v = (u_2v_3 - u_3v_2, u_3v_1 - u_1v_3, u_1v_2 - u_2v_1)$。

解題步驟：

1. 直接計算給定向量 $u$ 和 $v$ 的叉積 $u \times v$。
2. 驗證所得向量是否同時與 $u$ 和 $v$ 正交（內積為 0）。

計算過程：
給定 $u = (0, 2, -2)$ 和 $v = (1, 3, 0)$。

計算叉積 $u \times v$:
$u \times v = ( (2)(0) - (-2)(3), (-2)(1) - (0)(0), (0)(3) - (2)(1) )$

本題考查向量在給定基底下的坐標表示。

核心概念：
給定一個向量空間中的向量 $v$ 和一個基底 $S = \{b_1, b_2, \dots, b_n\}$，向量 $v$ 在基底 $S$ 下的坐標向量 $c = (c_1, c_2, \dots, c_n)$ 滿足 $v = c_1 b_1 + c_2 b_2 + \dots + c_n b_n$。
這可以寫成一個線性方程組的形式：$v = B c$，其中 $B$ 是以基底向量為行（或列）的矩陣，而 $c$ 是待求的坐標向量。

解題步驟：

1. 將基底向量寫成矩陣 $B$ 的列向量（或行向量）。
2. 將待求坐標向量設為 $c = (c_1, c_2, c_3)$。
3. 建立線性方程組 $v = c_1 b_1 + c_2 b_2 + c_3 b_3$。
4. 解這個線性方程組，求出 $c_1, c_2, c_3$。

計算過程：
給定向量 $v = (3, 4, 3)$，基底 $S = \{b_1, b_2, b_3\}$，其中 $b_1 = (3, 2, 1)$, $b_2 = (-2, 1, 0)$, $b_3 = (5, 0, 0)$。
我們要找 $c_1, c_2, c_3$ 使得 $v = c_1 b_1 + c_2 b_2 + c_3 b_3$。
$(3, 4, 3) = c_1(3, 2, 1) + c_2(-2, 1, 0) + c_3(5, 0, 0)$
$(3, 4, 3) = (3c_1 - 2c_2 + 5c_3, 2c_1 + c_2, c_1)$

由此可得一個線性方程組：

1. $c_1 = 3$
2. $2c_1 + c_2 = 4$
3. $3c_1 - 2c_2 + 5c_3 = 3$

從第一個方程，我們直接得到 $c_1 = 3$。
將 $c_1 = 3$ 代入第二個方程：
$2(3) + c_2 = 4 \Rightarrow 6 + c_2 = 4 \Rightarrow c_2 = 4 - 6 = -2$。

將 $c_1 = 3$ 和 $c_2 = -2$ 代入第三個方程：
$3(3) - 2(-2) + 5c_3 = 3$
$9 + 4 + 5c_3 = 3$
$13 + 5c_3 = 3$
$5c_3 = 3 - 13$
$5c_3 = -10$
$c_3 = -2$。

所以，坐標向量 $c = (c_1, c_2, c_3) = (3, -2, -2)$。

另一種方法：矩陣表示
我們可以將基底向量寫成矩陣 $B$ 的行向量，然後解 $c^T B^T = v^T$（或者將基底向量寫成列向量，解 $B c = v$）。
令 $B = \begin{pmatrix} 3 & 2 & 1 \\ -2 & 1 & 0 \\ 5 & 0 & 0 \end{pmatrix}$。我們要解 $B^T c = v^T$。

核心觀念

本題考查矩陣乘冪。由於 $A$ 是下三角矩陣，且非零元素只出現在第一欄，因此可利用矩陣乘法的遞迴形式，直接求出 $A^n$ 的一般表示式，再代入 $n=13$。

設

$$A^n= \begin{bmatrix} 1&0&0\\ b_n&1&0\\ c_n&0&3^n \end{bmatrix}.$$

對角線元素來自下三角矩陣的乘冪，因此分別為 $1,1,3^n$。

解題方法

計算 $A^{n+1}=A^nA$：

$$A^{n+1} = \begin{bmatrix} 1&0&0\\ b_n&1&0\\ c_n&0&3^n \end{bmatrix} \begin{bmatrix} 1&0&0\\ -2&1&0\\ 1&0&3 \end{bmatrix}.$$

逐項計算可得

$$A^{n+1} = \begin{bmatrix} 1&0&0\\ b_n-2&1&0\\ c_n+3^n&0&3^{n+1} \end{bmatrix}.$$

因此 $b_n,c_n$ 滿足遞迴關係

$$b_{n+1}=b_n-2,\qquad b_1=-2,$$

以及

$$c_{n+1}=c_n+3^n,\qquad c_1=1.$$

由第一個遞迴式：

$$b_n=-2n.$$

由第二個遞迴式：

$$c_n=1+3+3^2+\cdots+3^{n-1}.$$

這是等比級數，因此

本題考查 Gram-Schmidt 正交化過程，將一個向量空間中的標準基底轉換為正交基底。

核心概念：
Gram-Schmidt 正交化過程是一個算法，用於將一個向量空間中的一組線性獨立向量轉換為一組正交向量。
對於一組線性獨立向量 $\{v_1, v_2, \dots, v_n\}$，其正交化過程如下：
$u_1 = v_1$
$u_2 = v_2 - \text{proj}_{u_1} v_2 = v_2 - \frac{\langle v_2, u_1 \rangle}{\langle u_1, u_1 \rangle} u_1$
$u_3 = v_3 - \text{proj}_{u_1} v_3 - \text{proj}_{u_2} v_3 = v_3 - \frac{\langle v_3, u_1 \rangle}{\langle u_1, u_1 \rangle} u_1 - \frac{\langle v_3, u_2 \rangle}{\langle u_2, u_2 \rangle} u_2$
...
$u_k = v_k - \sum_{j=1}^{k-1} \text{proj}_{u_j} v_k = v_k - \sum_{j=1}^{k-1} \frac{\langle v_k, u_j \rangle}{\langle u_j, u_j \rangle} u_j$

給定的向量空間是 $P_2$，即次數小於等於 2 的多項式空間。
標準基底是 $v_1(x) = 1$, $v_2(x) = x$, $v_3(x) = x^2$。
內積定義為 $\langle p, q \rangle = \int_{-1}^{1} p(x)q(x)dx$。

解題步驟：

1. 初始化 $u_1 = v_1(x)$。
2. 計算 $u_2$ 使用 $v_2(x)$ 和 $u_1$。
3. 計算 $u_3$ 使用 $v_3(x)$、$u_1$ 和 $u_2$。
4. 將得到的 $u_1, u_2, u_3$ 作為正交基底 $\{\phi_1(x), \phi_2(x), \phi_3(x)\}$。

計算所需的積分：
首先，我們需要計算一些基本的多項式積分：
$\int_{-1}^{1} c \, dx = c[x]_{-1}^1 = c(1 - (-1)) = 2c$ (常數)
$\int_{-1}^{1} x^n \, dx$:
如果 $n$ 是奇數，積分結果為 0。
如果 $n$ 是偶數， $\int_{-1}^{1} x^n \, dx = [\frac{x^{n+1}}{n+1}]_{-1}^1 = \frac{1^{n+1}}{n+1} - \frac{(-1)^{n+1}}{n+1} = \frac{1 - (-1)}{n+1} = \frac{2}{n+1}$。

計算 $\langle u_i, u_i \rangle$ 和 $\langle v_k, u_j \rangle$：

步驟 1: 計算 $u_1(x)$
$v_1(x) = 1$
$u_1(x) = v_1(x) = 1$。

步驟 2: 計算 $u_2(x)$
$v_2(x) = x$
$u_2(x) = v_2(x) - \frac{\langle v_2, u_1 \rangle}{\langle u_1, u_1 \rangle} u_1(x)$

計算內積：
$\langle v_2, u_1 \rangle = \langle x, 1 \rangle = \int_{-1}^{1} x \cdot 1 \, dx = \int_{-1}^{1} x \, dx = 0$ (因為 $x$ 是奇函數)

本題要求使用兩種不同的證明方法（逆否證法和反證法）來證明一個關於整數奇偶性的命題。

命題：若 $n$ 是整數且 $n^3 + 5$ 是奇數，則 $n$ 是偶數。
形式化表示：$P \implies Q$，其中 $P$ 是 "$n$ 是整數且 $n^3 + 5$ 是奇數"，$Q$ 是 "$n$ 是偶數"。

a) 逆否證法 (Proof by Contraposition)
核心概念：
逆否證法證明 $P \implies Q$ 的方法是證明其逆否命題 $\neg Q \implies \neg P$ 為真。
逆否命題：若 $n$ 不是偶數（即 $n$ 是奇數），則 $n^3 + 5$ 不是奇數（即 $n^3 + 5$ 是偶數）。

證明步驟：

1. 假設 $\neg Q$ 為真，即假設 $n$ 是奇數。
2. 推導出 $\neg P$ 為真，即證明 $n^3 + 5$ 是偶數。

證明過程：
假設 $n$ 是奇數。
那麼 $n$ 可以表示為 $n = 2k + 1$，其中 $k$ 是整數。
計算 $n^3 + 5$:
$n^3 + 5 = (2k + 1)^3 + 5$
$n^3 + 5 = ((2k)^3 + 3(2k)^2(1) + 3(2k)(1)^2 + 1^3) + 5$
$n^3 + 5 = (8k^3 + 12k^2 + 6k + 1) + 5$
$n^3 + 5 = 8k^3 + 12k^2 + 6k + 6$
$n^3 + 5 = 2(4k^3 + 6k^2 + 3k + 3)$
令 $m = 4k^3 + 6k^2 + 3k + 3$。由於 $k$ 是整數，所以 $m$ 也是整數。
因此，$n^3 + 5 = 2m$，這表示 $n^3 + 5$ 是偶數。
我們成功證明了：如果 $n$ 是奇數，則 $n^3 + 5$ 是偶數。
這就是原命題的逆否命題。
因此，原命題 "若 $n$ 是整數且 $n^3 + 5$ 是奇數，則 $n$ 是偶數" 為真。

[答案 - a)]
假設 $n$ 是奇數，則 $n = 2k+1$ 對某個整數 $k$。
$n^3 + 5 = (2k+1)^3 + 5 = (8k^3 + 12k^2 + 6k + 1) + 5 = 8k^3 + 12k^2 + 6k + 6 = 2(4k^3 + 6k^2 + 3k + 3)$。
因為 $4k^3 + 6k^2 + 3k + 3$ 是整數，所以 $n^3 + 5$ 是偶數。
逆否命題成立，故原命題成立。

核心觀念

圖的 incidence matrix 中：

• 每一列代表一個頂點；
• 每一欄代表一條邊；
• 某欄在第 $i$、$j$ 列同時為 $1$，表示該邊連接頂點 $v_i$ 與 $v_j$；
• 圖同構必須保留頂點的鄰接關係，因此也保留：
  • 連通分支數；
  • 頂點度數；
  • 是否含有迴圈等結構。

矩陣的列、欄排列順序可以改變，但不能改變圖本身的結構。

解題方法：由矩陣還原圖形

$G_1$ 的邊

依照各欄讀取：

$e_1=(v_1,v_2)$

$e_2=(v_2,v_3)$

$e_3=(v_3,v_4)$

第 $4$ 欄只有第 $5$ 列為 $1$。依本題矩陣的表示方式，這表示位於 $v_5$ 的迴圈，記為

$e_4=(v_5,v_5)$

其餘邊為

$$e_5=(v_5,v_6),\qquad e_6=(v_6,v_7),\qquad e_7=(v_7,v_8)$$

因此，$G_1$ 的結構是：

• 一個由 $v_1,v_2,v_3,v_4$ 組成的路徑；
• 另一個由 $v_5,v_6,v_7,v_8$ 組成的路徑；
• 並且 $v_5$ 上有一個迴圈。

所以 $G_1$ 至少分成兩個連通分支：

$$\{v_1,v_2,v_3,v_4\},\qquad \{v_5,v_6,v_7,v_8\}$$

其中迴圈不會把兩個分支連接起來。

$G_2$ 的邊

由 $G_2$ 的各欄可得：

$$e_1=(v_1,v_2),\quad e_2=(v_2,v_3),\quad e_3=(v_3,v_4),\quad e_4=(v_4,v_5)$$

核心觀念

集合可數，表示它的元素能與正整數建立一一對應；若能將元素列成一個序列，使每個元素都在序列中出現，便可證明此集合至多可數。正有理數可寫成互質正整數之比，適合依分子與分母的和逐層排列。

解題方法

圖中第 8 題的內容是：「證明正有理數集合可數。」任一正有理數都能唯一寫成既約分數 $\frac{m}{n}$，其中 $m,n$ 為正整數且 $\gcd(m,n)=1$。

依照 $m+n$ 的大小排列這些既約分數。固定 $k=m+n$ 時，只需列出符合條件的有限個分數：

$$\frac{1}{k-1},\ \frac{2}{k-2},\ \ldots,\ \frac{k-1}{1}, \qquad \gcd(m,k-m)=1.$$

例如依序排列前幾層：

本題考查線性常係數非齊次遞迴關係式的求解。

核心概念：
對於線性常係數非齊次遞迴關係式 $a_n = c_1 a_{n-1} + \dots + c_k a_{n-k} + f(n)$，其一般解可以表示為：
$a_n = a_n^{(h)} + a_n^{(p)}$
其中 $a_n^{(h)}$ 是對應齊次遞迴關係式的通解（homogeneous solution），$a_n^{(p)}$ 是非齊次遞迴關係式的一個特解（particular solution）。

a) 齊次遞迴關係式 (Homogeneous Recurrence Relation)
將非齊次項 $f(n)$ 設為 0，即可得到對應的齊次遞迴關係式。

b) 齊次遞迴關係式的通解
對於齊次遞迴關係式 $a_n = c_1 a_{n-1} + \dots + c_k a_{n-k}$，其特徵方程（characteristic equation）為 $r^k - c_1 r^{k-1} - \dots - c_k = 0$。
根據特徵方程的根（特徵值），可以得到齊次解的形式。

• 如果特徵值 $r_i$ 互不相同，則 $a_n^{(h)} = A_1 r_1^n + \dots + A_k r_k^n$。
• 如果特徵值 $r_i$ 有重根 $r$ (重數為 $m$)，則對應項為 $(A_1 + A_2 n + \dots + A_m n^{m-1}) r^n$。

c) 非齊次遞迴關係式的特解
對於非齊次項 $f(n)$，可以根據其形式猜測特解的形式。

• 如果 $f(n)$ 是多項式（degree $d$），則猜測特解為一個 $d$ 次多項式。
• 如果 $f(n)$ 是指數形式 $C \cdot s^n$，則猜測特解為 $A \cdot s^n$。
• 如果 $f(n)$ 是三角函數形式，則猜測為對應的三角函數。
• 重要注意事項：如果猜測的特解形式與齊次解中的某項形式相同（或成比例），則需要在猜測的形式上乘以 $n$ （或 $n^m$，其中 $m$ 是重數），直到與齊次解的每一項都不同。

d) 非齊次遞迴關係式的通解
將齊次通解 $a_n^{(h)}$ 和特解 $a_n^{(p)}$ 相加得到。

e) 帶初始條件的特解
利用給定的初始條件（如 $a_0=1$），代入通解，解出其中的常數（如 $A_1, A_2, \dots$），從而得到特定解。

計算過程：
給定的遞迴關係式為 $a_n = 2a_{n-1} + 3n$。

a) 齊次遞迴關係式
將 $3n$ 設為 0：
$a_n^{(h)} = 2a_{n-1}^{(h)}$。

核心觀念

• 樹（tree）：連通且不含 cycle 的無向圖。若有 $n$ 個頂點，必有 $n-1$ 條邊。
• 非同構（non-isomorphic）：兩棵樹無法透過重新命名頂點，使其邊的連接關係完全一致。
• 判斷樹是否可能同構時，可先比較：
  • 頂點度數序列；
  • 葉節點數量；
  • 最大度數；
  • 路徑長度與分枝結構。
• 有根樹（rooted tree）：在樹中指定一個頂點作為根。根的位置也是結構的一部分，因此即使底層無根樹同構，根的位置不同，也可能形成不同的有根樹。

---

a) 所有具有 5 個頂點的非同構樹

5 個頂點的樹共有 $5-1=4$ 條邊。依照頂點度數分配分類。

度數總和必須為

$$2|E|=2(4)=8.$$

符合樹的結構且彼此非同構者共有 3 種。

1. 路徑樹 $P_5$

度數序列為

$$(2,2,2,1,1).$$

○──○──○──○──○

其中兩端頂點為葉節點，中間三個頂點的度數為 $2$。

---

2. 星狀樹 $K_{1,4}$

度數序列為

$$(4,1,1,1,1).$$

    ○
    │
○───●───○
    │
    ○

中心頂點度數為 $4$，其餘四個頂點都是葉節點。

---

3. 一個三分枝的樹

度數序列為

$$(3,2,1,1,1).$$

    ○
    │
○───●───○
    │
    ○

上圖若將中心頂點的其中一條分支延長一層，可清楚表示度數序列 $(3,2,1,1,1)$：

    ○
    │
○───●───○
    │
    ○

為避免與星狀樹混淆，正確結構應標示為：

      ○
      │
○─────●─────○
      │
      ○
      │
      ○

但此圖共有 6 個頂點，因此需使用 5 個頂點的形式：

    ○
    │
○───●───○
    │
    ○

其中將右側分支視為長度 2 的分支，即可表示為：

      ○
      │
○─────●─────○───○

此圖仍有 5 個頂點，度數為

• 最左端：$1$
• 中心頂點：$3$
• 最右側中間頂點：$2$
• 其餘兩端：$1$

因此其度數序列為

$$(3,2,1,1,1).$$

這三棵樹的度數序列分別為

$$(2,2,2,1,1),\qquad (4,1,1,1,1),\qquad (3,2,1,1,1),$$

彼此皆不同，所以不可能同構。

---

b) 所有具有 4 個頂點的非同構有根樹

先注意：4 個頂點的無根樹只有兩種。

1. 路徑樹 $P_4$；
2. 星狀樹 $K_{1,3}$。

接著分別考慮根可以放在哪些互不同構的位置。

---