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

本題考查行列式的計算。
給定一個 $3 \times 3$ 的矩陣 $A$，我們需要計算其行列式。

$$A = \begin{bmatrix} 0 & 1 & 5 \\ 3 & 6 & 9 \\ 2 & 6 & 1 \end{bmatrix}$$

計算行列式可以使用代數餘子式展開法。我們選擇第一列進行展開：

$$\det(A) = 0 \cdot C_{11} + 1 \cdot C_{12} + 5 \cdot C_{13}$$

其中 $C_{ij} = (-1)^{i+j} M_{ij}$，而 $M_{ij}$ 是除去第 $i$ 行和第 $j$ 列後所形成的子矩陣的行列式。

$C_{11} = (-1)^{1+1} \begin{vmatrix} 6 & 9 \\ 6 & 1 \end{vmatrix} = 1 \cdot (6 \cdot 1 - 9 \cdot 6) = 6 - 54 = -48$

$C_{12} = (-1)^{1+2} \begin{vmatrix} 3 & 9 \\ 2 & 1 \end{vmatrix} = -1 \cdot (3 \cdot 1 - 9 \cdot 2) = -1 \cdot (3 - 18) = -1 \cdot (-15) = 15$

本題考查向量空間的維度計算，主要是找出子空間的一組基底，其向量個數即為維度。

(a) 考慮形式為 $(a, b, c, 0)$ 的向量。
此類向量可以寫成 $a(1, 0, 0, 0) + b(0, 1, 0, 0) + c(0, 0, 1, 0)$。
令 $v_1 = (1, 0, 0, 0)$, $v_2 = (0, 1, 0, 0)$, $v_3 = (0, 0, 1, 0)$。
這三個向量顯然線性獨立，且它們的線性組合可以生成所有形式為 $(a, b, c, 0)$ 的向量。
因此，這三個向量構成該子空間的一組基底。
子空間的維度即為基底向量的個數。
【答案】3

核心觀念

若存在正交矩陣 $P$ 與對角矩陣 $D$，使得

$$A=PDP^T,$$

則因為 $P^T=P^{-1}$，可得

$$A^T=(PDP^T)^T=PDP^T=A.$$

因此，任何能寫成 $A=PDP^T$ 的實矩陣都必須是對稱矩陣。這是實對稱矩陣譜定理的必要條件：實矩陣可被正交對角化，當且僅當它是對稱矩陣。

解題方法

題目給定

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

其轉置為

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

比較 $A$ 與 $A^T$：

$$a_{12}=1,\qquad a_{21}=-1.$$

所以

$$A\neq A^T.$$

矩陣 $A$ 不是對稱矩陣。

若假設存在正交矩陣 $P$ 與對角矩陣 $D$，令

$$A=PDP^T,$$

則必有

本題考查向量空間的正規正交基的建構。給定兩個向量 $v_1, v_2$，我們需要找到一個向量 $v_3$，使得 $v_1, v_2, v_3$ 構成 $R^3$ 的一個標準正交基。

首先，確認給定的向量 $v_1$ 和 $v_2$ 是否已經是單位向量且互相正交。
計算 $v_1$ 的範數：

$$\|v_1\| = \sqrt{(2/3)^2 + (-1/3)^2 + (-2/3)^2} = \sqrt{4/9 + 1/9 + 4/9} = \sqrt{9/9} = \sqrt{1} = 1$$

$v_1$ 是單位向量。

計算 $v_2$ 的範數：

$$\|v_2\| = \sqrt{(-\sqrt{2}/2)^2 + 0^2 + (-\sqrt{2}/2)^2} = \sqrt{2/4 + 0 + 2/4} = \sqrt{4/4} = \sqrt{1} = 1$$

$v_2$ 是單位向量。

計算 $v_1$ 和 $v_2$ 的內積：

$$v_1 \cdot v_2 = (2/3)(-\sqrt{2}/2) + (-1/3)(0) + (-2/3)(-\sqrt{2}/2) = -\sqrt{2}/3 + 0 + \sqrt{2}/3 = 0$$

$v_1$ 和 $v_2$ 是正交的。
因此，$v_1$ 和 $v_2$ 已經構成一個標準正交集。

要構成 $R^3$ 的一個標準正交基，我們需要找到一個向量 $v_3$，它滿足以下條件：

1. $v_3$ 是單位向量，即 $\|v_3\| = 1$。
2. $v_3$ 與 $v_1$ 正交，即 $v_3 \cdot v_1 = 0$。
3. $v_3$ 與 $v_2$ 正交，即 $v_3 \cdot v_2 = 0$。

我們可以通過計算 $v_1$ 和 $v_2$ 的叉積 (cross product) 來找到一個同時與 $v_1$ 和 $v_2$ 正交的向量。

$$v_1 \times v_2 = \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ 2/3 & -1/3 & -2/3 \\ -\sqrt{2}/2 & 0 & -\sqrt{2}/2 \end{vmatrix}$$ $$= \mathbf{i} \left( (-\frac{1}{3})(-\frac{\sqrt{2}}{2}) - (-\frac{2}{3})(0) \right) - \mathbf{j} \left( (\frac{2}{3})(-\frac{\sqrt{2}}{2}) - (-\frac{2}{3})(-\frac{\sqrt{2}}{2}) \right) + \mathbf{k} \left( (\frac{2}{3})(0) - (-\frac{1}{3})(-\frac{\sqrt{2}}{2}) \right)$$ $$= \mathbf{i} \left( \frac{\sqrt{2}}{6} - 0 \right) - \mathbf{j} \left( -\frac{\sqrt{2}}{3} - \frac{\sqrt{2}}{3} \right) + \mathbf{k} \left( 0 - \frac{\sqrt{2}}{6} \right)$$ $$= \frac{\sqrt{2}}{6} \mathbf{i} - \mathbf{j} \left( -\frac{2\sqrt{2}}{3} \right) - \frac{\sqrt{2}}{6} \mathbf{k}$$ $$= \frac{\sqrt{2}}{6} \mathbf{i} + \frac{2\sqrt{2}}{3} \mathbf{j} - \frac{\sqrt{2}}{6} \mathbf{k}$$

所以，一個與 $v_1$ 和 $v_2$ 都正交的向量是 $w = \begin{bmatrix} \sqrt{2}/6 \\ 2\sqrt{2}/3 \\ -\sqrt{2}/6 \end{bmatrix}$。

本題考查特徵值與特徵向量的應用，包括由特徵值與特徵向量求矩陣 $A$、計算矩陣函數的特徵值，以及計算矩陣的冪次。

已知矩陣 $A$ 的特徵值為 $\lambda_1 = 2$ 和 $\lambda_2 = -1$，對應的特徵向量分別為 $v_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ 和 $v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}$。

(a) 求矩陣 $A$。
根據特徵值和特徵向量的定義，我們有：
$Av_1 = \lambda_1 v_1 \implies A \begin{bmatrix} 1 \\ 1 \end{bmatrix} = 2 \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 2 \\ 2 \end{bmatrix}$
$Av_2 = \lambda_2 v_2 \implies A \begin{bmatrix} 1 \\ -1 \end{bmatrix} = -1 \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} -1 \\ 1 \end{bmatrix}$

我們可以將這兩個方程式合併成一個矩陣方程式。令 $P$ 為由特徵向量組成的矩陣，令 $D$ 為由特徵值組成的對角矩陣。
$P = \begin{bmatrix} v_1 & v_2 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$
$D = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & -1 \end{bmatrix}$

則 $AP = AD$。

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

為了求得 $A$，我們需要計算 $P$ 的逆矩陣 $P^{-1}$。
$\det(P) = (1)(-1) - (1)(1) = -1 - 1 = -2$。

$$P^{-1} = \frac{1}{\det(P)} \begin{bmatrix} -1 & -1 \\ -1 & 1 \end{bmatrix} = \frac{1}{-2} \begin{bmatrix} -1 & -1 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} 1/2 & 1/2 \\ 1/2 & -1/2 \end{bmatrix}$$

現在，我們可以求出 $A = (AD)P^{-1}$。

$$A = \begin{bmatrix} 2 & -1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 1/2 & 1/2 \\ 1/2 & -1/2 \end{bmatrix}$$ $$A = \begin{bmatrix} 2(1/2) + (-1)(1/2) & 2(1/2) + (-1)(-1/2) \\ 2(1/2) + 1(1/2) & 2(1/2) + 1(-1/2) \end{bmatrix}$$ $$A = \begin{bmatrix} 1 - 1/2 & 1 + 1/2 \\ 1 + 1/2 & 1 - 1/2 \end{bmatrix} = \begin{bmatrix} 1/2 & 3/2 \\ 3/2 & 1/2 \end{bmatrix}$$

【答案】$A = \begin{bmatrix} 1/2 & 3/2 \\ 3/2 & 1/2 \end{bmatrix}$

本題考查 $n$ 維超立方體圖 $Q_n$ 的定義與繪製。

定義：
$n$ 維超立方體圖 $Q_n$ 的頂點集合是所有長度為 $n$ 的位元字串（即 $\{0, 1\}^n$）。
兩個頂點是相鄰的，若且唯若它們所代表的位元字串恰好只有一個位元不同。

繪製 $Q_4$：
$Q_4$ 的頂點代表長度為 4 的位元字串，共有 $2^4 = 16$ 個頂點。
頂點之間的連線規則是，兩個字串僅有一個位元不同。

繪製 $Q_4$ 的一種常見方法是從低維度的超立方體圖開始，逐步建構。
$Q_0$：一個頂點 (空字串 $\epsilon$)。
$Q_1$：兩個頂點 (0, 1)，它們之間有一條邊。
$Q_2$：四個頂點 (00, 01, 10, 11)。這可以看作是兩個 $Q_1$ 的副本，副本之間對應的頂點相連。
例如：
副本1 (前綴0)：00, 01
副本2 (前綴1)：10, 11
連線：00-10, 01-11。
$Q_2$ 形成一個正方形。

$Q_3$：八個頂點 ($2^3=8$)。這是兩個 $Q_2$ 的副本，副本之間對應的頂點相連。
例如：
副本1 (前綴0)：000, 001, 010, 011
副本2 (前綴1)：100, 101, 110, 111
連線：000-100, 001-101, 010-110, 011-111。
$Q_3$ 形成一個立方體。

$Q_4$：十六個頂點 ($2^4=16$)。這是兩個 $Q_3$ 的副本，副本之間對應的頂點相連。
我們可以將 $Q_4$ 想像成兩個 $Q_3$ 立方體，一個代表位元字串前綴為 0 (即 $0xxx$)，另一個代表前綴為 1 (即 $1xxx$)。
然後，將第一個 $Q_3$ 的每個頂點與第二個 $Q_3$ 中對應的頂點連接起來。

繪製步驟：

1. 繪製第一個 $Q_3$ 立方體，其頂點標記為 $0$ 後加上一個 3 位元的字串，例如：$0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111$。
2. 繪製第二個 $Q_3$ 立方體，其頂點標記為 $1$ 後加上一個 3 位元的字串，例如：$1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$。
3. 在兩個立方體之間，連接對應的頂點。例如，頂點 $0000$ 連接到頂點 $1000$；頂點 $0101$ 連接到頂點 $1101$；以此類推，總共會有 8 條連接線。

圖形描述：
$Q_4$ 可以想像成兩個立方體，一個在另一個的「上方」或「前面」。
第一個立方體的頂點（以 0 開頭）：
$0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111$

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

給定的遞迴關係式為 $a_n - 2a_{n-1} = 1$，其中 $n \ge 1$，且初始條件為 $a_0 = 1$。

我們將此遞迴關係式寫成 $a_n = 2a_{n-1} + 1$。

求解此類遞迴關係式通常分為兩部分：齊次解和特解。

第一步：求解齊次遞迴關係式
齊次遞迴關係式為 $a_n^{(h)} - 2a_{n-1}^{(h)} = 0$，即 $a_n^{(h)} = 2a_{n-1}^{(h)}$。
其特徵方程式為 $r - 2 = 0$，所以特徵根為 $r = 2$。
因此，齊次解為 $a_n^{(h)} = C \cdot 2^n$，其中 $C$ 是常數。

第二步：求解特解
對於非齊次項 $1$（一個常數），我們可以假設特解的形式為 $a_n^{(p)} = A$（一個常數）。
將 $a_n^{(p)} = A$ 代入原遞迴關係式 $a_n - 2a_{n-1} = 1$：
$A - 2A = 1$
$-A = 1$
$A = -1$
所以，特解為 $a_n^{(p)} = -1$。

第三步：合併齊次解和特解得到通解
通解為 $a_n = a_n^{(h)} + a_n^{(p)}$。
$a_n = C \cdot 2^n - 1$。

第四步：利用初始條件確定常數 $C$
已知初始條件 $a_0 = 1$。將 $n=0$ 代入通解：
$a_0 = C \cdot 2^0 - 1$
$1 = C \cdot 1 - 1$
$1 = C - 1$
$C = 2$

核心觀念

長度為 $4$ 的 path 表示從 $a$ 出發，經過 $4$ 條邊，最後抵達 $d$：

$$a\to v_1\to v_2\to v_3\to d$$

圖中的交叉點沒有標示頂點，因此兩條斜線只在圖形上交叉，並不構成新的頂點。可用的邊為

$$(a,b),\ (a,c),\ (d,b),\ (d,c)$$

每次從 $a$ 或 $d$ 只能走到 $b$ 或 $c$；從 $b$ 或 $c$ 只能走回 $a$ 或 $d$。

解題方法

第一步由 $a$ 出發，有 $2$ 種選擇：

$$a\to b,\qquad a\to c$$

第二步從 $b$ 或 $c$ 出發，可到 $a$ 或 $d$，各有 $2$ 種選擇。

第三步再從 $a$ 或 $d$ 到 $b$ 或 $c$，有 $2$ 種選擇。

最後一步由 $b$ 或 $c$ 到達 $d$，均可直接到達。

因此共有

$$2\times 2\times 2=8$$

本題考查數論中的同餘與模反元素。

定義：
若 $a, b$ 為整數，$m$ 為正整數，則稱 $a$ 與 $b$ 同餘於模 $m$，記作 $a \equiv b \pmod{m}$，若且唯若 $m$ 整除 $a-b$。

(a) 求 144 模 233 的反元素。
我們需要找到一個整數 $x$ 使得 $144x \equiv 1 \pmod{233}$。
這相當於求解線性 Diophantine 方程式 $144x + 233y = 1$。
我們可以利用擴展歐幾里得演算法 (Extended Euclidean Algorithm) 來求解。

步驟 1：對 233 和 144 執行歐幾里得演算法。
$233 = 1 \cdot 144 + 89$
$144 = 1 \cdot 89 + 55$
$89 = 1 \cdot 55 + 34$
$55 = 1 \cdot 34 + 21$
$34 = 1 \cdot 21 + 13$
$21 = 1 \cdot 13 + 8$
$13 = 1 \cdot 8 + 5$
$8 = 1 \cdot 5 + 3$
$5 = 1 \cdot 3 + 2$
$3 = 1 \cdot 2 + 1$
$2 = 2 \cdot 1 + 0$
最大公因數是 1，表示 144 和 233 互質，所以模反元素存在。

步驟 2：反向代入，將 1 表示為 144 和 233 的線性組合。
$1 = 3 - 1 \cdot 2$
$1 = 3 - 1 \cdot (5 - 1 \cdot 3) = 3 - 5 + 3 = 2 \cdot 3 - 5$
$1 = 2 \cdot (8 - 1 \cdot 5) - 5 = 2 \cdot 8 - 2 \cdot 5 - 5 = 2 \cdot 8 - 3 \cdot 5$
$1 = 2 \cdot 8 - 3 \cdot (13 - 1 \cdot 8) = 2 \cdot 8 - 3 \cdot 13 + 3 \cdot 8 = 5 \cdot 8 - 3 \cdot 13$
$1 = 5 \cdot (21 - 1 \cdot 13) - 3 \cdot 13 = 5 \cdot 21 - 5 \cdot 13 - 3 \cdot 13 = 5 \cdot 21 - 8 \cdot 13$

核心觀念

本題考察「抽屜原理」：若要保證某一類別至少出現 $k$ 個，先計算在「尚未達到 $k$ 個」的情況下最多能抽出多少張，再多抽 $1$ 張即可保證達成條件。

標準撲克牌共有四種花色，每種花色各有 $13$ 張；其中紅心牌共有 $13$ 張，非紅心牌共有 $39$ 張。

解題方法

(a) 保證至少有五張同花色

為了延後出現五張同花色，最多只能從每種花色抽出四張。

四種花色最多可抽出：

$$4 \times 4=16$$

此時每種花色都只有四張，尚未出現至少五張同花色。再抽出下一張牌時，無論該牌屬於哪一種花色，都會使該花色達到至少五張。

因此所需張數為：

$$16+1=17$$

(b) 保證至少有五張紅心

核心觀念

本題考查：

• 補集計數法；
• 遞迴關係；
• 避免出現連續三個 $0$ 的二進位字串計數。

令

• $a_n$：長度為 $n$ 且含有連續三個 $0$ 的二進位字串數；
• $b_n$：長度為 $n$ 且不含有連續三個 $0$ 的二進位字串數。

所有長度為 $n$ 的二進位字串一共有 $2^n$ 個，因此

$$a_n=2^n-b_n.$$

解題方法

先計算不含有 $000$ 的字串數 $b_n$。

一個不含有 $000$ 的長度為 $n$ 字串，其最後一段必定屬於下列三種形式之一：

1. 以 $1$ 結尾；
2. 以 $01$ 結尾；
3. 以 $001$ 結尾。

因此，分別去除最後的 $1$、$01$、$001$ 後，前面的部分長度分別為 $n-1$、$n-2$、$n-3$，且都不能含有 $000$。所以

$$b_n=b_{n-1}+b_{n-2}+b_{n-3},\qquad n\geq 3.$$

由於 $a_n=2^n-b_n$，可得

\begin{align*}
a_n
&=2^n-\left(b_{n-1}+b_{n-2}+b_{n-3}\right)\
&=2^n-\left[(2^{n-1}-a_{n-1})+(2^{n-2}-a_{n-2})+(2^{n-3}-a_{n-3})\right]\
&=a_{n-1}+a_{n-2}+a_{n-3}
+\left(2^n-2^{n-1}-2^{n-2}-2^{n-3}\right).
\end{align*}

而

$$2^n-2^{n-1}-2^{n-2}-2^{n-3}=2^{n-3},$$

故所求遞迴關係為

$$\boxed{a_n=a_{n-1}+a_{n-2}+a_{n-3}+2^{n-3}},\qquad n\geq 3.$$

初始條件

長度為 $0$、$1$、$2$ 的字串都不可能含有連續三個 $0$，因此