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

這是一題計數問題。
首先，我們需要確定集合 $\{ "A", "B" \}^3$ 的元素個數。這個集合包含所有長度為 3 的序列，其中每個元素可以從 $\{ "A", "B" \}$ 中選擇。因此，元素個數為 $2^3 = 8$。
接著，我們需要確定集合 $\{1,2,3\}$ 的元素個數，這個集合有 3 個元素。
一個從 $\{ "A", "B" \}^3$ 到 $\{1,2,3\}$ 的函數，相當於為 $\{ "A", "B" \}^3$ 中的每一個元素指定一個 $\{1,2,3\}$ 中的輸出值。
由於 $\{ "A", "B" \}^3$ 有 8 個元素，而對於每一個元素，我們有 3 種可能的輸出選擇，因此總共有 $3^8$ 個這樣的函數。
所以，$z = 3^8$。
接下來，我們計算 $z \pmod 7$。
$3^1 \equiv 3 \pmod 7$

這是一題邏輯敘述的真值表計算問題。
我們需要計算有多少個變數的組合 (satisfying assignments) 能使給定的邏輯敘述為真。
給定的邏輯敘述為：
$L = ( \neg w \land x \land \neg y ) \lor ( \neg w \land x \land y ) \lor ( \neg w \land \neg x \land y ) \lor ( w \land \neg x \land \neg z )$

我們有四個變數：$w, x, y, z$。每個變數有兩個可能的值（真或假，或 1 或 0）。因此，總共有 $2^4 = 16$ 種可能的變數組合。
我們需要逐一檢查這 16 種組合，看哪些組合能使 $L$ 為真。

我們可以先簡化邏輯敘述：
注意到前三項都有 $(\neg w \land \dots)$。
第一項和第二項都是 $(\neg w \land x \land \dots)$。
$(\neg w \land x \land \neg y ) \lor ( \neg w \land x \land y ) = \neg w \land x \land (\neg y \lor y) = \neg w \land x \land \text{True} = \neg w \land x$。

所以，原敘述可以簡化為：
$L = ( \neg w \land x ) \lor ( \neg w \land \neg x \land y ) \lor ( w \land \neg x \land \neg z )$

現在，我們來檢查 16 種組合。為了方便，我們用 0 代表 False，1 代表 True。
變數順序：$w, x, y, z$

1. $w=0$:

   • $x=0$:
     • $y=0$:
       • $z=0$: $(\neg 0 \land 0) \lor (\neg 0 \land \neg 0 \land 0) \lor (0 \land \neg 0 \land \neg 0) = (1 \land 0) \lor (1 \land 1 \land 0) \lor (0 \land 1 \land 1) = 0 \lor 0 \lor 0 = 0$ (False)
       • $z=1$: $(\neg 0 \land 0) \lor (\neg 0 \land \neg 0 \land 0) \lor (0 \land \neg 0 \land \neg 1) = (1 \land 0) \lor (1 \land 1 \land 0) \lor (0 \land 1 \land 0) = 0 \lor 0 \lor 0 = 0$ (False)
     • $y=1$:
       • $z=0$: $(\neg 0 \land 0) \lor (\neg 0 \land \neg 0 \land 1) \lor (0 \land \neg 0 \land \neg 0) = (1 \land 0) \lor (1 \land 1 \land 1) \lor (0 \land 1 \land 1) = 0 \lor 1 \lor 0 = 1$ (True) -> (0,0,1,0)
       • $z=1$: $(\neg 0 \land 0) \lor (\neg 0 \land \neg 0 \land 1) \lor (0 \land \neg 0 \land \neg 1) = (1 \land 0) \lor (1 \land 1 \land 1) \lor (0 \land 1 \land 0) = 0 \lor 1 \lor 0 = 1$ (True) -> (0,0,1,1)
   • $x=1$:
     • $y=0$:
       • $z=0$: $(\neg 0 \land 1) \lor (\neg 0 \land \neg 1 \land 0) \lor (0 \land \neg 1 \land \neg 0) = (1 \land 1) \lor (1 \land 0 \land 0) \lor (0 \land 0 \land 1) = 1 \lor 0 \lor 0 = 1$ (True) -> (0,1,0,0)
       • $z=1$: $(\neg 0 \land 1) \lor (\neg 0 \land \neg 1 \land 0) \lor (0 \land \neg 1 \land \neg 1) = (1 \land 1) \lor (1 \land 0 \land 0) \lor (0 \land 0 \land 0) = 1 \lor 0 \lor 0 = 1$ (True) -> (0,1,0,1)
     • $y=1$:
       • $z=0$: $(\neg 0 \land 1) \lor (\neg 0 \land \neg 1 \land 1) \lor (0 \land \neg 1 \land \neg 0) = (1 \land 1) \lor (1 \land 0 \land 1) \lor (0 \land 0 \land 1) = 1 \lor 0 \lor 0 = 1$ (True) -> (0,1,1,0)
       • $z=1$: $(\neg 0 \land 1) \lor (\neg 0 \land \neg 1 \land 1) \lor (0 \land \neg 1 \land \neg 1) = (1 \land 1) \lor (1 \land 0 \land 1) \lor (0 \land 0 \land 0) = 1 \lor 0 \lor 0 = 1$ (True) -> (0,1,1,1)

2. $w=1$:

   • $x=0$:
     • $y=0$:
       • $z=0$: $(\neg 1 \land 0) \lor (\neg 1 \land \neg 0 \land 0) \lor (1 \land \neg 0 \land \neg 0) = (0 \land 0) \lor (0 \land 1 \land 0) \lor (1 \land 1 \land 1) = 0 \lor 0 \lor 1 = 1$ (True) -> (1,0,0,0)

這是一題數論問題，計算歐拉 φ 函數。
歐拉 φ 函數 $\Phi(n)$ 表示小於或等於 $n$ 且與 $n$ 互質的正整數的個數。
計算歐拉 φ 函數的公式為：
若 $n$ 的質因數分解為 $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$，
則 $\Phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right)$
或者 $\Phi(n) = p_1^{k_1-1}(p_1-1) p_2^{k_2-1}(p_2-1) \cdots p_r^{k_r-1}(p_r-1)$。

首先，我們需要對 90 進行質因數分解。
$90 = 9 \times 10$
$9 = 3^2$
$10 = 2 \times 5$
所以，$90 = 2^1 \times 3^2 \times 5^1$。
質因數是 2, 3, 5。

使用第一個公式：
$\Phi(90) = 90 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{5}\right)$

這是一題線性齊次遞迴關係的求解問題。
給定的遞迴關係為 $a_n = -a_{n-1} + 12a_{n-2}$。
其特徵方程式為：$r^2 = -r + 12$。
整理後得到：$r^2 + r - 12 = 0$。
對此二次方程式進行因式分解：
$(r+4)(r-3) = 0$。
特徵根為 $r_1 = 3$ 和 $r_2 = -4$。

由於特徵根是兩個相異的實數，遞迴關係的通解形式為：
$a_n = c_1 (r_1)^n + c_2 (r_2)^n$
$a_n = c_1 (3)^n + c_2 (-4)^n$。

接下來，我們利用初始條件 $a_0 = 3$ 和 $a_1 = 2$ 來求解常數 $c_1$ 和 $c_2$。

當 $n=0$ 時：
$a_0 = c_1 (3)^0 + c_2 (-4)^0$
$3 = c_1 (1) + c_2 (1)$
$3 = c_1 + c_2$ (方程式 1)

當 $n=1$ 時：
$a_1 = c_1 (3)^1 + c_2 (-4)^1$
$2 = 3c_1 - 4c_2$ (方程式 2)

核心觀念

本題考查：

• 色數：將相鄰頂點塗成不同顏色所需的最少顏色數。
• 最大獨立集：任兩頂點皆不相鄰的頂點集合，其最大大小記為 $\alpha(G)$。
• Euler 圖：連通且每個頂點的度數皆為偶數。
• Hamilton 圖：存在一個經過每個頂點恰好一次的閉迴路。

由圖可見，頂點 $\{1,4,5,7,9\}$ 兩兩相鄰，形成完全圖 $K_5$。

解題方法

1. 色數

由於 $\{1,4,5,7,9\}$ 形成 $K_5$，其中每個頂點都互相相鄰，因此至少需要 $5$ 種顏色：

其餘頂點可使用這 $5$ 種顏色配置，不需增加第 $6$ 種顏色，因此：

2. 最大獨立集

在完全圖 $K_5$ 中，任意兩個頂點皆相鄰，所以獨立集中至多取其中一個頂點。

在其餘頂點 $\{2,3,6,8\}$ 中，$2$ 與 $6$ 相鄰、$3$ 與 $6$ 相鄰，因此最多可取 $\{2,3,8\}$，共 $3$ 個頂點。

故獨立集大小至多為：

例如：

中的任意兩點皆不相鄰，因此確實存在大小為 $4$ 的獨立集。故：

核心觀念

本題考查最小平方問題。對線性方程組 $Ax=b$，若方程組有解，則存在 $x$ 使得

因此殘差範數 $\|Ax-b\|$ 的最小值為 $0$，其平方也是 $0$。

題目給出的增廣矩陣有 $4$ 個未知數欄位，因此應將未知向量視為 $x\in\mathbb C^4$；題目所寫的 $\mathbb C^3$ 與矩陣欄數不一致，以下依增廣矩陣判定為四個未知數。

解題方法

由增廣矩陣可得方程組

令自由變數

由第一式，

由第二式，

代入第三式：

整理得

核心觀念

本題考查：

1. 子空間的張成。
2. 直和的必要條件。
3. 子空間包含關係的判斷。

若

則依直和定義，必須同時滿足

且

因此，只要證明 $V\not\subseteq W$，即可直接判定不存在符合條件的子空間 $U$，無須再計算正交條件。

解題方法

先將 $S$ 中的向量觀察為：

對 $S$ 中每個向量 $(x_1,x_2,x_3,x_4)$，前三個分量的和皆為 $0$：

由於「前三個分量和為 $0$」的向量集合本身是子空間，因此 $W$ 中任意向量都滿足

換言之，

這是一道關於有限體上的多項式問題。
給定的體是 $F = \{0, 1, 2\}$，其運算為模 3 的加法和乘法。
多項式為 $p(x) = a + bx + cx^2$，其中 $a, b, c \in F$。
條件是 $p(i) = i^3 + 2$ 對於每個 $i \in F$ 成立。
我們需要求解係數 $(a, b, c)$。

首先，我們計算 $F$ 中的元素的立方值，以及 $i^3+2$ 的值。
模 3 的運算：
$0^3 = 0$
$1^3 = 1$
$2^3 = 8 \equiv 2 \pmod 3$

計算 $i^3 + 2 \pmod 3$：
當 $i=0$: $0^3 + 2 = 0 + 2 = 2$。
當 $i=1$: $1^3 + 2 = 1 + 2 = 3 \equiv 0 \pmod 3$。
當 $i=2$: $2^3 + 2 = 2 + 2 = 4 \equiv 1 \pmod 3$。

現在我們將這些值代入 $p(i) = i^3 + 2$：

1. 對於 $i=0$:
   $p(0) = a + b(0) + c(0)^2 = a$
   所以，$a = 0^3 + 2 = 2$。
   我們得到 $a=2$。

2. 對於 $i=1$:
   $p(1) = a + b(1) + c(1)^2 = a + b + c$
   所以，$a + b + c = 1^3 + 2 = 0$。
   我們已經知道 $a=2$，代入得到：
   $2 + b + c = 0$
   $b + c = -2 \equiv 1 \pmod 3$。 (方程式 1)

核心觀念

本題使用以下觀念：

1. 凱萊–漢米爾頓定理：若 $f(x)$ 是 $T$ 的特徵多項式，則
   $f(T)=0.$

2. 若特徵多項式在 $\mathbb{C}$ 上有互異根，則 $T$ 可對角化。

3. 對角化後，$p(T)$ 的秩可由多項式 $p(x)$ 在 $T$ 的特徵值上的取值判定。

解題方法

令

則題目中的算子為 $S=p(T)$。

由

以及凱萊–漢米爾頓定理，

因此計算 $p(x)$ 對 $f(x)$ 的餘式即可。

由 $x^3=2x^2-1$，可得

代回 $p(x)$：

\begin{align*}
p(x)
&=(12x^2-4x-7)-2(7x^2-2x-4)\
&\quad -(4x^2-x-2)+4(2x^2-1)-x^2-2x\
&=x^2-x-1.
\end{align*}

所以

接著分解特徵多項式：

二次因式 $x^2-x-1$ 的兩根為

三個特徵值互異，因此 $T$ 可對角化。設其特徵值為

核心觀念

本題使用奇異值分解與 Moore–Penrose 廣義逆的性質。

若線性映射 $T$ 的所有非零奇異值為

則其偽逆 $T^\dagger$ 的非零奇異值為

又因為矩陣與其伴隨矩陣具有相同的奇異值，所以 $(T^\dagger)^*$ 的非零奇異值仍為

因此所求乘積為

解題方法

題目給出

因此每個非零奇異值都要加 $1$：

其乘積為