108 年 國立臺灣大學資訊工程學系碩士班《數學》

核心觀念

獨立集（independent set）是圖中一組頂點，任意兩個頂點之間都沒有邊相連。因此，本題只要找出四個兩兩不相鄰的節點。

解題方法

從圖中選取節點 $9$、$7$、$3$、$1$。逐對確認：

核心觀念

• 迴文（Palindrome）定義：對稱序列 $A = (a_1, a_2, \dots, a_n)$ 滿足對所有 $1 \le i \le n$ 均有 $a_i = a_{n-i+1}$。此對稱性決定了整個長度為 $n$ 的序列完全由前一半的位元唯一確定。
• 計數乘法原理（Rule of Product）：若一組合對象可拆解為若干個互相獨立的選擇步驟，則總組合數為各步驟可能選擇數的連乘積。
• 上取整函數（Ceiling Function）：符號 $\lceil x \rceil$ 表示大於或等於 $x$ 的最小整數。

解題方法

本題旨在求長度為 $n$ 的二進位迴文個數。在離散數學中，「二進位數（binary numbers）」在標準考題情境下通常等同於「長度為 $n$ 的二位元字串（bit strings of length $n$）」。以下給出完整嚴謹推導。

步驟一：對稱性與自由位元分析

設長度為 $n$ 的二進位序列為 $a_1 a_2 \dots a_n$，其中每一個位元 $a_i \in \{0, 1\}$。
根據迴文的鏡像對稱定義，位元必須滿足：
$a_1 = a_n, \quad a_2 = a_{n-1}, \quad \dots, \quad a_i = a_{n-i+1}$

此對稱關係表明：後半段位元 $a_{\lceil n/2 \rceil + 1}, \dots, a_n$ 的值完全被前半段對應位元所固定，無獨立選擇權。因此，整個序列的組合數僅由前半段（含奇數長度時的中央位元）的可自由選擇位元數決定。

步驟二：自由位元數計算

區分 $n$ 為偶數與奇數兩種情況：

• 當 $n$ 為偶數（即 $n = 2m$，$m \in \mathbb{N}$）：
  可自由選擇的位元為 $a_1, a_2, \dots, a_m$，自由位元數 $k = m = \frac{n}{2}$。
• 當 $n$ 為奇數（即 $n = 2m - 1$，$m \in \mathbb{N}$）：
  可自由選擇的位元為 $a_1, a_2, \dots, a_m$（包含中央位元 $a_m$），自由位元數 $k = m = \frac{n+1}{2}$。

將上述兩式統一用上取整函數表示，可得自由位元總數為：
$k = \left\lceil \frac{n}{2} \right\rceil$

步驟三：組合總數計算

由於每個自由位元均有 $2$ 種可能取值（$0$ 與 $1$），由乘法原理，長度為 $n$ 的二位元迴文字串總數為：
$2^k = 2^{\lceil n/2 \rceil}$

選項分析

本題為非選擇性計算題（計算與推導題），無選項可供逐一分析。針對離散數學考題中對於名詞「binary numbers」的兩種常見定義範疇，分析比較如下：

核心觀念

本題考查**代數分式簡化（Algebraic Fraction Simplification）與公因式約分（Factor Reduction）的基礎運算原則。在離散數學與工程數學中，處理含參數 $n$ 的分式表達式時，核心在於運用「分子相乘、分母相乘」的運算律展開，並在定義域條件允許下消去分子與分母的共同因子，將結果化簡為最簡分式（Irreducible Fraction）。此外，本題亦可延伸至組合數學中二項式係數（Binomial Coefficients）**與比例關係推導。

解題方法

標準代數推導步驟

1. 分式乘積展開
   給定等式左邊為兩分式之乘積：
   $\left(\frac{2n}{n+1}\right) \cdot \left(\frac{2n}{n}\right)$
   依分式乘法法則，分子與分子相乘，分母與分母相乘：
   $\left(\frac{2n}{n+1}\right) \cdot \left(\frac{2n}{n}\right) = \frac{2n \cdot 2n}{(n+1) \cdot n} = \frac{4n^2}{n(n+1)}$

2. 公因式消去（約分）
   在 $n \neq 0$ 的前提下，分子 $4n^2$ 與分母 $n(n+1)$ 同時含有公因式 $n$。將分子與分母同除以 $n$：
   $\frac{4n^2}{n(n+1)} = \frac{4n}{n+1}$

3. 比較係數對應解
   將化簡後的最簡分式對應至題目右式 $\frac{A}{B}$：
   $\frac{4n}{n+1} = \frac{A}{B}$
   比對兩邊之分子與分母，即得出最簡表達式下之 $A$ 與 $B$：
   $A = 4n$
   $B = n+1$

選項分析

Note on the original problem statement:
In combinatorial sum problems of this form, $\binom{n}{k}$ is the standard binomial coefficient. The expression $\left(\frac{n}{k}\right)$ and $\left(\frac{n-k}{k}\right)$ in typical NTU BME exam papers represents either plain arithmetic division/fractions or binomial coefficients written in fractional notation. However, evaluating the sum as given:

【觀念與導引】

本題考查組合數（Binomial Coefficients）與代數求和技巧。

核心觀念

這題考二階線性常係數遞迴式的特徵方程法。對

設解為 $a_n=r^n$，代入後可得特徵方程。若特徵方程有兩個相異根 $r_1,r_2$，通解為

解題方法

令 $a_n=r^n$，代入遞迴式：

除以 $r^n$，得到特徵方程：

因式分解：

所以特徵根為 $r=-1$ 與 $r=2$。因此通解為

核心觀念

本題考「隔板法」（stars and bars）：將正整數變數的固定總和轉換成非負整數變數的固定總和，再計算解的個數。

解題方法

依題目的標準設定，令 $n_i$ 為已知非負整數。由 $x_i>n_i$ 且 $x_i$ 為整數，設

則每個 $y_i$ 都是正整數，且原式變成

設 $R=r-\sum_{i=1}^{n}n_i$。將每個正整數 $y_i$ 再寫成 $y_i=z_i+1$，其中 $z_i\geq 0$，可得

依隔板法，非負整數解的個數為

核心觀念

命題 $A\to B$ 只有在 $A$ 為真、$B$ 為假時為假；其餘情況皆為真。若一個複合命題在所有真值組合下都為真，才稱為重言式（tautology）。

本題考查蘊涵命題的真值判斷，以及否定前件的推理錯誤。

解題方法

直接找出一組使整個命題為假的真值組合。外層是蘊涵，因此只要讓前件為真、後件為假即可。

令 $p=\text{假}$、$q=\text{真}$。此時：

• $p\to q$ 為真，因為蘊涵的前件 $p$ 為假。
• $\neg p$ 為真，因此 $(p\to q)\land\neg p$ 為真。
• $\neg q$ 為假。

所以整個命題的前件為真、後件為假，外層蘊涵為假。存在一組真值使命題為假，因此它不是重言式。

也可用等值變形確認：

核心觀念

本題考查子空間與張成、線性相依、基底存在所需的選擇公理、內積空間的正交基底，以及秩－零度定理。

判斷時須注意：「基底」通常指代數基底，也就是每個向量都能寫成基底向量的有限線性組合。在無限維內積空間中，正交集的線性張成與其閉包不同。

解題方法

逐項檢查定義與定理的適用範圍：子空間對線性組合封閉；線性相依只保證至少某個向量可由其餘向量表示；任意向量空間存在基底涉及選擇公理；無限維內積空間的正交基底要分清代數張成與稠密張成；秩－零度定理則可透過核空間與有限維補空間的直和分解確認。

選項分析

第一項：正確。

$S\subseteq U$，且 $U$ 是子空間，因此 $U$ 包含 $S$ 中向量的所有有限線性組合。由張成的定義，

第二項：錯誤。

線性相依只表示存在一組不全為零的係數，使某個有限線性組合等於零；它不表示每個向量都能由其餘向量表示。

取非零向量 $u$，令 $R=\{u,0\}$。$R$ 線性相依，但當 $x=u$ 時，

所以 $u\notin\operatorname{span}(R\setminus\{u\})$。因此「每個」向量都滿足該條件並不成立。

第三項：錯誤。

「每個向量空間都有基底」是與選擇公理相關的命題；在通常的集合論框架中，任意向量空間都存在基底等價於選擇公理。僅有「公理系統一致」並不足以保證這個命題成立，因此不能從任意一致的集合論公理系統都推出每個向量空間有基底。

第四項：錯誤。

對一般的無限維內積空間，不能保證存在代數基底形式的正交基底。以 $C[0,1]$ 為例，賦予內積

核心觀念

本題考查齊次線性方程組的解空間、矩陣的可逆性、秩與轉置的關係，以及共軛轉置對行列式的影響。

• 齊次方程組 $Ax=0$ 的解集合是 $A$ 的零空間。若 $A$ 的元素都是有理數，解集合對有理數倍與向量加法封閉，因此是 $\mathbb{Q}$ 上的向量空間。
• 矩陣與其轉置有相同的秩；複數矩陣與其共軛轉置也有相同的秩。
• 對可逆矩陣，零度為 $0$。
• 共軛轉置的行列式滿足 $\det(A^*)=\overline{\det(A)}$，其中上橫線表示複共軛。

解題方法

逐項檢查定義與公式。判斷敘述是否必然成立時，特別留意「可逆」是否要求方陣，以及行列式遇到複共軛後是否仍等於原值。

選項分析

1. 正確。 設解集合為
   $S=\{x\in\mathbb{R}^n:Ax=0\},$
   且 $A$ 為有理矩陣。若 $x,y\in S$，則 $A(x+y)=Ax+Ay=0$；對任意 $q\in\mathbb{Q}$，也有 $A(qx)=qAx=0$。因此 $S$ 對有理數純量封閉，是 $\mathbb{Q}$ 上的向量空間。即使把變數限為有理數，解集合仍是 $\mathbb{Q}$ 上的向量空間。

核心觀念

本題考查有理數域與複數域上的特徵空間、實對稱矩陣的譜定理、複對稱與 Hermitian 矩陣的差異，以及酉相似下跡的保持性。

若 $A$ 是複數正規矩陣，即 $A^*A=AA^*$，則由譜定理可知 $A$ 能酉對角化；而 $A^*$ 的特徵值是 $A$ 特徵值的共軛數，對應的特徵向量相同。若 $A$ 是實對稱矩陣，則所有特徵值皆為實數，且可正交對角化。

解題方法

逐項檢查各敘述使用的矩陣條件是否足以套用相應定理。特別注意：

• 「可對角化」只要求存在由特徵向量組成的基底。
• 正規矩陣的 $A$ 與 $A^*$ 共享特徵向量，但對應的特徵值會取共軛。
• 複對稱條件 $A^t=A$ 不等於 Hermitian 條件 $A^*=A$。
• 酉等價矩陣的 $A^*A$ 與 $B^*B$ 具有相同的跡。

選項分析

（1）正確。
若 $\mathbb{Q}^n$ 是 $A$ 的特徵空間直和，表示每個向量都能寫成各特徵空間向量的和，且不同特徵空間的和為直和。因此，取各特徵空間的基底合併後，即得到 $\mathbb{Q}^n$ 的一組基底，而其中每個向量都是 $A$ 的特徵向量。以這組基底表示 $A$，矩陣即為對角矩陣，所以 $A$ 可對角化。

（2）正確。
由 $A^*A=AA^*$，$A$ 是正規矩陣，故可寫成

其中 $U$ 為酉矩陣。因此

兩矩陣有相同的特徵向量；若 $Av=\lambda v$，則 $A^*v=\overline{\lambda}v$。

核心觀念

所有從 $\mathbb{R}^3$ 到 $\mathbb{R}^2$ 的線性轉換，都能用一個 $2\times 3$ 矩陣表示。若

則 $T$ 的矩陣為

因此，這個向量空間等同於所有 $2\times 3$ 實矩陣所成的向量空間，維度為 $2\cdot 3=6$。

解題方法

令 $e_1=(1,0)$、$e_2=(0,1)$ 為 $\mathbb{R}^2$ 的標準基底。對 $i=1,2$、$j=1,2,3$，定義線性轉換 $T_{ij}:\mathbb{R}^3\to\mathbb{R}^2$：

這些轉換各自只取出輸入向量的一個座標，並放到輸出的其中一個座標。例如，

六個轉換對應的矩陣為