109 年國立中央大學資訊工程學系碩士班《離散數學與線性代數》考古題與詳解

Question 1

$AB=BA$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣乘法一般不符合交換律。即使 $A$、$B$ 都是相同階數的方陣，也不代表 $AB=BA$；只有特定矩陣組合才會滿足交換關係。 解題方法 要判斷「$AB=BA$」是否對所有矩陣都成立，只要找出一組矩陣使兩種乘法順序的結果不同，即可否定此敘述。 取 $$ A=\begin{bmatrix}1&0\0&0\end{bmatrix}, \qquad B=\begin{bmatrix}0&1\1&0\end{bmatrix}. $$ 依照矩陣乘法定義，分別計算： $$ AB = \begin{bmatrix}1&0\0&0\end{bmatrix} \begin{bmatrix}0&1\1&0\end{bmatrix} = \begin{bmatrix}0&1\0&0\end{bmatrix}, $$

Question 2

$AB=AC\Rightarrow B=C$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣乘法一般不具有消去律。由 $AB=AC$ 可得 $$ A(B-C)=0 $$ 但這只表示 $B-C$ 的每一個欄向量都落在 $A$ 的零空間中，不一定表示 $B-C=0$，因此不能直接推出 $B=C$。 解題方法 用一組符合題意的矩陣作反例，即可判定此命題是否對所有矩陣成立。取 $$ A=\begin{bmatrix}0\end{bmatrix},\qquad B=\begin{bmatrix}1\end{bmatrix},\qquad C=\begin{bmatrix}2\end{bmatrix} $$ 則 $B
e C$，但

Question 3

$AB=0\Rightarrow A=0$ or $B=0$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣乘法不具有「零乘積必有一個因子為零」的性質。也就是說，即使 $AB=0$，仍可能同時有 $A
e 0$ 與 $B
e 0$。這與實數乘法不同。 解題方法 以反例判斷此命題。取兩個非零的 $2	imes 2$ 矩陣： $$ A= \begin{bmatrix} 1&0\ 0&0 \end{bmatrix}, \qquad B= \begin{bmatrix} 0&0\ 0&1 \end{bmatrix}. $$ 兩矩陣相乘：

Question 4

$(AB)^T=A^TB^T$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣乘積轉置時，乘法順序會顛倒： $$ (AB)^T=B^TA^T $$ 若 $A$ 為 $m	imes n$ 矩陣、$B$ 為 $n	imes p$ 矩陣，則 $AB$ 為 $m	imes p$ 矩陣，因此 $(AB)^T$ 為 $p	imes m$ 矩陣；而 $B^TA^T$ 的尺寸也是 $(p	imes n)(n	imes m)=p	imes m$，符合結果的尺寸。 解題方法 直接套用矩陣乘積的轉置公式。轉置會把乘積中的因子順序反轉，所以正確關係是： $$ (AB)^T=B^TA^T $$ 題目寫成 $A^TB^T$，並未反轉順序，因此一般不成立。 選項分析

Question 5

$(rA)^{-1}=rA^{-1}$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣乘上純量後再取反矩陣，純量會以倒數形式出現。若 $A$ 為可逆方陣且 $r
e 0$，則 $$ (rA)^{-1}=\frac{1}{r}A^{-1}. $$ 這題考的是反矩陣的純量倍數性質。 解題方法 利用反矩陣的定義驗證。令 $X=\frac{1}{r}A^{-1}$，則 $$ (rA)X=(rA)\left(\frac{1}{r}A^{-1}ight) =AA^{-1} =I. $$ 同理，$X(rA)=I$，所以 $$ (rA)^{-1}=\frac{1}{r}A^{-1}. $$

Question 6

$\det(A+B)=\det A+\det B$。 (A) True. (B) False.

Accepted Answer

核心觀念 行列式一般不具加法性，也就是通常不成立 $$ \det(A+B)=\det A+\det B。 $$ 行列式對每一列（或每一行）分別具有線性，但這不代表把兩個矩陣相加後，行列式會等於兩個行列式相加。 解題方法 以相同大小的方陣作反例即可判斷命題。令 $$ A=B=I2= \begin{bmatrix} 1&0\ 0&1 \end{bmatrix}。 $$ 則 $$ \det A=\det B=1， $$ 而

Question 7

$\det(AB)=\det A\det B$。 (A) True. (B) False.

Accepted Answer

核心觀念 行列式具有乘法性：若 $A$、$B$ 是相同階數的方陣，則 $$ \det(AB)=\det(A)\det(B). $$ 行列式只對方陣有定義（長方形矩陣即使相乘得到方陣，$\det A$、$\det B$ 也不存在），所以題目寫出 $\det A$、$\det B$，就表示 $A$、$B$ 是同階方陣，此時性質恆成立。 解題方法

Question 8

$\det(AB)=\det(BA)$。 (A) True. (B) False.

Accepted Answer

核心觀念 本題組（與上一題 $\det(AB)=\det A\det B$ 同一組）的 $A$、$B$ 指的是同階方陣——行列式只對方陣定義，題組中的 $\det A$、$\det B$ 都要存在。對同階方陣，行列式有乘法性： $$ \det(AB)=\det A\,\det B . $$ 解題方法 利用乘法性與純量乘法的交換律： $$ \det(AB)=\det A\,\det B=\det B\,\det A=\det(BA). $$ 雖然矩陣乘法一般不可交換（$AB
eq BA$），但兩者的行列式一定相等，因為行列式是純量，純量相乘可交換。 選項分析 - (A) True：正確。 對同階方陣 $A$、$B$，由乘法性可得 $\det(AB)=\det(BA)$。 - (B) False：錯誤。

Question 9

$\det(rA)=r\det A$。 (A) True. (B) False.

Accepted Answer

核心觀念 行列式對矩陣的每一列（或每一行）都具有線性。若 $A$ 是 $n	imes n$ 方陣，將 $A$ 乘上純量 $r$，等於把 $A$ 的每一列都乘上 $r$。因此行列式會總共乘上 $n$ 次 $r$： $$ \det(rA)=r^n\det A $$ 題目敘述把右側寫成 $r\det A$，一般情況下並不成立。 解題方法 由行列式的列線性，每一列提出一個 $r$，共有 $n$ 列，故 $$ \det(rA) = \underbrace{r\cdot r\cdots r}{n	ext{ 個}} \det A = r^n\det A $$ 以 $2	imes2$ 單位矩陣 $A=I2$、$r=2$ 驗證：

Question 10

$\det(A^{-1})=(-1)\det A$。 (A) True. (B) False.

Accepted Answer

核心觀念 對可逆方陣 $A$，行列式具有乘法性： $$ \det(AB)=\det(A)\det(B) $$ 又因為 $AA^{-1}=I$，且單位矩陣的行列式為 $1$，所以 $\det(A^{-1})$ 是 $\det(A)$ 的乘法反元素。 解題方法 由 $AA^{-1}=I$ 兩邊取行列式： $$ \det(A)\det(A^{-1})=\det(I)=1 $$ 因此： $$ \det(A^{-1})=\frac{1}{\det(A)} $$

Question 11

If $b
e 0$, the solution set may be a subspace. (A) True. (B) False.

Accepted Answer

核心觀念 線性方程組 $Ax=b$ 的解集合若要成為子空間，必須包含零向量。由於 $A$ 是線性變換，$A\mathbf{0}=\mathbf{0}$；因此當 $b
e\mathbf{0}$ 時，零向量不會是方程組的解。 解題方法 題目已知方程組相容，所以解集合非空。取其中一個特解 $\mathbf{x}p$，所有解可寫成 $$ \mathbf{x}=\mathbf{x}p+\mathbf{z},\qquad \mathbf{z}\in\operatorname{Null}(A). $$ 因此解集合是零空間的平移。要成為子空間，它必須包含 $\mathbf{0}$；但若 $\mathbf{0}$ 是解，就必須滿足

Question 12

If $b
e 0$, the solution set is not a subspace. (A) True. (B) False.

Accepted Answer

核心觀念 線性子空間必須包含零向量。對線性系統 $Ax=b$，若 $b
e 0$，代入 $x=0$ 得 $$ A0=0
e b, $$ 所以零向量不是此系統的解。任何線性子空間都包含零向量，因此這個解集合不是子空間。 由於題幹已說明系統相容，解集合非空。若取一個特解 $xp$，所有解可寫成 $$ \{x:Ax=b\}=xp+\operatorname{Null}(A), $$ 這是零空間的平移，稱為仿射集合；當 $b
e 0$ 時，它不包含零向量，故不是線性子空間。 解題方法

Question 13

If $b=0$, the solution set may be or may not be a subspace. (A) True. (B) False.

Accepted Answer

核心觀念 當 $b=0$ 時，方程組 $Ax=b$ 成為齊次線性系統 $Ax=0$。它的解集合就是矩陣 $A$ 的零空間： $$ \mathcal{N}(A)=\{x:Ax=0\}. $$ 零空間是子空間：它包含零向量，且對向量加法與純量乘法封閉。 解題方法 設 $u,v$ 為解，則 $Au=Av=0$。對任意純量 $c$， $$ A(u+v)=Au+Av=0+0=0, $$ $$ A(cu)=c(Au)=c\cdot 0=0. $$

Question 14

If $b=0$, the solution set is not a subspace. (A) True. (B) False.

Accepted Answer

核心觀念 當 $b=0$ 時，方程組 $Ax=b$ 成為齊次線性系統 $Ax=0$。它的解集合就是矩陣 $A$ 的零空間： $$ \mathcal{N}(A)=\{x\in\mathbb{R}^n:Ax=0\}. $$ 矩陣的零空間是 $\mathbb{R}^n$ 的子空間，因為它包含零向量，且對向量加法與純量乘法封閉。 解題方法 先檢查零向量是否為解：$A\mathbf{0}=\mathbf{0}$，因此 $\mathbf{0}\in\mathcal{N}(A)$。 再取任意 $u,v\in\mathcal{N}(A)$ 與純量 $c$。由 $Au=Av=0$，可得

Question 15

If $b=0$, the solution set is exactly a subspace. (A) True. (B) False.

Accepted Answer

核心觀念

當 $b=0$ 時，方程組 $Ax=b$ 成為齊次線性方程組 $Ax=0$ 。它的解集合就是矩陣 $A$ 的零空間：

\mathcal{N}(A)=\{x:Ax=0\}.

線性方程組的零空間是向量子空間。

解題方法

檢查解集合是否包含零向量，並對線性組合封閉：

零向量是解，因為 $A0=0$ 。
若 $x_1,x_2$ 都是解，則 $Ax_1=Ax_2=0$ 。對任意純量 $c_1,c_2$ ，

A(c_1x_1+c_2x_2) =c_1Ax_1+c_2Ax_2 =0.

Question 16

$\det(A)=\det(B)$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 與 $B$ 相似，表示存在可逆矩陣 $P$，使得 $$ B=P^{-1}AP. $$ 利用行列式的乘法性 $\det(XY)=\det(X)\det(Y)$，可得相似矩陣的行列式相同。 解題方法 由 $B=P^{-1}AP$，兩邊取行列式： $$ \det(B)=\det(P^{-1})\det(A)\det(P). $$ 因為 $P$ 可逆，所以 $\det(P^{-1})=\dfrac{1}{\det(P)}$。因此

Question 17

$A^2$ is similar to $B^2$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 與 $B$ 相似，表示存在可逆矩陣 $P$，使得 $$ B=P^{-1}AP. $$ 相似矩陣具有相同的特徵值與特徵多項式；更重要的是，相似關係保留矩陣的乘冪。對任意正整數 $k$，都有 $$ B^k=(P^{-1}AP)^k=P^{-1}A^kP. $$ 因此，$A^k$ 與 $B^k$ 仍然相似。 解題方法 由題目給定 $A$ 與 $B$ 相似，存在可逆矩陣 $P$ 使 $B=P^{-1}AP$。將此式平方： $$ B^2=(P^{-1}AP)(P^{-1}AP) =P^{-1}A(PP^{-1})AP =P^{-1}A^2P. $$

Question 18

$A^T$ is similar to $B^T$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 與 $B$ 相似，表示存在可逆矩陣 $P$，使得 $$ A=P^{-1}BP. $$ 相似矩陣代表同一線性變換在不同基底下的矩陣表示。轉置後仍可找到可逆矩陣，將 $A^T$ 表示為 $B^T$ 的相似矩陣。 解題方法 由 $A=P^{-1}BP$ 兩側取轉置。利用 $(XYZ)^T=Z^TY^TX^T$： $$ A^T=(P^{-1}BP)^T =P^TB^T(P^{-1})^T. $$

Question 19

$A^{-1}$ is similar to $B^{-1}$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 與 $B$ 相似，表示存在可逆矩陣 $P$，使得 $$ A=P^{-1}BP。 $$ 相似矩陣代表同一線性變換在不同基底下的矩陣表示。若 $A$、$B$ 都可逆，便可對相似關係兩側取反矩陣。 解題方法 由 $A=P^{-1}BP$，利用矩陣乘積取反矩陣時順序反轉： $$ A^{-1}=(P^{-1}BP)^{-1} =P^{-1}B^{-1}(P^{-1})^{-1} =P^{-1}B^{-1}P。 $$

Question 20

$AB$ is similar to $BA$。 (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $X$ 與 $Y$ 相似，表示存在可逆矩陣 $P$，使得 $$ P^{-1}XP=Y。 $$ 相似矩陣是透過可逆的換基變換互相轉換。此題可直接尋找一個可逆矩陣，將 $AB$ 共軛成 $BA$。 解題方法 因為 $A$ 可逆，取相似變換矩陣 $P=A$。則 $$ A^{-1}(AB)A = (A^{-1}A)BA = BA。 $$

Question 21

$A$ has $n$ distinct eigenvalues. (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 可對角化，表示存在可逆矩陣 $P$ 與對角矩陣 $D$，使得 $$ A=PDP^{-1}. $$ 對角化代表 $A$ 有足夠的線性獨立特徵向量；它不要求特徵值彼此相異。每個特徵值的重數可以大於 $1$。 解題方法 以單位矩陣 $In$ 作為反例。它本身就是對角矩陣，因此可對角化；但當 $n\ge 2$ 時，所有對角元素都是 $1$，所以它只有一個相異特徵值 $1$，並非 $n$ 個相異特徵值。

Question 22

$A$ has $n$ linearly independent columns. (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 可對角化，表示存在可逆矩陣 $P$ 與對角矩陣 $D$，使得 $$ A=PDP^{-1}. $$ 這只表示 $A$ 有一組由特徵向量構成的基底，並不保證 $A$ 可逆。$A$ 的欄向量線性獨立，等價於 $A$ 可逆；而 $A$ 可逆又等價於 $0$ 不是 $A$ 的特徵值。 解題方法 判斷敘述是否必然成立，可以檢查可對角化矩陣是否可能含有特徵值 $0$。取 $n	imes n$ 零矩陣 $A=0$，它本身就是對角矩陣，因此可對角化；

Question 23

$A^T$ and $A^{-1}$ are all diagonalizable. (A) True. (B) False.

Accepted Answer

核心觀念 $A$ 可對角化表示存在可逆矩陣 $P$ 與對角矩陣 $D$，使 $A=PDP^{-1}$。可對角化與可逆是兩件獨立的事：$D$ 的對角線（特徵值）可以有 $0$，此時 $A$ 可對角化但不可逆。 解題方法 1. $A^T$：一定可對角化。 $$ A^T=(PDP^{-1})^T=(P^{-1})^T D^T P^T=(P^T)^{-1} D\, P^T , $$ 令 $Q=(P^T)^{-1}$，則 $A^T=QDQ^{-1}$，故 $A^T$ 可對角化。 2. $A^{-1}$：不一定存在。 若 $A$ 可逆（所有特徵值非零），則 $A^{-1}=PD^{-1}P^{-1}$ 也可對角化；但題目只說 $A$ 可對角化，沒有保證可逆。反例： $$ A=\begin{bmatrix}1&0\0&0\end{bmatrix} $$

Question 24

$A$ has no zero eigenvalues. (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 可對角化，表示存在可逆矩陣 $P$ 與對角矩陣 $D$，使得 $$ A=PDP^{-1}. $$ $D$ 的對角線元素就是 $A$ 的特徵值。可對角化只要求有足夠的線性獨立特徵向量，並不要求特徵值都非零。 解題方法 取 $A$ 為零矩陣，則 $$ A=\begin{bmatrix}0&0\0&0\end{bmatrix} $$

Question 25

$A$ has $n$ linearly independent eigenspaces. (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 可對角化，表示存在由 $A$ 的特徵向量組成的一組基底；等價地，$A$ 有 $n$ 個線性獨立的特徵向量。這不代表 $A$ 一定有 $n$ 個不同的特徵值，也不代表它有 $n$ 個特徵空間。 特徵空間是對應特徵值 $\lambda$ 的所有特徵向量（再加上零向量）所成的子空間： $$ E\lambda=\ker(A-\lambda I). $$ 解題方法 用單位矩陣作反例。對 $A=In$，任意非零向量 $v$ 都滿足 $Av=v$，所以唯一的特徵值是 $1$，其特徵空間為 $$ E1=\mathbb{R}^n. $$

Question 26

$\operatorname{Nul} A$ is the orthogonal complement of $\operatorname{Row} A$. (A) True. (B) False.

Accepted Answer

核心觀念 對 $m	imes n$ 矩陣 $A$，零空間 $\operatorname{Nul} A$ 是所有滿足 $A\mathbf{x}=\mathbf{0}$ 的向量所成的子空間，位於 $\mathbb{R}^n$。列空間 $\operatorname{Row} A$ 由 $A$ 的各列向量張成，也位於 $\mathbb{R}^n$。 兩者滿足基本關係： $$ \operatorname{Nul} A=(\operatorname{Row} A)^\perp. $$ 也就是說，$A\mathbf{x}=\mathbf{0}$ 恰好等價於 $\mathbf{x}$ 與 $A$ 的每一列都正交。 解題方法 設 $A$ 的列向量為 $\mathbf{r}1,\ldots,\mathbf{r}m$。矩陣乘法可寫成： $$ A\mathbf{x} = \begin{bmatrix} \mathbf{r}1\cdot\mathbf{x}\ \vdots\ \mathbf{r}m\cdot\mathbf{x} \end{bmatrix}. $$ 因此，$\mathbf{x}\in\operatorname{Nul} A$ 等價於 $A\mathbf{x}=\mathbf{0}$，也等價於：

Question 27

$W^\perp$ is always a subspace. (A) True. (B) False.

Accepted Answer

核心觀念 對 $W\subseteq\mathbb{R}^n$，其正交補空間定義為 $$ W^\perp=\{x\in\mathbb{R}^n\mid x\cdot w=0	ext{，對每個 }w\in W\}. $$ 判斷是否為子空間，可檢查是否包含零向量，並對向量加法及純量乘法封閉。 解題方法 任取 $x,y\in W^\perp$ 與純量 $c$。依定義，對每個 $w\in W$ 都有 $x\cdot w=0$、$y\cdot w=0$，因此 $$ 0\cdot w=0, \qquad (x+y)\cdot w=x\cdot w+y\cdot w=0, \qquad (cx)\cdot w=c(x\cdot w)=0. $$

Question 28

$(W^\perp)^\perp=W$。 (A) True. (B) False.

Accepted Answer

核心觀念 在 $\mathbb{R}^n$ 中，$W^\perp$ 是所有與 $W$ 中每個向量都正交的向量所成的集合： $$ W^\perp=\{x\in\mathbb{R}^n:\langle x,wangle=0	ext{，對所有 }w\in W\}. $$ 有限維內積空間中，對任意集合 $W$ 都有 $$ (W^\perp)^\perp=\operatorname{span}(W), $$ 其中 $\operatorname{span}(W)$ 是由 $W$ 張成的子空間。因此，只有當 $W$ 本身是子空間時，才可直接得到 $(W^\perp)^\perp=W$。 解題方法 題目只說 $W$ 是 $\mathbb{R}^n$ 的子集，沒有說 $W$ 是子空間。用一個不是子空間的集合檢查等式即可。 取 $\mathbb{R}^2$ 中的集合 $W=\{(1,0)\}$。向量 $(a,b)$ 與 $(1,0)$ 正交，當且僅當 $$ (a,b)\cdot(1,0)=a=0. $$ 所以

Question 29

If $v$ and $w$ are orthogonal, then $Av$ and $Aw$ are orthogonal. (A) True. (B) False.

Accepted Answer

核心觀念 矩陣 $A$ 的欄向量兩兩正交，代表不同欄向量的內積為 $0$，也就是 $A^{T}A$ 是對角矩陣。這個條件不代表 $A$ 會保留所有向量間的正交關係。 對任意 $v,w\in\mathbb{R}^{n}$， $$ (Av)\cdot(Aw)=v^{T}A^{T}Aw. $$ 因此，$Av$ 與 $Aw$ 是否正交，取決於 $v^{T}A^{T}Aw$ 是否為 $0$。 解題方法 用反例檢驗敘述。取 $$ A= \begin{bmatrix} 1&0\ 0&2 \end{bmatrix}, \qquad v= \begin{bmatrix} 1\ 1 \end{bmatrix}, \qquad w= \begin{bmatrix} 1\ -1 \end{bmatrix}. $$ $A$ 的兩個欄向量分別為 $(1,0)^{T}$ 與 $(0,2)^{T}$，內積為 $0$，符合「欄向量正交」的條件。原向量也正交： $$ v\cdot w=1(1)+1(-1)=0. $$

Question 30

$W\cup W^\perp=\mathbb{R}^n$。 (A) True. (B) False.

Accepted Answer

核心觀念 對 $W\subseteq\mathbb{R}^n$，其正交補空間定義為 $$ W^\perp=\{x\in\mathbb{R}^n:\ x\cdot w=0	ext{，對每個 }w\in W\}. $$ $W\cup W^\perp$ 表示「屬於 $W$ 或屬於 $W^\perp$」的向量所成的集合。這和兩個子空間的和 $W+W^\perp$ 不同。 若 $W$ 是 $\mathbb{R}^n$ 的子空間，有限維內積空間中的正交分解定理給出 $$ \mathbb{R}^n=W\oplus W^\perp, $$ 也就是每個向量都能寫成 $W$ 中向量與 $W^\perp$ 中向量的和；這不代表每個向量本身都屬於兩者之一。 解題方法 用 $\mathbb{R}^2$ 中的反例即可判斷命題是否對所有 $W$ 成立。令 $$ W=\operatorname{span}\{(1,0)\}. $$

Question 31

$0$ and $-1$ are in the $\beta$-matrix. (A) True. (B) False.

Accepted Answer

核心觀念 若 $P=[\,b1\ b2\ b3\,]$ 是由 $\beta=\{b1,b2,b3\}$ 的基底向量組成的矩陣，則線性變換 $x\mapsto Ax$ 在 $\beta$ 座標系下的矩陣為 $$ [A]{\beta}=P^{-1}AP. $$ 等價地，$[A]{\beta}$ 的第 $j$ 欄，就是 $Abj$ 用基底 $\beta$ 表示時的座標。 解題方法 先計算 $Ab1,Ab2,Ab3$，再分別求出它們在 $\beta$ 下的座標。 $$ Ab1= \begin{bmatrix} -7&-48&-16\ 1&14&6\ -3&-45&-19 \end{bmatrix} \begin{bmatrix}-3\1\-3\end{bmatrix} = \begin{bmatrix}21\-7\21\end{bmatrix} =-7b1. $$ 因此，$Ab1$ 的 $\beta$ 座標為 $\begin{bmatrix}-7\0\0\end{bmatrix}$。 $$ Ab2= \begin{bmatrix}14\-6\18\end{bmatrix}. $$ 設 $Ab2=xb1+yb2+zb3$。比較分量可得 $$ \begin{cases} -3x-2y+3z=14,\ x+y-z=-6,\ -3x-3y=18. \end{cases} $$

Question 32

$1$ and $-3$ are in the $\beta$-matrix. (A) True. (B) False.

Accepted Answer

核心觀念

若 $A$ 是標準座標下的線性轉換矩陣，而新基底為 $\beta=\{b_1,b_2,b_3\}$ ，令

P=\begin{bmatrix}b_1&b_2&b_3\end{bmatrix},

則 $\beta$ -矩陣為

[A]_\beta=P^{-1}AP.

也就是先計算 $Ab_j$ ，再把結果改寫成基底 $\beta$ 的線性組合；各組合係數就是 $\beta$ -矩陣的第 $j$ 欄。

解題方法

設向量 $y=(x,y,z)^T$ 在基底 $\beta$ 下的座標為 $(u,v,w)^T$ ，則

y=u b_1+v b_2+w b_3.

比較分量可得

x=-3u-2v+3w,\qquad y=u+v-w,\qquad z=-3u-3v.

解得

v=x+3y,\qquad u=-\frac{z}{3}-x-3y,\qquad w=-\frac{z}{3}-y.

先計算 $A$ 對各基底向量的作用：

Ab_1=\begin{bmatrix}21\\-7\\21\end{bmatrix}=-7b_1,

Question 33

$-2$ and $-4$ are in the $\beta$-matrix. (A) True. (B) False.

Accepted Answer

核心觀念 若 $A$ 是標準座標下的線性轉換矩陣，而 $P=[\,b1\ b2\ b3\,]$ 是以 $\beta=\{b1,b2,b3\}$ 為欄向量組成的基底矩陣，則相對於 $\beta$ 的轉換矩陣為 $$ [A]{\beta}=P^{-1}AP. $$ 也可以逐一計算 $Abj$，再把結果表示成基底 $\beta$ 的線性組合；這些線性組合的係數就是 $[A]{\beta}$ 的各欄。 解題方法 先計算 $A$ 對各基底向量的作用： $$ Ab1= \begin{bmatrix} 21\ -7\ 21 \end{bmatrix} =-7b1, $$ 所以第一欄的基底座標為 $\begin{bmatrix}-7&0&0\end{bmatrix}^{T}$。 接著， $$ Ab2= \begin{bmatrix} 14\ -6\ 18 \end{bmatrix} =-2b1-4b2+0b3, $$

Question 34

$-6$ and $-7$ are in the $\beta$-matrix. (A) True. (B) False.

Accepted Answer

核心觀念 若 $A$ 是標準座標下的線性轉換矩陣，而 $P=[\,b1\ b2\ b3\,]$ 是基底 $\beta$ 的基底矩陣，則相對於 $\beta$ 的矩陣為 $$ [A]\beta=P^{-1}AP. $$ 這個矩陣的第 $j$ 欄，是 $A bj$ 用基底 $\beta$ 表示時的座標。 解題方法 先計算 $A$ 作用在各基底向量上的結果： $$ Ab1= \begin{bmatrix} 21\-7\21 \end{bmatrix}, \qquad Ab2= \begin{bmatrix} 14\-6\18 \end{bmatrix}, \qquad Ab3= \begin{bmatrix} 27\-11\36 \end{bmatrix}. $$ 接著把每個結果寫成 $c1b1+c2b2+c3b3$。由 $$ c1b1+c2b2+c3b3 = \begin{bmatrix} -3c1-2c2+3c3\ c1+c2-c3\ -3c1-3c2 \end{bmatrix} $$ 可解得：

Question 35

$8$ and $-9$ are in the $\beta$-matrix. (A) True. (B) False.

Accepted Answer

核心觀念 若 $A$ 是標準座標系下的線性轉換矩陣，且新基底為 $\beta=\{b1,b2,b3\}$，令 $$ P=\begin{bmatrix}b1&b2&b3\end{bmatrix}, $$ 則相對於 $\beta$ 的矩陣為 $$ [A]\beta=P^{-1}AP. $$ 等價地說，第 $j$ 欄是 $Abj$ 用基底 $\beta$ 表示時的座標。先確認 $P$ 可逆；本題 $\det P=3
e 0$，所以 $\beta$ 確實是基底。 解題方法 依序計算 $Ab1,Ab2,Ab3$，再將結果寫成 $b1,b2,b3$ 的線性組合。 首先， $$ Ab1= \begin{bmatrix} 21\-7\21 \end{bmatrix} =-7b1, $$ 所以 $\beta$-matrix 的第一欄為 $\begin{bmatrix}-7\0\0\end{bmatrix}$。 接著， $$ Ab2= \begin{bmatrix} 14\-6\18 \end{bmatrix} =-2b1-4b2, $$

Question 36

$1$ is not in the $R$ matrix. (A) True. (B) False.

Accepted Answer

核心觀念 QR 分解將矩陣寫成 $A=QR$，其中 $Q$ 的欄向量互相正交且為單位向量，$R$ 為上三角矩陣。以 Gram–Schmidt 正交化計算時，$R$ 的元素由 $r{ij}=qi^{mathsf T}aj$（$i\leq j$）決定；對角元素是正交化後各向量的長度。 解題方法 設題目矩陣的三個欄向量為 $a1,a2,a3$。依序正交化並正規化： $$ a1=(1,1,1,1)^{\mathsf T},\qquad \|a1\|=2, \qquad q1=\frac12(1,1,1,1)^{\mathsf T}. $$ $$ r{12}=q1^{\mathsf T}a2=4,\qquad a2-r{12}q1=(1,-1,-1,1)^{\mathsf T}. $$ 因此 $r{22}=2$，且 $q2=\frac12(1,-1,-1,1)^{\mathsf T}$。 第三欄先投影到 $q1,q2$： $$ r{13}=q1^{\mathsf T}a3=5,\qquad r{23}=q2^{\mathsf T}a3=3. $$

Question 37

$3$ is not in the $R$ matrix. (A) True. (B) False.

Accepted Answer

核心觀念 QR 分解將矩陣 $A$ 寫成 $A=QR$，其中 $Q$ 的欄向量互相正交且長度為 $1$，$R$ 為上三角矩陣。以 Gram–Schmidt 正交化求解時，$r{ij}=qi^{T}aj$，其中 $aj$ 是 $A$ 的第 $j$ 欄，$qi$ 是 $Q$ 的第 $i$ 欄。 解題方法 令題目矩陣的三個欄向量為 $$ a1= \begin{bmatrix}1\1\1\1\end{bmatrix},\qquad a2= \begin{bmatrix}3\1\1\3\end{bmatrix},\qquad a3= \begin{bmatrix}5\0\2\3\end{bmatrix}. $$ 先將 $a1$ 單位化： $$ r{11}=\|a1\|=2,\qquad q1=\frac{a1}{2} =\frac12 \begin{bmatrix}1\1\1\1\end{bmatrix}. $$ 第二欄在 $q1$ 方向的投影係數為 $$ r{12}=q1^Ta2=4. $$ 扣除投影後， $$ u2=a2-r{12}q1 = \begin{bmatrix}1\-1\-1\1\end{bmatrix}, \qquad r{22}=\|u2\|=2, \qquad q2=\frac12 \begin{bmatrix}1\-1\-1\1\end{bmatrix}. $$ 第三欄在 $q1$ 與 $q2$ 方向的投影係數分別為

Question 38

$5$ is not in the $R$ matrix. (A) True. (B) False.

Accepted Answer

核心觀念 QR 分解將矩陣 $A$ 寫成 $A=QR$，其中 $Q$ 的欄向量互相正交且為單位向量，$R$ 是上三角矩陣。以 Gram–Schmidt 正交化計算時，$R$ 的元素為 $$ r{ij}=qi^{T}aj \quad (i\leq j), $$ 其中 $aj$ 是 $A$ 的第 $j$ 欄。題目要判斷數字 $5$ 是否出現在 $R$ 中。 解題方法 令 $A$ 的三個欄向量為 $$ a1=\begin{bmatrix}1\1\1\1\end{bmatrix},\qquad a2=\begin{bmatrix}3\1\1\3\end{bmatrix},\qquad a3=\begin{bmatrix}5\0\2\3\end{bmatrix}. $$ 先將第一欄單位化： $$ \|a1\|=2,\qquad q1=\frac{a1}{2}. $$ 計算第二欄在 $q1$ 方向上的投影係數： $$ r{12}=q1^Ta2=4. $$ 因此第二欄的正交分量為 $$ u2=a2-r{12}q1 =\begin{bmatrix}1\-1\-1\1\end{bmatrix}, \qquad \|u2\|=2, \qquad q2=\frac{u2}{2}. $$ 接著計算第三欄在 $q1$ 方向上的投影係數： $$ r{13}=q1^Ta3 =\frac{1}{2}(5+0+2+3) =5. $$ 這已經顯示 $R$ 中有一個元素是 $5$。其餘係數為

Question 39

$7$ is not in the $R$ matrix. (A) True. (B) False.

Accepted Answer

核心觀念 QR 分解將矩陣寫成 $A=QR$，其中 $Q$ 的欄向量互相正交且為單位向量，$R$ 為上三角矩陣。以 Gram–Schmidt 正交化計算時，$R$ 的元素為 $r{ij}=qi^{T}aj$（$i\le j$）；採用正對角線慣例時，$r{jj}$ 是正交化後向量的長度。 解題方法 令原矩陣的三個欄向量為 $a1,a2,a3$。依序正交化： $$ a1=\begin{bmatrix}1\1\1\1\end{bmatrix}, \qquad \|a1\|=2, \qquad q1=\frac12\begin{bmatrix}1\1\1\1\end{bmatrix}. $$ 第二欄在 $q1$ 方向的投影係數為 $$ r{12}=q1^Ta2=4. $$ 扣除投影後， $$ u2=a2-r{12}q1 =\begin{bmatrix}1\-1\-1\1\end{bmatrix}, \qquad \|u2\|=2, \qquad q2=\frac12\begin{bmatrix}1\-1\-1\1\end{bmatrix}. $$ 第三欄的投影係數為

Question 40

$9$ is not in the $R$ matrix. (A) True. (B) False.

Accepted Answer

核心觀念 QR 分解將矩陣 $A$ 寫成 $A=QR$，其中 $Q$ 的欄向量互相正交且長度為 $1$，而 $R$ 是上三角矩陣。使用 Gram–Schmidt 正交化，可依序求出 $Q$ 的欄向量，並計算 $$ r{ij}=qi^{T}aj \quad (i\le j), $$ 其中 $aj$ 是 $A$ 的第 $j$ 欄。 解題方法 令 $A$ 的三個欄向量為 $$ a1= \begin{bmatrix}1\1\1\1\end{bmatrix}, \qquad a2= \begin{bmatrix}3\1\1\3\end{bmatrix}, \qquad a3= \begin{bmatrix}5\0\2\3\end{bmatrix}. $$ 先將 $a1$ 單位化： $$ r{11}=\|a1\|=2, \qquad q1=\frac{a1}{2} =\frac12 \begin{bmatrix}1\1\1\1\end{bmatrix}. $$ 計算第二欄在 $q1$ 方向的投影係數與正交分量： $$ r{12}=q1^Ta2=4, \qquad u2=a2-r{12}q1 = \begin{bmatrix}1\-1\-1\1\end{bmatrix}. $$ 因此

Question 41

Four friends have been identified as suspects for an unauthorized access into a computer system. They have made statements to the investigating authorities. 小英 said “神掌 did it.” 韓總 said “I did not do it.” 神掌 said “柯 P did it.” 柯 P said “神掌 lied when he said that I did it.” If the authorities also know that exactly one is lying, who did it? (A) 小英. (B) 韓總. (C) 神掌. (D) 柯 P. (E) 郭董.

Accepted Answer

核心觀念 本題考察命題與否定命題的真值關係。若命題 $P$ 表示「柯 P 做的」，那麼「神掌說謊」就是「神掌所說的命題 $P$ 為假」，也就是 $
eg P$。 互為否定的命題 $P$ 與 $
eg P$，必定恰有一個為真、另一個為假。 解題方法 設「神掌做的」為 $S$、「韓總做的」為 $H$、「柯 P 做的」為 $K$。 四人的陳述分別是： - 小英：$S$ - 韓總：$
eg H$ - 神掌：$K$ - 柯 P：$
eg K$ 神掌與柯 P 的陳述互為否定，因此兩人之中必定恰有一人說謊。題目已知總共只有一人說謊，所以小英與韓總都必須說真話。 小英說真話，得到 $S$；韓總說真話，得到 $
eg H$。因此，做案者是神掌。此時神掌說「柯 P 做的」為假，柯 P 說「神掌說謊」為真，恰好只有神掌一人說謊，符合題意。 選項分析

Question 42

Which of the following statement is most inappropriate? (A) There exists a bijection function from $\mathbb{N}$ to $\mathbb{Z}$. (B) There exists a bijection function from $\mathbb{Z}$ to $\mathbb{Q}$. (C) There exists a bijection function from $\mathbb{Q}$ to $\mathbb{R}$. (D) There exists a bijection function from $\mathbb{N}$ to $\mathbb{Q}$. (E) There exists a bijection function from $\mathbb{Z}$ to $\mathbb{N}$.

Accepted Answer

核心觀念 「存在雙射」代表兩個集合可以一一配對，因此它們具有相同的基數。無限集合中，若元素能依序列成一列，就稱為可數無限；自然數、整數與有理數都是可數無限，而實數不可數。 本題的關鍵是判斷各集合的基數： $$ |\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|<|\mathbb{R}| $$ 解題方法 先確認 $\mathbb{N}$、$\mathbb{Z}$、$\mathbb{Q}$ 都能依序列舉。整數可排成 $0,1,-1,2,-2,\ldots$；有理數可將分子、分母依大小排列，再沿著格點的對角線依序檢查，並略過重複的分數與分母為 $0$ 的情形。如此每個有理數都會出現在序列中，因此 $\mathbb{Q}$ 可數。 實數則不可數。假設 $[0,1]$ 的實數能列成一列，將每個數寫成小數，逐位改變第 $n$ 個數的小數點後第 $n$ 位，便能構造出一個與清單中每個數至少有一位不同的新實數，造成矛盾。因此 $\mathbb{R}$ 不可數，無法與可數的 $\mathbb{Q}$ 建立雙射。 選項分析

Question 43

Which of the following statement is most inappropriate? (A) $3^{302}\bmod 5=4$. (B) $3^{302}\bmod 7=2$. (C) $3^{302}\bmod 11=9$. (D) $3^{302}\bmod 385=9$. (E) None of the above.

Accepted Answer

核心觀念 本題考模冪的循環性，以及中國剩餘定理。若 $\gcd(a,m)=1$，則 $a^n \bmod m$ 會依固定週期循環；費馬小定理指出，當 $p$ 為質數且 $p
mid a$ 時，$a^{p-1}\equiv 1\pmod p$。 此外，$5、7、11$ 兩兩互質，因此若兩數在模 $5、7、11$ 下的餘數都相同，便能合併成模 $5\cdot7\cdot11=385$ 的同餘式。 解題方法 分別利用費馬小定理化簡指數： - 模 $5$ 的週期為 $4$，而 $302\equiv 2\pmod 4$，所以 $$3^{302}\equiv 3^2\equiv 9\equiv 4\pmod 5。$$ - 模 $7$ 的週期為 $6$，而 $302\equiv 2\pmod 6$，所以 $$3^{302}\equiv 3^2\equiv 9\equiv 2\pmod 7。$$ - 模 $11$ 的週期為 $10$，而 $302\equiv 2\pmod {10}$，所以 $$3^{302}\equiv 3^2\equiv 9\pmod {11}。$$

Question 44

A binary relation $R$ on a set of 3 elements is represented by the matrix $$ \begin{bmatrix} 0&1&0\ 0&1&1\ 0&0&1 \end{bmatrix}. $$ Which of the following statement is most inappropriate? (A) $R$ is antisymmetric. (B) The reflexive closure of $R$ is $$ \begin{bmatrix} 1&1&0\ 0&1&1\ 0&0&1 \end{bmatrix}. $$ (C) The symmetric closure of $R$ is $$ \begin{bmatrix} 1&1&0\ 0&1&1\ 0&0&1 \end{bmatrix}. $$ (D) The transitive closure of $R$ is $$ \begin{bmatrix} 0&1&1\ 0&1&1\ 0&0&1 \end{bmatrix}. $$ (E) $R$ is an equivalent relation.

Accepted Answer

核心觀念 設矩陣第 $i$ 列、第 $j$ 欄的元素為 $1$，表示 $(i,j)\in R$。本題考查關係矩陣的四種性質與閉包： - 反對稱：若 $(i,j)\in R$ 且 $(j,i)\in R$，則必須有 $i=j$。 - 自反：每個 $(i,i)$ 都屬於 $R$。 - 對稱閉包：$R\cup R^{-1}$，矩陣上相當於將原矩陣與其轉置做逐項 OR。 - 傳遞閉包：加入所有由傳遞性必須補上的有序對。 - 等價關係：同時具備自反、對稱、傳遞三種性質。 題目中的關係矩陣為 $$ M= \begin{bmatrix} 0&1&0\ 0&1&1\ 0&0&1 \end{bmatrix}. $$ 因此 $$ R=\{(1,2),(2,2),(2,3),(3,3)\}. $$ 解題方法 先把矩陣轉成有序對，或直接觀察矩陣中的 $1$。依序檢查反對稱性，再分別計算自反閉包、對稱閉包與傳遞閉包。最後判斷題目是否只有一個錯誤選項。 選項分析 (A) $R$ 是反對稱關係：正確。 反對稱性只會在某兩個不同元素 $i
e j$ 同時有 $(i,j)$ 和 $(j,i)$ 時違反。矩陣中有 $(1,2)$、$(2,3)$，但沒有相反方向的 $(2,1)$、$(3,2)$，所以 $R$ 是反對稱關係。 (B) 所列矩陣是 $R$ 的自反閉包：正確。 自反閉包只需補上缺少的對角線元素。原矩陣的 $(1,1)$ 為 $0$，其餘兩個對角線元素已是 $1$，故

Question 45

Two undirected graphs $G1=(V1,E1)$ and $G2=(V2,E2)$ are isomorphic if (A) $|V1|=|V2|$. (B) $|E1|=|E2|$. (C) The number of vertices with any given degree is the same in both $G1$ and $G2$. (D) For every subgraph of $G1$, there is a subgraph of $G2$ that is isomorphic to it. (E) All of the above must hold.

Accepted Answer

核心觀念 圖同構是指存在一個頂點間的一對一對應，使相鄰關係也完全保留。若 $G1$ 與 $G2$ 同構，兩圖的結構相同，只是頂點名稱可能不同。 因此，同構圖必須具有相同的頂點數、邊數與各種度數的頂點數量；$G1$ 的每個子圖也都能在 $G2$ 中找到同構的子圖。這些都是圖同構的必要條件。 解題方法 逐項判斷各選項是否為圖同構必備的性質。只要 $G1$ 與 $G2$ 同構，對應的頂點與邊便一一配對，頂點度數也會保留；此外，同構映射限制在任一子圖上，仍會得到 $G2$ 中對應的同構子圖。因此，題列條件全都是必要條件。 選項分析 - (A) 正確。 同構映射是頂點間的一對一對應，所以 $|V1|=|V2|$。 - (B) 正確。 同構映射保留相鄰關係，因此兩圖的邊也能一一對應，故 $|E1|=|E2|$。 - (C) 正確。

Question 46

Which statement cannot be supported by Gödel’s incompleteness theorem? (A) “Graph isomorphism problem is NP-hard in general.” (B) “No single Artificial Intelligence algorithm can solve all humans’ problems”. (C) “The cloud computing platform is not capable enough to solve all big-data tasks”. (D) “There are problems which cannot be calculated by Turing machine”. (E) “We cannot expect to construct a large enough Database to support analyzing all aspects of social networks”.

Accepted Answer

核心觀念 哥德爾不完備定理（Gödel's incompleteness theorem）說：任何足以表達基本算術、且一致（不矛盾）的形式系統，都存在在系統內為真、卻無法在系統內被證明的命題。它的精神在計算理論中的對應是「存在演算法（圖靈機）無法解決的問題」（如停機問題）。因此，凡是在講「沒有一套萬能的機械程序／系統能解決所有問題」的敘述，都可以拿不完備定理作為支持（類比或延伸）；而談論某個具體問題難度等級的敘述，與它無關。 選項分析 - (A) 無法被支持（本題答案）。 「圖同構問題一般而言是 NP-hard」講的是一個可計算問題的計算複雜度分類，與「可否證明／可否計算」無關，不完備定理對 P、NP 的關係不提供任何資訊。而且這句話本身也不是已知事實——圖同構目前並未被證明是 NP-hard（一般認為不是 NP-complete）。 - (B) 可以被支持。

Question 47

Which operator or function is associative? (A) Set difference ($-$) on sets. (B) Division ($/$) on numbers. (C) Implication ($	o$) on propositions. (D) Greatest common divisor (GCD) on integers. (E) Cartesian product ($	imes$) on sets.

Accepted Answer

核心觀念 二元運算 $\star$ 若滿足結合律，必須對所有適用的 $a,b,c$ 都有 $$ (a\star b)\star c=a\star(b\star c). $$ 判斷選項時，若能找到一組反例，就足以證明該運算不具結合律；若要證明具結合律，則須說明任意三個輸入都滿足等式。 解題方法 逐項比較先算左邊兩個輸入與先算右邊兩個輸入的結果。集合差集、數字除法與命題蘊涵都可用具體反例檢驗；最大公因數則可利用「共同因數」的定義證明。 選項分析 (A) 集合差集 $-$：不具結合律。 取 $A=B=C=\{1\}$： $$ (A\setminus B)\setminus C =\varnothing\setminus\{1\} =\varnothing, $$ 但 $$ A\setminus(B\setminus C) =\{1\}\setminus\varnothing =\{1\}. $$ 兩邊不同，因此集合差集不具結合律。 (B) 除法 $/$：不具結合律。 取 $a=8,\ b=4,\ c=2$： $$ (8/4)/2=2/2=1, $$ 而 $$ 8/(4/2)=8/2=4. $$ 兩邊不相等，因此除法不具結合律。 (C) 命題蘊涵 $	o$：不具結合律。 令 $p$ 為假、$q$ 為真、$r$ 為假。此時 $$ (p	o q)	o r =(	ext{假}	o	ext{真})	o	ext{假} =	ext{真}	o	ext{假} =	ext{假}, $$ 而

Question 48

We will evaluate the time complexity of a recursive algorithm $A$ with input of $n$ items. Algorithm $A$ works as follows: when input size is $m$, the algorithm will first use $	heta(\sqrt{m})$ steps to prepare and divide the input into 4 roughly equal-size subsets; for each size $m/4$ subset, recursively call $A$; finally it uses $	heta(\sqrt{m})$ steps to merge all 4 partial results to get the final solution. What is the time complexity for this algorithm? (A) $	heta(n)$ (B) $	heta(n\log n)$ (C) $	heta(n^2)$ (D) $	heta(\sqrt{n})$ (E) $	heta(\sqrt{n\log n})$

Accepted Answer

核心觀念 本題考遞迴式的時間複雜度分析。若演算法將大小為 $n$ 的問題分成 $a$ 個、每個大小為 $n/b$ 的子問題，並花費 $f(n)$ 時間處理分割與合併，則遞迴式為 $$ T(n)=aT\left(\frac{n}{b}ight)+f(n). $$ 可用主定理比較 $f(n)$ 與 $n^{\logb a}$，判斷總時間複雜度。 解題方法 每次將問題分成 $4$ 個大小約為 $n/4$ 的子問題，因此遞迴呼叫部分為 $4T(n/4)$。準備與合併各需 $	heta(\sqrt n)$，合計仍是 $	heta(\sqrt n)$。所以 $$ T(n)=4T\left(\frac{n}{4}ight)+	heta(\sqrt n). $$ 計算主定理的比較項： $$ n^{\log4 4}=n. $$ 而非遞迴成本 $	heta(\sqrt n)=	heta(n^{1/2})$，比 $n$ 的成長速度慢；具體而言，$\sqrt n=O(n^{1-\varepsilon})$，取 $\varepsilon=1/2$，符合主定理第一種情形。因此 $$ T(n)=	heta(n). $$ 選項分析

Question 49

A restaurant provides different ways to accept reservation of ordered seats. For any individual (1 person), he/she can make reservation by email or through the web page. For any party of 2 persons, they can use phone, email, or web page to reserve. How many different ways for this restaurant to make reservation of $n$ ordered seats? (A) $\frac{5}{12}3^n+\frac{3}{4}(-1)^{n+1}$ (B) $\frac{1}{12}(-3)^n+\frac{9}{4}$ (C) $3^n+(-1)^n$ (D) $\frac{3}{2}2^n+(-1)^n$ (E) $\frac{3}{4}3^n+\frac{1}{4}(-1)^n$

Accepted Answer

核心觀念 把 $n$ 個有順序的座位由左至右安排。每次可用一種預約方式安排： - 1 個人坐 1 個座位：可用電子郵件或網頁，共 $2$ 種。 - 2 個人坐相鄰的 2 個座位：可用電話、電子郵件或網頁，共 $3$ 種。 因此，安排最前面的座位時，可能由一個單人預約占用，或由一組兩人預約占用。這類計數可用遞迴式處理。 解題方法 令 $an$ 表示安排 $n$ 個有順序座位的預約方式數。 考慮最前面的座位： - 若由 1 人預約，這個預約有 $2$ 種方式，剩下 $n-1$ 個座位有 $a{n-1}$ 種安排。 - 若由 2 人預約，這個預約有 $3$ 種方式，剩下 $n-2$ 個座位有 $a{n-2}$ 種安排。 所以對 $n\ge 2$， $$ an=2a{n-1}+3a{n-2}. $$ 初始值為 $a0=1$（沒有座位時有 1 種空安排），$a1=2$。因此 $a2=2(2)+3(1)=7$。 解遞迴式。設 $an=r^n$，代入得特徵方程： $$ r^2-2r-3=0 $$ $$ (r-3)(r+1)=0. $$

Question 50

We define that a person is “happy” if he is liked by at least 3 other people. Suppose in a group of 10 people, everyone likes at least 4 other persons. What following conclusion can be reached? (A) At least 4 persons are happy. (B) At most 6 persons are not happy. (C) It is impossible that no one is happy. (D) “like” cannot be a symmetric relation. (E) For each person, the number of persons who like him cannot be all different among 10 people.

Accepted Answer

核心觀念 把每個人視為一個頂點；若甲喜歡乙，就畫一條由甲指向乙的有向邊。每條邊代表一次「喜歡」關係，因此： - 每個人的出度是他喜歡的人數，題目給定每個人的出度至少為 $4$。 - 每個人的入度是喜歡他的人數；入度至少為 $3$ 的人就是「快樂的人」。 - 全部出度總和等於全部入度總和，兩者都等於喜歡關係的總數。 解題方法 設快樂人數為 $h$。每個人至多被另外 $9$ 人喜歡，因此全部入度總和至多為 $$ 9h+2(10-h)=20+7h, $$ 因為快樂者的入度至多為 $9$，其餘人的入度至多為 $2$。另一方面，全部出度總和至少為 $$ 10\cdot 4=40. $$ 因此 $20+7h\ge 40$，得 $h\ge 3$。這能保證至少有 $3$ 人快樂，但不能由此推出至少有 $4$ 人快樂。 若沒有任何人快樂，所有人的入度都至多為 $2$，總入度至多為 $10\cdot2=20$；然而總入度必須等於總出度，而總出度至少為 $40$，矛盾。因此一定有人快樂。 選項分析

109 年 國立中央大學資訊工程學系碩士班《離散數學與線性代數》

第 1 題1 分

第 2 題1 分

第 3 題1 分

第 4 題1 分

第 5 題1 分

第 6 題1 分

第 7 題1 分

核心觀念

解題方法

第 8 題1 分

第 9 題1 分

第 10 題1 分

第 11 題1 分

第 12 題1 分

第 13 題1 分

第 14 題1 分

第 15 題1 分

核心觀念

解題方法

第 16 題1 分

核心觀念

解題方法

第 17 題1 分

第 18 題1 分

核心觀念

解題方法

第 19 題1 分

核心觀念

解題方法

第 20 題1 分

第 21 題1 分

核心觀念

解題方法

第 22 題1 分

第 23 題1 分

第 24 題1 分

核心觀念

解題方法

第 25 題1 分

第 26 題1 分

第 27 題1 分

第 28 題1 分

第 29 題1 分

第 30 題1 分

第 31 題2 分

第 32 題2 分

核心觀念

解題方法

第 33 題2 分

第 34 題2 分

第 35 題2 分

核心觀念

解題方法

第 36 題2 分

第 37 題2 分

第 38 題2 分

第 39 題2 分

核心觀念

解題方法

第 40 題2 分

核心觀念

解題方法

第 41 題5 分

核心觀念

解題方法

選項分析

第 42 題5 分

第 43 題5 分

核心觀念

解題方法

第 44 題5 分

核心觀念

解題方法

選項分析

第 45 題5 分

第 46 題5 分

第 47 題5 分

第 48 題5 分

核心觀念

109 年國立中央大學資訊工程學系碩士班《離散數學與線性代數》