108 年 國立臺北大學資訊工程研究所《線性代數與離散數學》

核心觀念

本題屬於離散數學（Discrete Mathematics）中的**組合計數（Combinatorics）**範疇，主要考驗以下三大核心概念：

1. 乘法原理（Rule of Product）：當一個完成事件可分解為若干獨立的連續步驟時，總方法數為各步驟選擇數之連乘積。對於長度為 $7$ 的字串（由 $26$ 個英文大寫字母組成，允許重複），若各位置的選擇數分別為 $n_1, n_2, \dots, n_7$，則總字串數為 $\prod_{i=1}^{7} n_i$。
2. 取捨原理／排容原理（Principle of Inclusion-Exclusion, PIE）：用於計算多個集合聯集之元素個數。雙集合形式為：
   $|A \cup B| = |A| + |B| - |A \cap B|$
3. 餘集法／反向計數（Complementary Counting）：利用全集 $U$ 扣除不符合條件的補集 $A^c$，即 $|A| = |U| - |A^c|$。對於包含邏輯「或（OR）」的多條件問題，轉化為補集邏輯「非 A 且 非 B」往往能大幅簡化計算。

---

解題方法

本題字串長度固定為 $7$，字母表大小 $|\Sigma| = 26$，全集總字串數為 $|U| = 26^7$。各小題之解題切入點如下：

• (a) 子題切入點：指定第 $1$ 個位置必為 R、第 $7$ 個位置必為 T。中間第 $2$ 至第 $6$ 個位置（共 $5$ 個位置）完全無限制，直接套用乘法原理計算。
• (b) 子題切入點：要求「開頭為 A」或「結尾為 B」。設 $E_1$ 為開頭為 A 的字串集合，$E_2$ 為結尾為 B 的字串集合。求 $|E_1 \cup E_2|$。可用取捨原理正向計算，亦可用餘集法拿全集扣除「開頭非 A 且結尾非 B」之字串數。
• (c) 子題切入點：要求「開頭為 A 或 R」或「結尾為 T 或 B」。開頭可選字母有 $2$ 種（A 或 R），結尾可選字母有 $2$ 種（T 或 B）。利用餘集法計算「開頭非 A 且非 R」且「結尾非 T 且非 B」之補集個數，再由全集扣除，可最快速求得答案。

---

選項分析（各子題詳細推導與分析）

(a) How many words begin with R and end with T?

• 推導過程：
  將長度為 $7$ 的字串位置記為 $(L_1, L_2, L_3, L_4, L_5, L_6, L_7)$。

  • $L_1$ 固定為 'R'：只有 $1$ 種選擇。
  • $L_7$ 固定為 'T'：只有 $1$ 種選擇。
  • $L_2, L_3, L_4, L_5, L_6$ 無任何限制：每個位置皆可從 $26$ 個字母中任意選擇，各有 $26$ 種選擇。
    由乘法原理，符合條件的字串總數為：
    $N_a = 1 \times 26 \times 26 \times 26 \times 26 \times 26 \times 1 = 26^5$
    計算數值為：
    $26^5 = 11,881,376$

• 【答案】：$26^5$ （或 $11,881,376$）

---

(b) How many words begin with A or end with B?

• 推導過程：
  全集 $U$ 之總字串數為 $|U| = 26^7$。
  定義集合：

  • $E_1$：開頭為 'A' 的字串集合。
  • $E_2$：結尾為 'B' 的字串集合。

  方法一：取捨原理（PIE）

  1. $E_1$ 的元素個數：$L_1$ 固定為 'A'（$1$ 種），其餘 $6$ 個位置自由選擇，故 $|E_1| = 1 \times 26^6 = 26^6$。
  2. $E_2$ 的元素個數：$L_7$ 固定為 'B'（$1$ 種），其餘 $6$ 個位置自由選擇，故 $|E_2| = 1 \times 26^6 = 26^6$。
  3. 交集 $E_1 \cap E_2$ 的元素個數（即同時開頭為 'A' 且結尾為 'B'）：$L_1$ 固定為 'A'，$L_7$ 固定為 'B'，中間 $5$ 個位置自由選擇，故 $|E_1 \cap E_2| = 1 \times 26^5 \times 1 = 26^5$。
     代入取捨原理公式：
     $|E_1 \cup E_2| = |E_1| + |E_2| - |E_1 \cap E_2| = 26^6 + 26^6 - 26^5 = 2 \times 26^6 - 26^5$
     提出公因數 $26^5$：
     $|E_1 \cup E_2| = 26^5 \times (2 \times 26 - 1) = 51 \times 26^5$
     計算數值為：
     $51 \times 11,881,376 = 605,950,176$

核心觀念

本題的圖形是正十二面體的骨架圖，可視為一個具有 20 個頂點、每個頂點度數皆為 3 的立方圖。

使用的判定定理如下：

1. 平面圖：若圖可以在平面上繪出，使任兩條邊只在共同端點相交，則為平面圖。
2. Euler circuit：連通圖具有 Euler circuit 的充要條件是所有頂點的度數皆為偶數。
3. Euler path：連通圖具有 Euler path 的充要條件是奇度數頂點恰有 0 個或 2 個。
4. Hamilton circuit：經過每個頂點恰好一次並回到起點的迴路。
5. Hamilton path：經過每個頂點恰好一次的路徑，不要求回到起點。

---

1. 是否為平面圖？

是平面圖。

題目附圖本身就是正十二面體骨架的一個平面嵌入圖。圖中各面可視為五邊形，所有邊只在共同端點相交，沒有任何兩條非鄰接邊交叉。

因此，該圖是平面圖。

---

2. 是否具有 Euler circuit？

沒有 Euler circuit。

圖是連通圖，且每個頂點的度數皆為

$$\deg(v)=3.$$

因此 20 個頂點全部都是奇度數頂點。Euler circuit 要求每個頂點的度數皆為偶數，所以不符合條件。

故：

$$\boxed{\text{沒有 Euler circuit}}$$

---

3. 是否具有 Euler path？

沒有 Euler path。

Euler path 存在的條件是奇度數頂點數量必須為 0 或 2 個。

本圖有 20 個頂點，而且每個頂點度數都是 3，因此奇度數頂點共有 20 個：

$$\#\{\text{奇度數頂點}\}=20.$$

因為 $20\neq 0,2$，所以不存在 Euler path。

故：

$$\boxed{\text{沒有 Euler path}}$$

---

4. 是否具有 Hamilton circuit？

有 Hamilton circuit。

將此正十二面體圖重新標記為廣義 Petersen 圖 $G(10,2)$：

• 外圈頂點為 $u_0,u_1,\ldots,u_9$；
• 內部頂點為 $v_0,v_1,\ldots,v_9$；
• 外圈邊為 $u_i u_{i+1}$；
• 連接邊為 $u_i v_i$；
• 內部邊為 $v_i v_{i+2}$，下標以 10 為模數計算。

其中一條經過全部 20 個頂點的 Hamilton circuit 為

原式：

$$f=\neg x\vee(x\wedge y\wedge z\wedge\neg w) \vee(\neg x\wedge y\wedge\neg z\wedge w)$$

利用吸收律：

$$\neg x\vee(\neg x\wedge y\wedge\neg z\wedge w)=\neg x$$

再由 $\neg x\vee(x\wedge A)=\neg x\vee A$：

$$\boxed{f=\neg x\vee(y\wedge z\wedge\neg w)}$$

真值表如下：

$x$	$y$	$z$	$w$	$f$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

簡化後的組合電路：

核心觀念

本題旨在考驗對**向量空間（Vector Space）**定義的理解與嚴格驗證能力。
一個非空集合 $V$ 搭配體 $F$（在此為實數體 $\mathbb{R}$）、向量加法 $+: V \times V \to V$ 以及純量乘法 $\cdot: F \times V \to V$，若要構成實數體上的向量空間，必須完整滿足 10 項公理（Axioms）（包含 2 項封閉性公理與 8 項代數公理）。

---

解題方法

設向量集合 $V = \mathbb{R}$，純量體 $F = \mathbb{R}$。對於任意 $u, v, w \in V$ 以及任意純量 $c, d \in F$，採用實數系傳統的加法與乘法性質，逐一驗證以下 10 項向量空間公理：

1. 向量加法封閉性（Closure under Addition）

若 $u, v \in \mathbb{R}$，依據實數加法之封閉性，兩實數相加仍為實數，故：
$u + v \in \mathbb{R}$

2. 向量加法交換律（Commutativity of Addition）

依據實數加法交換律，對任意 $u, v \in \mathbb{R}$，恆有：
$u + v = v + u$

3. 向量加法結合律（Associativity of Addition）

依據實數加法結合律，對任意 $u, v, w \in \mathbb{R}$，恆有：
$(u + v) + w = u + (v + w)$

4. 加法單位元的存在性（Existence of Additive Identity）

實數集中存在元素 $0 \in \mathbb{R}$，使得對任意 $u \in \mathbb{R}$，恆滿足：
$u + 0 = u$
此元素 $0$ 即為加法零向量 $\mathbf{0}$。

5. 加法反元素的存在性（Existence of Additive Inverse）

對任意元素 $u \in \mathbb{R}$，皆存在實數 $-u \in \mathbb{R}$，使得：
$u + (-u) = 0$
此元素 $-u$ 即為 $u$ 之加法反元素（Additive Inverse）。

6. 純量乘法封閉性（Closure under Scalar Multiplication）

若純量 $c \in \mathbb{R}$ 且向量 $u \in \mathbb{R}$，依據實數乘法之封閉性，兩實數相乘仍為實數，故：
$c \cdot u \in \mathbb{R}$

7. 純量乘法對向量加法之分配律（Distributivity over Vector Addition）

依據實數乘法對加法之分配律，對任意純量 $c \in \mathbb{R}$ 及向量 $u, v \in \mathbb{R}$，恆有：
$c \cdot (u + v) = c \cdot u + c \cdot v$

核心觀念

本題考查：

1. 線性轉換的定義：
   $L(\mathbf{x}+\mathbf{y})=L(\mathbf{x})+L(\mathbf{y})$
   $L(c\mathbf{x})=cL(\mathbf{x})$

2. 線性轉換的矩陣表示法。

3. 核心（kernel）的定義：
   $\ker L=\{\mathbf{x}\in\mathbb{R}^3:L(\mathbf{x})=\mathbf{0}\}$

---

解題方法

將向量 $\mathbf{x}=(x_1,x_2,x_3)^T$ 寫成矩陣乘法：

$$L(\mathbf{x}) = \begin{pmatrix} x_1+2x_2\\ 3x_2+x_3 \end{pmatrix} = \begin{pmatrix} 1&2&0\\ 0&3&1 \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}.$$

因此，$L$ 可表示為矩陣

$$A= \begin{pmatrix} 1&2&0\\ 0&3&1 \end{pmatrix}$$

所代表的矩陣轉換，即

$$L(\mathbf{x})=A\mathbf{x}.$$

任何矩陣乘法所定義的映射皆為線性轉換，因此 $L$ 是線性轉換。

也可直接驗證。設 $\mathbf{x},\mathbf{y}\in\mathbb{R}^3$，以及 $c\in\mathbb{R}$，則

$$L(\mathbf{x}+\mathbf{y}) = A(\mathbf{x}+\mathbf{y}) = A\mathbf{x}+A\mathbf{y} = L(\mathbf{x})+L(\mathbf{y}),$$

且

$$L(c\mathbf{x}) = A(c\mathbf{x}) = cA\mathbf{x} = cL(\mathbf{x}).$$

所以 $L$ 符合線性轉換的兩項條件。

---

核心 $\ker L$ 的求法

根據定義，需找出所有滿足

$$L(\mathbf{x})= \begin{pmatrix} 0\\ 0 \end{pmatrix}$$

的向量 $\mathbf{x}$。因此解聯立方程式：

$$\begin{cases} x_1+2x_2=0,\\ 3x_2+x_3=0. \end{cases}$$

由第一式得

$$x_1=-2x_2,$$

核心觀念

本題考查：

• 特徵值與特徵向量的定義：
  $Av=\lambda v,\qquad v\ne 0$
• 特徵多項式：
  $\det(\lambda I-A)=0$
• 可對角化條件：若矩陣有 $3$ 個線性獨立的特徵向量，則可寫成
  $A=PDP^{-1}$
• 利用相似對角化計算矩陣高次方：
  $A^5=PD^5P^{-1}$
• 也可利用 Cayley–Hamilton 定理化簡 $A^5$。

---

解題方法

令

$$A= \begin{pmatrix} 3&-1&-2\\ 2&0&-2\\ -2&-1&-1 \end{pmatrix}.$$

先求特徵多項式，再求各特徵值對應的特徵向量。由於三個特徵值相異，因此矩陣必可對角化。計算 $A^5$ 時，採用 Cayley–Hamilton 定理可避免直接計算 $P^{-1}$。

---

（a）求特徵值與特徵向量

求特徵多項式

計算

$$\det(\lambda I-A) = \det \begin{pmatrix} \lambda-3&1&2\\ -2&\lambda&2\\ 2&1&\lambda+1 \end{pmatrix}.$$

展開可得

$$\det(\lambda I-A) = \lambda^3-2\lambda^2-7\lambda+8.$$

因式分解：

$$\lambda^3-2\lambda^2-7\lambda+8 = (\lambda-1)(\lambda^2-\lambda-8).$$

因此特徵值為

$$\boxed{\lambda_1=1,\qquad \lambda_2=\frac{1+\sqrt{33}}{2},\qquad \lambda_3=\frac{1-\sqrt{33}}{2}}.$$

---

特徵值 $\lambda=1$

解

$$(A-I)v=0.$$

其中

$$A-I= \begin{pmatrix} 2&-1&-2\\ 2&-1&-2\\ -2&-1&-2 \end{pmatrix}.$$

設 $v=(x,y,z)^T$，則

$$2x-y-2z=0,$$ $$-2x-y-2z=0.$$

兩式相減得

$$4x=0\quad\Longrightarrow\quad x=0.$$

代回可得

$$y=-2z.$$

取 $z=1$，得到特徵向量

$$\boxed{v_1= \begin{pmatrix} 0\\-2\\1 \end{pmatrix}}.$$

---

特徵值 $\lambda\ne 1$

解

$$(A-\lambda I) \begin{pmatrix} x\\y\\z \end{pmatrix} =0.$$

由前兩列方程式：

$$(3-\lambda)x-y-2z=0,$$ $$2x-\lambda y-2z=0.$$

第一式給出

$$y=(3-\lambda)x-2z.$$

代入第二式：

$$2x-\lambda\bigl((3-\lambda)x-2z\bigr)-2z=0,$$

整理為

$$(\lambda-1)\bigl((\lambda-2)x+2z\bigr)=0.$$

因為 $\lambda\ne1$，所以

$$(\lambda-2)x+2z=0,$$

即

$$z=\frac{2-\lambda}{2}x.$$

取 $x=2$，則

$$z=2-\lambda, \qquad y=2.$$

因此對任意 $\lambda=\lambda_2,\lambda_3$，可取特徵向量

$$v(\lambda)= \begin{pmatrix} 2\\2\\2-\lambda \end{pmatrix}.$$

所以

$$\boxed{ v_2= \begin{pmatrix} 2\\ 2\\ \dfrac{3-\sqrt{33}}{2} \end{pmatrix}}$$

對應於

$$\lambda_2=\frac{1+\sqrt{33}}{2},$$

以及

$$\boxed{ v_3= \begin{pmatrix} 2\\ 2\\ \dfrac{3+\sqrt{33}}{2} \end{pmatrix}}$$

對應於

$$\lambda_3=\frac{1-\sqrt{33}}{2}.$$

為避免分數，也可將後兩個特徵向量分別放大 $2$ 倍：

核心觀念

本題考查：

• 特徵值與特徵向量的定義：
  $Av=\lambda v,\qquad v\ne 0$
• 特徵多項式：
  $\det(\lambda I-A)=0$
• 可對角化條件：若矩陣有 $3$ 個線性獨立的特徵向量，則可寫成
  $A=PDP^{-1}$
• 利用相似對角化計算矩陣高次方：
  $A^5=PD^5P^{-1}$
• 也可利用 Cayley–Hamilton 定理化簡 $A^5$。

---

解題方法

令

$$A= \begin{pmatrix} 3&-1&-2\\ 2&0&-2\\ -2&-1&-1 \end{pmatrix}.$$

先求特徵多項式，再求各特徵值對應的特徵向量。由於三個特徵值相異，因此矩陣必可對角化。計算 $A^5$ 時，採用 Cayley–Hamilton 定理可避免直接計算 $P^{-1}$。

---

（a）求特徵值與特徵向量

求特徵多項式

計算

$$\det(\lambda I-A) = \det \begin{pmatrix} \lambda-3&1&2\\ -2&\lambda&2\\ 2&1&\lambda+1 \end{pmatrix}.$$

展開可得

$$\det(\lambda I-A) = \lambda^3-2\lambda^2-7\lambda+8.$$

因式分解：

$$\lambda^3-2\lambda^2-7\lambda+8 = (\lambda-1)(\lambda^2-\lambda-8).$$

因此特徵值為

$$\boxed{\lambda_1=1,\qquad \lambda_2=\frac{1+\sqrt{33}}{2},\qquad \lambda_3=\frac{1-\sqrt{33}}{2}}.$$

---

特徵值 $\lambda=1$

解

$$(A-I)v=0.$$

其中

$$A-I= \begin{pmatrix} 2&-1&-2\\ 2&-1&-2\\ -2&-1&-2 \end{pmatrix}.$$

設 $v=(x,y,z)^T$，則

$$2x-y-2z=0,$$ $$-2x-y-2z=0.$$

兩式相減得

$$4x=0\quad\Longrightarrow\quad x=0.$$

代回可得

$$y=-2z.$$

取 $z=1$，得到特徵向量

$$\boxed{v_1= \begin{pmatrix} 0\\-2\\1 \end{pmatrix}}.$$

---

特徵值 $\lambda\ne 1$

解

$$(A-\lambda I) \begin{pmatrix} x\\y\\z \end{pmatrix} =0.$$

由前兩列方程式：

$$(3-\lambda)x-y-2z=0,$$ $$2x-\lambda y-2z=0.$$

第一式給出

$$y=(3-\lambda)x-2z.$$

代入第二式：

$$2x-\lambda\bigl((3-\lambda)x-2z\bigr)-2z=0,$$

整理為

$$(\lambda-1)\bigl((\lambda-2)x+2z\bigr)=0.$$

因為 $\lambda\ne1$，所以

$$(\lambda-2)x+2z=0,$$

即

$$z=\frac{2-\lambda}{2}x.$$

取 $x=2$，則

$$z=2-\lambda, \qquad y=2.$$

因此對任意 $\lambda=\lambda_2,\lambda_3$，可取特徵向量

$$v(\lambda)= \begin{pmatrix} 2\\2\\2-\lambda \end{pmatrix}.$$

所以

$$\boxed{ v_2= \begin{pmatrix} 2\\ 2\\ \dfrac{3-\sqrt{33}}{2} \end{pmatrix}}$$

對應於

$$\lambda_2=\frac{1+\sqrt{33}}{2},$$

以及

$$\boxed{ v_3= \begin{pmatrix} 2\\ 2\\ \dfrac{3+\sqrt{33}}{2} \end{pmatrix}}$$

對應於

$$\lambda_3=\frac{1-\sqrt{33}}{2}.$$

為避免分數，也可將後兩個特徵向量分別放大 $2$ 倍：