113 年國立陽明交通大學資訊工程學系碩士班《線性代數與離散數學》考古題與詳解

Question 1

Solve the following puzzle.

一名醫護人員說：「醫院裡的醫護人員，包括我在內，總共是 16 名醫生與護士，並且下面四條狀況都成立。並且如果把我排除不計的話，下面四條狀況仍然都成立。」

護士多於醫生。
男醫生多於男護士。
男護士多於女護士。
至少有一位女醫生。

請問說話的人是甚麼性別和職稱？

注意：每個人要麼是男性，要麼是女性，不可以又是男又是女。每個人要麼是醫生，要麼是護士，不可以既是護士又是醫生。

Accepted Answer

核心觀念

把人數設成四個變數，先用四條狀況與總數 16 解出唯一的人員組成，再用「把說話者排除後仍然成立」判斷說話者屬於哪一類。

設女護士 $a$ 人、男護士 $b$ 人、男醫生 $c$ 人、女醫生 $d$ 人， $a+b+c+d=16$ 。四條狀況：

護士多於醫生： $a+b>c+d$
男醫生多於男護士： $c>b$
男護士多於女護士： $b>a$
至少有一位女醫生： $d\ge1$

解題方法

第一步：解出人員組成。

由 (1) 與總數 16，護士至少 9 人： $a+b\ge9$ ，醫生至多 7 人： $c+d\le7$ 。

由 (4)， $c\le7-d\le6$ ；由 (2)， $b\le c-1\le5$ ；由 (3)， $a\le b-1\le4$ 。所以 $a+b\le9$ 。

結合 $a+b\ge9$ ，每個不等式都必須取等號：

a=4,\quad b=5,\quad c=6,\quad d=1

檢查： $9>7$ 、 $6>5$ 、 $5>4$ 、 $1\ge1$ ，總數 16，四條都成立，而且這是唯一解。

Question 2

Consider the following non-decreasing sequence of natural numbers:
$a_1,a_2,a_3,\ldots; 1,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,\ldots$

Note that there are exactly $k^2$ occurrences of $k$ . Define a function $f(n)$ as the largest integer $m$ such that $a_m=n$ . For example, $f(3)=14$ and $f(4)=30$ . What is $f(f(n))$ ?

Accepted Answer

核心觀念

數列依非遞減順序排列，且每個正整數 $k$ 恰好出現 $k^2$ 次。因此， $f(n)$ 是數列中所有值不大於 $n$ 的項數，也就是前 $n$ 個平方數的總和：

f(n)=\sum_{k=1}^{n}k^2 =\frac{n(n+1)(2n+1)}{6}.

解題方法

先由平方和公式求出 $f(n)$ ，再把 $f(n)$ 代入同一公式。

令

q=f(n)=\frac{n(n+1)(2n+1)}{6}.

因此

f(f(n))=f(q) =\frac{q(q+1)(2q+1)}{6}.

代回 $q$ ，得到

Question 3

Find all non-negative integers $a$ and $b$ such that $\sqrt{a}+\sqrt{b}=\sqrt{2009}$.

Accepted Answer

核心觀念 利用整數的平方因數分解：每個正整數都可唯一寫成「平方自由整數 × 完全平方數」。若 $a,b0$ 且 $ab$ 是完全平方數，則 $a$ 與 $b$ 的平方自由部分相同。 解題方法 先處理 $a=0$ 或 $b=0$ 的情況：若 $a=0$，原式給出 $b=2009$；若 $b=0$，則 $a=2009$。 接著考慮 $a,b0$。將原式平方： $$ a+b+2\sqrt{ab}=2009 $$ 因此 $$ \sqrt{ab}=\frac{2009-a-b}{2} $$ 右側是有理數。因為 $ab$ 是整數，且其平方根為有理數，所以 $ab$ 必為完全平方數。 設 $a=d u^2$、$b=d v^2$，其中 $d$ 是共同的平方自由部分，$u,v$ 為正整數。代回原式： $$ (u+v)\sqrt d=\sqrt{2009}=7\sqrt{41} $$

Question 4

The Goldbach's conjecture says, “every even integer greater than 2 is a sum of two prime numbers.” Please translate Goldbach's conjecture into a logical formula using $\exists$, $\land$, $\lor$, $
eg$, $	o$, and $\leftrightarrow$, and the four basic integer arithmetic operators ($+$, $-$, $	imes$, $\div$). Note that $\div$ is integer division; for example, $5\div2=2$.

Accepted Answer

核心觀念 Goldbach 猜想表示：每個大於 $2$ 的偶數，都能寫成兩個質數的和。題目只要求使用存在量詞 $\exists$，因此可把「每個」改寫成「不存在一個反例」： 不存在大於 $2$ 的偶數，無法表示成兩個質數的和。 還需要用整數除法表達「偶數」與「質數」。以下量詞的範圍皆為整數，並使用題目中的大小關係符號 $$、$<$。 解題方法 對正整數 $n$，條件 $$ n=2	imes(n\div 2) $$ 恰好表示 $n$ 是偶數：偶數除以 $2$ 沒有餘數；奇數的整數除法結果乘回 $2$，則會比原數小 $1$。 對正整數 $p1$，若存在整數 $d$ 滿足 $1<d<p$，且 $$ p=d	imes(p\div d), $$ 便表示 $d$ 整除 $p$，所以 $p$ 不是質數。

Question 5

A bit string is a string of 0 and 1 digits. For instance, $0011010110$ is a bit string of length 10. How many bit strings of length 10 contain either five consecutive 1's or five consecutive 0's?

Accepted Answer

核心觀念 利用補集計數：先計算長度為 $10$、沒有連續 $5$ 個相同數字的位串，再從全部 $2^{10}$ 個位串中扣除。 每個位串都能唯一分解成一段一段的「連續相同數字區段」，稱為連續段。例如 $0011010110$ 的連續段長度為 $2,1,2,1,1,2,1$。相鄰連續段的數字必定交替，因此只要計算連續段長度的組合數，再乘上第一段可選的 $0$ 或 $1$，就能得到位串數量。 解題方法 要避免出現連續 $5$ 個相同數字，每個連續段的長度只能是 $1,2,3,4$。令 $cn$ 表示將 $n$ 拆成若干個 $1$ 至 $4$ 之間的正整數之方法數，並令 $c0=1$。 第一個連續段長度可能為 $1,2,3,4$，所以對 $n\geq 1$： $$ cn=c{n-1}+c{n-2}+c{n-3}+c{n-4}, $$ 其中負下標的 $ck$ 視為 $0$。依序計算：

Question 6

What is the number of paths from vertices $m$ to $n$?

Accepted Answer

核心觀念 每條路徑都由「向右」與「向上」兩種步伐組成。若總共需要向右走 $r$ 步、向上走 $u$ 步，路徑數就是將這 $r+u$ 步中的 $u$ 個向上步安排位置： $$ \binom{r+u}{u}=\binom{r+u}{r} $$ 解題方法 圖中 $m$ 位於左下角、$n$ 位於右上角；格線間共有 $6$ 欄、$4$ 列，因此從 $m$ 到 $n$ 必須向右走 $6$ 步、向上走 $4$ 步。

Question 7

What is the number of paths from vertices $m$ to $n$ that do not go through vertex $x$?

Accepted Answer

核心觀念 每條路徑由向右與向上組成。若需向右走 $r$ 步、向上走 $u$ 步，路徑總步數為 $r+u$；從中選出 $u$ 個位置安排向上步，路徑數為 $$ \binom{r+u}{u}. $$ 解題方法 圖中從 $m$ 到 $n$ 的格點路徑需向右走 $6$ 步、向上走 $4$ 步；頂點 $x$ 位於從 $m$ 向右 $3$ 步、向上 $2$ 步的位置。先算全部路徑，再扣除經過 $x$ 的路徑。 全部路徑數為 $$ \binom{6+4}{4}=\binom{10}{4}=210. $$

Question 8

Let $P$ be the set of all vertices in the above graph. Define a binary relation $R$ on $P$ such that $(p,q)\in R$ if we need either one unit to the right or one unit upward to move from vertex $p$ to $q$. Is $(P,R)$ a partially ordered set? Why or why not?

Accepted Answer

核心觀念 偏序集 $(P,R)$ 的關係 $R$ 必須同時滿足： - 自反性：對每個 $p\in P$，$(p,p)\in R$。 - 反對稱性：若 $(p,q)\in R$ 且 $(q,p)\in R$，則 $p=q$。 - 傳遞性：若 $(p,q)\in R$ 且 $(q,r)\in R$，則 $(p,r)\in R$。 解題方法 圖中是由格點構成的矩形網格，從一個頂點到另一個頂點只相隔一格向右或一格向上時，兩點才屬於 $R$。因此，檢查它是否為偏序，只要逐一檢驗上述三項條件。

Question 9

How many different results can we get?

Accepted Answer

核心觀念 拓樸排序必須保留偏序中的先後關係：若 $x<y$，則 $x$ 必須排在 $y$ 前面。Hasse 圖中位置較低的元素小於沿連線向上可達的元素；沒有偏序關係的元素，先後順序可自由安排。 解題方法 圖（a）共有 $e,f,g,h,i$ 五個元素，兩條由下往上的鏈為 $$ e<g<i,\qquad f<h<i. $$ 左右兩條鏈之間沒有額外的先後限制。 由於 $e,f,g,h$ 都必須排在 $i$ 前面，因此 $i$ 固定排在最後。問題便化為：將兩個有序序列 $(e,g)$ 與 $(f,h)$ 交錯排列，同時維持 $e$ 在 $g$ 前、$f$ 在 $h$ 前。 在前四個位置中，選出兩個位置依序放入 $e,g$；剩下兩個位置依序放入 $f,h$。每一組位置選擇恰好對應一種合法排序，因此共有

Question 10

How many different results can we get?

Accepted Answer

核心觀念 拓樸排序必須保留偏序中的先後關係：若 $x<y$，則 $x$ 必須排在 $y$ 前面。Hasse 圖中位置較低的元素小於沿連線向上可達的元素；沒有偏序關係的元素，先後順序可自由安排。 解題方法 圖（a）共有 $e,f,g,h,i$ 五個元素，兩條由下往上的鏈為 $$ e<g<i,\qquad f<h<i. $$ 左右兩條鏈之間沒有額外的先後限制。 由於 $e,f,g,h$ 都必須排在 $i$ 前面，因此 $i$ 固定排在最後。問題便化為：將兩個有序序列 $(e,g)$ 與 $(f,h)$ 交錯排列，同時維持 $e$ 在 $g$ 前、$f$ 在 $h$ 前。 在前四個位置中，選出兩個位置依序放入 $e,g$；剩下兩個位置依序放入 $f,h$。每一組位置選擇恰好對應一種合法排序，因此共有

Question 11

Suppose that we already have the following theorem.

If $G$ is a connected planar simple graph with $e$ edges and $v$ vertices, where $v\geq3$ , then $e\leq3v-6$ .

Using this theorem to prove that if $G$ is a connected planar simple graph with at least three vertices, then $G$ has a vertex of degree not exceeding five.

Accepted Answer

核心觀念 使用握手定理：圖中所有頂點的度數總和等於邊數的兩倍， $$ \sum{u\in V(G)}\deg(u)=2e. $$ 再將此式與題目給定的平面簡單圖邊數上界 $e\leq 3v-6$ 結合，限制頂點度數的平均值。 解題方法 由題目給定的定理， $$ e\leq 3v-6. $$ 因此，利用握手定理可得平均度數

Question 12

Let $$A=\begin{bmatrix}0&-3&3&9\2&3&-1&1\1&3&-2&2\4&10&-5&1\end{bmatrix}.$$ Find $A^{-1}=?$

Accepted Answer

核心觀念 可逆矩陣 $A$ 的逆矩陣 $A^{-1}$ 滿足 $AA^{-1}=I$。使用 Gauss–Jordan 消去法，將增廣矩陣 $[A\mid I]$ 做列運算，直到左半部化為單位矩陣；此時右半部就是 $A^{-1}$。 解題方法 將 $A$ 與 $I$ 合併成增廣矩陣，依序進行列運算。先交換第 1、3 列，再消去第 1 欄： $$ \left[ \begin{array}{rrrr|rrrr} 1&3&-2&2&0&0&1&0\ 0&-3&3&-3&0&1&-2&0\ 0&-3&3&9&1&0&0&0\ 0&-2&3&-7&0&0&0&1 \end{array} ight]. $$ 接著令 $R3\leftarrow R3-R2$、$R4\leftarrow R4-\frac23R2$，並將第 2 列與第 3 列分別除以 $-3$ 與 $12$：

Question 13

Let $$A=\begin{bmatrix}0&-3&3&9\2&3&-1&1\1&3&-2&2\4&10&-5&1\end{bmatrix}.$$ Find the $PA=LU$ factorization for $A$, where $P$ is a permutation matrix, $L$ is a lower triangular matrix with unit diagonal, and $U$ is an upper triangular matrix.

Accepted Answer

核心觀念 高斯消去時若遇到主元（pivot）為 $0$，就必須交換列；把所有列交換預先集中成一個排列矩陣 $P$，就能寫成 $PA=LU$：$L$ 是單位下三角（對角線為 $1$，下方存消去用的乘數 $\ell{ij}$），$U$ 是消去後的上三角矩陣。 $$ A=\begin{bmatrix}0&-3&3&9\2&3&-1&1\1&3&-2&2\4&10&-5&1\end{bmatrix} $$ 解題方法 找出需要的列交換。 - 第 1 欄：$a{11}=0$，必須換列。與第 2 列交換（$R1\leftrightarrow R2$）。 - 照原順序繼續消去會發現：第 3 列在第 2 步後變成 $(0,0,0,6)$，第 3 欄主元為 $0$，必須與第 4 列交換（$R3\leftrightarrow R4$）。 所以 $P$ 把列順序排成 $(2,1,4,3)$： $$ P=\begin{bmatrix}0&1&0&0\1&0&0&0\0&0&0&1\0&0&1&0\end{bmatrix},\qquad PA=\begin{bmatrix}2&3&-1&1\0&-3&3&9\4&10&-5&1\1&3&-2&2\end{bmatrix} $$ 對 $PA$ 做不需換列的消去。 第 1 步（主元 $2$）： - $\ell{21}=0/2=0$ - $\ell{31}=4/2=2$：$R3-2R1=(0,4,-3,-1)$ - $\ell{41}=1/2$：$R4-	frac12R1=(0,	frac32,-	frac32,	frac32)$ 第 2 步（主元 $-3$）：

Question 14

Given 4 points $(t,b)$: $(0,20)$, $(1,0)$, $(2,0)$, and $(3,0)$, what is the sum of squared error $\lVert e\rVert^2$ if we fit the closest quadratic polynomial $b=C+Dt+Et^2$ by the least square approximation?

Accepted Answer

核心觀念

最小平方法是選擇係數，使殘差平方和最小。令設計矩陣的第 $i$ 列為 $[1,t_i,t_i^2]$ ，則模型可寫成

\mathbf b=X\boldsymbol\beta,\qquad \boldsymbol\beta= \begin{bmatrix}C\\D\\E\end{bmatrix}.

最小平方解滿足正規方程 $X^{\mathsf T}X\boldsymbol\beta=X^{\mathsf T}\mathbf b$ ；其殘差向量與 $X$ 的每一欄都正交。

解題方法

四個資料點的 $t$ 值為 $0,1,2,3$ ，因此

X= \begin{bmatrix} 1&0&0\\ 1&1&1\\ 1&2&4\\ 1&3&9 \end{bmatrix}, \qquad \mathbf b= \begin{bmatrix}20\\0\\0\\0\end{bmatrix}.

計算各欄的乘積和：

X^{\mathsf T}X= \begin{bmatrix} 4&6&14\\ 6&14&36\\ 14&36&98 \end{bmatrix}, \qquad X^{\mathsf T}\mathbf b= \begin{bmatrix}20\\0\\0\end{bmatrix}.

所以正規方程為

Question 15

Prove that if a square matrix $A$ is invertible, then $(A^{-1})^T=(A^T)^{-1}$ .

(Please leave it blank if you don't know the correct answer, or you will get at most minus 5 points (until questions 7, 8, and 9 are 0 points) for the wrong answer. For example, if you get questions 7, 8, and 9 wrong, you will get 0 points for them.)

Accepted Answer

核心觀念 矩陣 $B$ 是方陣 $A$ 的反矩陣，若且唯若 $$ AB=BA=I. $$ 此外，轉置會反轉矩陣乘法的順序： $$ (AB)^T=B^TA^T. $$ 解題方法 因為 $A$ 可逆，所以 $$ AA^{-1}=I,\qquad A^{-1}A=I. $$ 將兩式分別取轉置，並使用 $(AB)^T=B^TA^T$： $$ (AA^{-1})^T=(A^{-1})^TA^T=I^T=I, $$

Question 16

Find the eigenvalues of $A$.

Accepted Answer

核心觀念

三角矩陣的特徵值就是其對角線上的元素。這是因為特徵值 $\lambda$ 滿足特徵方程

\det(A-\lambda I)=0,

而三角矩陣的行列式等於對角線元素的乘積。

解題方法

矩陣 $A$ 是上三角矩陣，因此可直接由對角線讀出特徵值。也可計算特徵多項式驗證：

Question 17

Find the corresponding eigenvectors of $A$.

Accepted Answer

核心觀念 特徵向量 $v$ 必須是非零向量，且滿足 $Av=\lambda v$，等價於 $$ (A-\lambda I)v=0. $$ 因此，先由 $A$ 的特徵值逐一求解齊次方程組，即可得到對應的特徵向量。由於 $A$ 是上三角矩陣，其特徵值為對角線元素 $1,2,3$。 解題方法 令 $v=(x,y,z)^T$，分別解 $(A-\lambda I)v=0$。 當 $\lambda=1$ 時， $$ A-I= \begin{bmatrix} 0&1&1\ 0&1&1\ 0&0&2 \end{bmatrix}. $$ 方程組給出 $y+z=0$、$y+z=0$、$2z=0$，因此 $z=0$、$y=0$，而 $x$ 可任意取非零值。故 $$ E1=\operatorname{span}\left\{ \begin{bmatrix}1\0\0\end{bmatrix} ight\}. $$ 當 $\lambda=2$ 時， $$ A-2I= \begin{bmatrix} -1&1&1\ 0&0&1\ 0&0&1 \end{bmatrix}. $$ 方程組給出 $-x+y+z=0$、$z=0$，所以 $y=x$。故

Question 18

Find the eigenvalues of $B$.

Accepted Answer

核心觀念 矩陣 $B$ 的區塊結構可寫成 Kronecker 積： $$ B= \begin{bmatrix} 2A&2A\ A&3A \end{bmatrix} = \begin{bmatrix} 2&2\ 1&3 \end{bmatrix}\otimes A. $$ 若 $C$ 的特徵值為 $\mui$，而 $A$ 的特徵值為 $\lambdaj$，則 $C\otimes A$ 的特徵值為所有乘積 $\mui\lambdaj$。這可由特徵向量直接看出：若 $Cx=\mui x$ 且 $Ay=\lambdaj y$，則 $$ (C\otimes A)(x\otimes y) =(Cx)\otimes(Ay) =(\mui\lambdaj)(x\otimes y). $$ 解題方法 令 $$ C=\begin{bmatrix}2&2\1&3\end{bmatrix}, \qquad B=C\otimes A. $$

Question 19

Let $$C=\begin{bmatrix}9&3&-6\3&4&1\-6&1&7\end{bmatrix}=LL^T,$$ where $L$ is a $3	imes3$ lower triangular matrix. Please find $L$.

Accepted Answer

核心觀念 這題考下三角矩陣的 Cholesky 分解。對稱矩陣若可寫成 $C=LL^T$，其中 $L$ 為下三角矩陣，通常取所有對角元素非負；逐項比較 $C$ 與 $LL^T$，即可求出 $L$ 的元素。 解題方法 設 $$ L= \begin{bmatrix} \ell{11}&0&0\ \ell{21}&\ell{22}&0\ \ell{31}&\ell{32}&\ell{33} \end{bmatrix}. $$ 由 $C=LL^T$ 的對角元素開始計算： $$ \ell{11}^2=9 \quad\Longrightarrow\quad \ell{11}=3. $$ 這裡採用標準 Cholesky 分解的非負對角線慣例。接著比較第一欄的非對角元素： $$ \ell{21}\ell{11}=3 \quad\Longrightarrow\quad \ell{21}=1, $$ $$ \ell{31}\ell{11}=-6 \quad\Longrightarrow\quad \ell{31}=-2. $$ 再由第二列的對角元素求 $\ell{22}$： $$ \ell{21}^2+\ell{22}^2=4 \quad\Longrightarrow\quad 1+\ell{22}^2=4 \quad\Longrightarrow\quad \ell{22}=\sqrt{3}. $$

Question 20

Let $$D=\begin{bmatrix}4&0&0\0&1&i\0&-i&1\end{bmatrix}=F^HF,$$ where $F$ is a $3	imes3$ Hermitian matrix. Please find $F$.

Accepted Answer

核心觀念 因為 $F$ 是 Hermitian 矩陣，所以 $F^H=F$，題目條件等價於 $$ F^2=D. $$ 也就是求 $D$ 的 Hermitian 平方根。Hermitian 矩陣的特徵值皆為實數；若 $F^2=D$，則 $F$ 與 $D$ 具有相同的特徵向量，而 $F$ 在每個特徵方向上的特徵值，平方後必須等於 $D$ 對應的特徵值。 解題方法 將 $D$ 寫成一個 $1	imes1$ 區塊與一個 $2	imes2$ 區塊： $$ D= \begin{bmatrix} 4&0\ 0&B \end{bmatrix}, \qquad B= \begin{bmatrix} 1&i\ -i&1 \end{bmatrix}. $$ 先計算 $B$ 的平方： $$ B^2= \begin{bmatrix} 1&i\ -i&1 \end{bmatrix} \begin{bmatrix} 1&i\ -i&1 \end{bmatrix} = \begin{bmatrix} 2&2i\ -2i&2 \end{bmatrix} =2B. $$ 因此 $$ \left(\frac{B}{\sqrt{2}}ight)^2=B. $$ 而 $4$ 的實數平方根為 $\pm2$。所以對任意 $\varepsilon,\delta\in\{1,-1\}$，矩陣

113 年 國立陽明交通大學資訊工程學系碩士班《線性代數與離散數學》

第 1 題5 分

核心觀念

解題方法

第 2-(a) 題5 分

核心觀念

解題方法

第 2-(b) 題5 分

第 3-(a) 題5 分

第 3-(b) 題5 分

核心觀念

解題方法

第 4-(a) 題3 分

第 4-(b) 題4 分

第 4-(c) 題4 分

第 5-(a) 題2 分

第 5-(b) 題4 分

第 6 題8 分

核心觀念

解題方法

第 7-(a) 題6 分

第 7-(b) 題6 分

核心觀念

解題方法

第 8 題8 分

核心觀念

解題方法

第 9 題5 分

核心觀念

解題方法

第 10-(a) 題5 分

核心觀念

解題方法

第 10-(b) 題5 分

第 10-(c) 題5 分

核心觀念

解題方法

第 11 題5 分

第 12 題5 分

核心觀念

解題方法

其他考古題

113 年陽明交通大學的其他科目

陽明交通大學《線性代數與離散數學》其他年度

其他學校的資工系考古題

113 年國立陽明交通大學資訊工程學系碩士班《線性代數與離散數學》