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

本題考查有向圖的 Euler 路徑與 Euler 迴路定理。一個有向圖存在 Euler 迴路（Eulerian circuit）的充要條件是：圖是連通的（忽略方向後），且所有頂點的入度（in-degree）等於出度（out-degree）。如果存在一個頂點的入度比出度多一，且另一個頂點的出度比入度多一，其餘頂點入度等於出度，則存在 Euler 路徑（Eulerian path）。

我們需要檢查圖 (A) 到 (E) 的入度與出度。

(A)
頂點 1: in=1, out=1
頂點 2: in=1, out=1
頂點 3: in=1, out=1
頂點 4: in=1, out=1
頂點 5: in=1, out=1
頂點 6: in=1, out=1
頂點 7: in=1, out=1
頂點 8: in=1, out=1
所有頂點的入度等於出度，且圖是連通的。因此，圖 (A) 是 Eulerian。

(B)
頂點 1: in=1, out=1
頂點 2: in=1, out=1
頂點 3: in=1, out=1
頂點 4: in=1, out=1
頂點 5: in=1, out=1
頂點 6: in=1, out=1
頂點 7: in=1, out=1
頂點 8: in=1, out=1
所有頂點的入度等於出度，且圖是連通的。因此，圖 (B) 是 Eulerian。

(C)
頂點 1: in=1, out=1
頂點 2: in=1, out=1
頂點 3: in=1, out=1
頂點 4: in=1, out=1
頂點 5: in=1, out=1
頂點 6: in=1, out=1
頂點 7: in=1, out=1
頂點 8: in=1, out=1
所有頂點的入度等於出度，且圖是連通的。因此，圖 (C) 是 Eulerian。

核心觀念

本題考查命題邏輯中的：

• 真值指派：為變數 $w,x,y$ 分別指定真（$1$）或假（$0$）。
• 合取 $\land$：所有條件同時成立。
• 析取 $\lor$：至少一個條件成立。
• 滿足真值指派：代入後使整個命題為真的變數配置。

題目中的命題為

解題方法

逐一分析三個合取項。每個合取項都完整指定了 $w,x,y$ 的真假，因此各自對應一組真值指派。

第一項：

要求

即真值指派為

第二項：

要求

本題考查集合論中的二元關係數量計算。

設集合 $X = \{A, B, C, D\}$，集合 $Y = \{1, 2, 3, 4, 5\}$。
一個從集合 $X$ 到集合 $Y$ 的二元關係 $R$ 是笛卡兒積 $X \times Y$ 的一個子集。
笛卡兒積 $X \times Y$ 的元素個數為 $|X| \times |Y|$。
$|X| = 4$
$|Y| = 5$
所以，$|X \times Y| = 4 \times 5 = 20$。

一個集合的子集個數為 $2^k$，其中 $k$ 是集合的元素個數。
因此，從 $X$ 到 $Y$ 的二元關係的個數 $N$ 等於 $X \times Y$ 的子集個數。
$N = 2^{|X \times Y|} = 2^{20}$。

現在我們需要計算 $N \pmod{13}$，也就是 $2^{20} \pmod{13}$。
我們可以利用費馬小定理（Fermat's Little Theorem），如果 $p$ 是一個質數，對於任意整數 $a$ 不被 $p$ 整除，則有 $a^{p-1} \equiv 1 \pmod{p}$。
在這裡，$p = 13$（質數），$a = 2$。

本題考查線性齊次遞迴關係式的求解。
給定的遞迴關係式為 $a_n = -3a_{n-1} + 10a_{n-2}$，初始條件為 $a_0 = 3$ 和 $a_1 = 2$。

首先，寫出遞迴關係式的特徵方程式（Characteristic Equation）：
$r^2 = -3r + 10$
$r^2 + 3r - 10 = 0$

接著，解這個二次方程式來找出特徵根：
$(r+5)(r-2) = 0$
所以，特徵根為 $r_1 = 2$ 和 $r_2 = -5$。

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

現在，我們利用初始條件來求解常數 $c_1$ 和 $c_2$。
當 $n=0$ 時，$a_0 = 3$:
$3 = c_1 (2)^0 + c_2 (-5)^0$
$3 = c_1 (1) + c_2 (1)$
$c_1 + c_2 = 3$ (方程式 1)

當 $n=1$ 時，$a_1 = 2$:
$2 = c_1 (2)^1 + c_2 (-5)^1$
$2 = 2c_1 - 5c_2$ (方程式 2)

本題考查遞迴關係式的生成函數（Generating Function）及其部分分式分解。

首先，我們需要建立遞迴關係式的生成函數。
假設生成函數為 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。
給定的遞迴關係式是 $a_n = -3a_{n-1} + 10a_{n-2}$，初始條件是 $a_0 = 3$ 和 $a_1 = 2$。
這個關係式對 $n \ge 2$ 成立。

將遞迴關係式乘以 $x^n$ 並對 $n \ge 2$ 求和：
$\sum_{n=2}^{\infty} a_n x^n = \sum_{n=2}^{\infty} (-3a_{n-1}) x^n + \sum_{n=2}^{\infty} (10a_{n-2}) x^n$

左邊：
$\sum_{n=2}^{\infty} a_n x^n = A(x) - a_0 - a_1 x = A(x) - 3 - 2x$

右邊第一項：
$\sum_{n=2}^{\infty} (-3a_{n-1}) x^n = -3x \sum_{n=2}^{\infty} a_{n-1} x^{n-1} = -3x \sum_{k=1}^{\infty} a_k x^k$ (令 $k = n-1$)
$= -3x (A(x) - a_0) = -3x (A(x) - 3) = -3xA(x) + 9x$

右邊第二項：
$\sum_{n=2}^{\infty} (10a_{n-2}) x^n = 10x^2 \sum_{n=2}^{\infty} a_{n-2} x^{n-2} = 10x^2 \sum_{m=0}^{\infty} a_m x^m$ (令 $m = n-2$)
$= 10x^2 A(x)$

將這些組合起來：
$A(x) - 3 - 2x = (-3xA(x) + 9x) + 10x^2 A(x)$

整理 $A(x)$ 的項：
$A(x) - 3 - 2x = -3xA(x) + 9x + 10x^2 A(x)$
$A(x) + 3xA(x) - 10x^2 A(x) = 3 + 2x + 9x$
$A(x) (1 + 3x - 10x^2) = 3 + 11x$

所以，生成函數是：
$A(x) = \frac{3 + 11x}{1 + 3x - 10x^2}$

分母的特徵方程式是 $1 + 3x - 10x^2 = 0$。
我們知道遞迴關係式的特徵根是 $r_1=2$ 和 $r_2=-5$。
分母的根與特徵根的倒數有關。
令 $1 + 3x - 10x^2 = 0$。
如果 $r$ 是特徵方程式 $r^2 + 3r - 10 = 0$ 的根，則 $1/r$ 是 $1+3x-10x^2$ 的根（乘以 $x^2$ 後）。
也就是說，分母的根是 $1/2$ 和 $1/(-5) = -1/5$。
所以，分母可以寫成 $k(x - 1/2)(x - (-1/5)) = k(x - 1/2)(x + 1/5)$。

核心觀念

本題考查「隔板法」（Stars and Bars）以及不等式轉等式的技巧。

對於 $r$ 個非負整數變數滿足

其解的數量為

原題是不等式

可加入一個「剩餘量」變數，將不等式轉為等式。

解題方法

令

因為原本滿足

所以 $x_5$ 是非負整數，即 $x_5\ge 0$。

因此原問題等價於求下列方程式的非負整數解數：

共有 $5$ 個非負整數變數，利用隔板法，解的數量為

核心觀念

向量組 $\{v_1,\ldots,v_k\}$ 線性獨立的定義是：若

只有 $c_1=\cdots=c_k=0$ 這組解，則向量組線性獨立；若存在不全為零的係數使線性組合等於零，則線性相依。

多項式可以依照各次方項的係數表示成向量；矩陣可以逐項比較；在 $\mathbb{R}^3$ 中，將向量排成矩陣後，可用行列式判斷：行列式非零，三個向量線性獨立；行列式為零，則線性相依。

解題方法與選項分析

(A) 線性獨立

設三個多項式的線性組合為零：

依照 $x^3,x^2,x,1$ 各項比較係數，得到

由 $3a=0$ 得 $a=0$；代入 $-a-3c=0$ 得 $c=0$；再由 $b+c=0$ 得 $b=0$。因此只有零解，三個多項式線性獨立。

(B) 線性相依

第一個矩陣是單位矩陣 $I$，第二個矩陣是 $-I$，兩者相加為零：

這已構成係數不全為零的線性組合，因此整組線性相依。

(C) 線性獨立

設三個矩陣的線性組合為零：

核心觀念

本題考查內積空間中的兩個基本概念：

1. 以多項式基底表示內積時，利用 Gram 矩陣

   $$A=\bigl[\langle b_i,b_j\rangle\bigr].$$

2. 向量或函數沿某一方向的 Fourier coefficient：

   $$c=\frac{\langle f,v\rangle}{\langle v,v\rangle}, \qquad v\neq 0.$$

   此係數使得 $cv$ 成為 $f$ 在 $v$ 所張成子空間上的正交投影。

（A）求內積矩陣 $A$

令

並記

若

則

矩陣 $A$ 的第 $i,j$ 個元素為

由於 $b_i=x^{i-1}$、$b_j=x^{j-1}$，因此

逐項計算得

所以

核心觀念

題目要求「所有特徵值的乘積」。由特徵值與行列式的基本定理：

因此不必逐一求出特徵值，只要求出 $\det(A)$ 即可。

矩陣 $A$ 的元素可統一表示為

提出每一列共同的因子 $a$，可寫成

其中

故

解題方法

對 $R$ 由最後一列開始，依序施行列運算

這些列運算都不會改變行列式。

以第 $k$ 列為例，當 $j<k$ 時，

當 $j=k$ 時，

本題考查矩陣函數的特徵值。
如果 $\lambda$ 是矩陣 $A$ 的一個特徵值，那麼對於一個多項式 $f(x)$， $f(\lambda)$ 是矩陣 $f(A)$ 的一個特徵值。
要找到 $f(A)$ 的最大特徵值，我們需要先找到矩陣 $A$ 的所有特徵值，然後對每個特徵值計算 $f(\lambda)$，最後找出最大的 $f(\lambda)$ 值。

矩陣 $A$ 是：
$A = \begin{pmatrix} 2 & -1 & 2 & 0 \\ -1 & 0 & 2 & 5 \\ 0 & 0 & 4 & -1 \\ 0 & 0 & 2 & 1 \end{pmatrix}$
這是一個 $4 \times 4$ 的矩陣。
注意到矩陣 $A$ 具有一個塊對角結構：
$A = \begin{pmatrix} B & C \\ 0 & D \end{pmatrix}$
其中 $B = \begin{pmatrix} 2 & -1 \\ -1 & 0 \end{pmatrix}$, $C = \begin{pmatrix} 2 & 0 \\ 5 & 2 \end{pmatrix}$, $D = \begin{pmatrix} 4 & -1 \\ 2 & 1 \end{pmatrix}$, $0 = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$。

一個塊對角矩陣的特徵值是其對角塊矩陣的特徵值的並集。
所以，我們需要找到矩陣 $B$ 和 $D$ 的特徵值。

首先，找矩陣 $B$ 的特徵值。
特徵方程式為 $\det(B - \lambda I) = 0$。
$\det \begin{pmatrix} 2-\lambda & -1 \\ -1 & -\lambda \end{pmatrix} = (2-\lambda)(-\lambda) - (-1)(-1) = -2\lambda + \lambda^2 - 1 = \lambda^2 - 2\lambda - 1 = 0$
使用二次方程式求根公式：
$\lambda = \frac{-(-2) \pm \sqrt{(-2)^2 - 4(1)(-1)}}{2(1)} = \frac{2 \pm \sqrt{4 + 4}}{2} = \frac{2 \pm \sqrt{8}}{2} = \frac{2 \pm 2\sqrt{2}}{2} = 1 \pm \sqrt{2}$
所以，$B$ 的特徵值是 $\lambda_{B1} = 1 + \sqrt{2}$ 和 $\lambda_{B2} = 1 - \sqrt{2}$。

接下來，找矩陣 $D$ 的特徵值。
特徵方程式為 $\det(D - \mu I) = 0$。
$\det \begin{pmatrix} 4-\mu & -1 \\ 2 & 1-\mu \end{pmatrix} = (4-\mu)(1-\mu) - (-1)(2) = 4 - 4\mu - \mu + \mu^2 + 2 = \mu^2 - 5\mu + 6 = 0$
因式分解：
$(\mu - 2)(\mu - 3) = 0$
所以，$D$ 的特徵值是 $\mu_{D1} = 2$ 和 $\mu_{D2} = 3$。

矩陣 $A$ 的特徵值是 $B$ 和 $D$ 的特徵值的並集：
$\{\lambda_1, \lambda_2, \lambda_3, \lambda_4\} = \{1+\sqrt{2}, 1-\sqrt{2}, 2, 3\}$。

現在，我們需要計算 $f(\lambda)$ 對於這些特徵值。
$f(x) = x^4 - 7x^3 + 13x^2 - 6x + 1$。

我們將計算 $f(\lambda)$ 對於 $\lambda = 1+\sqrt{2}, 1-\sqrt{2}, 2, 3$。
首先，注意 $B$ 的特徵值 $\lambda$ 滿足 $\lambda^2 - 2\lambda - 1 = 0$。
這意味著 $\lambda^2 = 2\lambda + 1$。