115 年 國立臺灣大學資訊工程學系人工智慧研究所《數學》

核心觀念

本題考察二維格點隨機漫步的「可達狀態」計數。每一步的位移為

$$(1,1),\ (1,-1),\ (-1,1),\ (-1,-1),\ (0,0).$$

因此，每一步中兩個座標的奇偶性必定同時改變，或同時不變。從 $(0,0)$ 出發後，任意可達狀態 $(i,j)$ 都必須滿足：

1. $|i|\le n$ 且 $|j|\le n$；
2. $i$ 與 $j$ 具有相同奇偶性。

---

解題方法

經過 $n$ 步後，每個座標的絕對值都不可能超過 $n$，因此所有可能狀態位於正方形

$$-n\le i\le n,\qquad -n\le j\le n.$$

在整數範圍 $-n,-n+1,\ldots,n$ 中，若 $i,j$ 奇偶性不同，則不可能到達；若兩者奇偶性相同，則一定可以到達。

例如：

• $(i,j)$ 皆為偶數時，可利用對角線移動互相抵消，並搭配停留步；
• $(i,j)$ 皆為奇數時，使用奇數次的對角線移動，再搭配必要的停留步；

此題為一個組合數學問題，涉及函數的數量計算，並要求計算結果對 11 取餘數。

首先，我們需要確定集合 $A$ 的大小。
集合 $A$ 是所有從 $\{1,2,3,4,5\}$ 到 $\{1,2,3,4,5,6\}$ 的函數所構成的集合。
設 $S_1 = \{1,2,3,4,5\}$，其大小為 $|S_1| = 5$。
設 $S_2 = \{1,2,3,4,5,6\}$，其大小為 $|S_2| = 6$。
一個從 $S_1$ 到 $S_2$ 的函數，意味著對於 $S_1$ 中的每一個元素，都有一個對應到 $S_2$ 中的元素。
對於 $S_1$ 中的第一個元素 $1$，有 $|S_2|=6$ 種可能的映射。
對於 $S_1$ 中的第二個元素 $2$，有 $|S_2|=6$ 種可能的映射。
...
對於 $S_1$ 中的第五個元素 $5$，有 $|S_2|=6$ 種可能的映射。
因此，從 $S_1$ 到 $S_2$ 的函數總數為 $|S_2|^{|S_1|} = 6^5$。
所以，集合 $A$ 的大小是 $|A| = 6^5$。

接下來，題目說有 $N$ 個函數是從集合 $A$ 到集合 $\{1,2,3,4,5,6,7,8,9\}$。
設 $S_3 = \{1,2,3,4,5,6,7,8,9\}$，其大小為 $|S_3| = 9$。
我們有 $N$ 個函數，這些函數是從 $A$ 到 $S_3$ 的。
這表示，對於集合 $A$ 中的每一個元素（即集合 $A$ 中的每一個函數），都有一個對應到 $S_3$ 中的元素。
因此，$N$ 是從 $A$ 到 $S_3$ 的函數的總數。
$N = |S_3|^{|A|} = 9^{|A|} = 9^{6^5}$。

我們需要計算 $N \pmod{11}$，即 $9^{6^5} \pmod{11}$。
根據費馬小定理 (Fermat's Little Theorem)，如果 $p$ 是一個質數，那麼對於任何整數 $a$，$a^p \equiv a \pmod{p}$。
如果 $a$ 不是 $p$ 的倍數，則 $a^{p-1} \equiv 1 \pmod{p}$。
在這裡，$p=11$ 是一個質數。
所以，我們需要計算 $9^{6^5} \pmod{11}$。
根據費馬小定理，$9^{11-1} = 9^{10} \equiv 1 \pmod{11}$。
因此，我們只需要計算指數 $6^5$ 對 $10$ 取餘數。

計算 $6^5 \pmod{10}$：
$6^1 \equiv 6 \pmod{10}$
$6^2 = 36 \equiv 6 \pmod{10}$
$6^3 = 6 \times 6 \equiv 36 \equiv 6 \pmod{10}$

此題要求解一個三階線性齊次遞迴關係式，並給定初始條件。

遞迴關係式為 $a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}$。
為了求解此遞迴關係式，我們需要找到其特徵方程式。
特徵方程式為：
$r^3 - 6r^2 + 11r - 6 = 0$

我們需要找到這個三次方程式的根。可以嘗試代入一些簡單的整數值，如 $\pm 1, \pm 2, \pm 3, \pm 6$。
令 $P(r) = r^3 - 6r^2 + 11r - 6$。
$P(1) = 1^3 - 6(1)^2 + 11(1) - 6 = 1 - 6 + 11 - 6 = 0$。
所以 $r=1$ 是其中一個根。這意味著 $(r-1)$ 是 $P(r)$ 的一個因式。

我們可以用多項式長除法或綜合除法來找到其他因式。
使用綜合除法，用根 $1$ 去除係數 $1, -6, 11, -6$:

1 | 1  -6   11  -6
  |    1   -5   6
  ----------------
    1  -5    6   0

得到的商是 $r^2 - 5r + 6$。
所以，特徵方程式可以分解為 $(r-1)(r^2 - 5r + 6) = 0$。

現在我們需要分解二次方程式 $r^2 - 5r + 6 = 0$。
我們可以因式分解為 $(r-2)(r-3) = 0$。
所以，二次方程式的根是 $r=2$ 和 $r=3$。

特徵方程式的根是 $r_1 = 1$, $r_2 = 2$, $r_3 = 3$。
由於三個根是相異的，遞迴關係式的通解形式為：
$a_n = c_1(1)^n + c_2(2)^n + c_3(3)^n$
$a_n = c_1 + c_2 2^n + c_3 3^n$

接下來，我們使用給定的初始條件來求解常數 $c_1, c_2, c_3$。
初始條件：$a_0 = 1$, $a_1 = 2$, $a_2 = 2$。

當 $n=0$:
$a_0 = c_1 + c_2 2^0 + c_3 3^0 = c_1 + c_2 + c_3 = 1$ (方程式 1)

當 $n=1$:
$a_1 = c_1 + c_2 2^1 + c_3 3^1 = c_1 + 2c_2 + 3c_3 = 2$ (方程式 2)

當 $n=2$:
$a_2 = c_1 + c_2 2^2 + c_3 3^2 = c_1 + 4c_2 + 9c_3 = 2$ (方程式 3)

核心觀念

題目中的「above recurrence equation」未提供，因此缺少遞迴式、初始條件與選項，無法唯一決定特定的部分分式答案。

一般而言，若數列滿足 $k$ 階線性遞迴式

$$a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}, \qquad n\ge k,$$

並定義普通生成函數

$$A(x)=\sum_{n=0}^{\infty}a_nx^n,$$

則其分母由特徵多項式所對應的生成函數分母決定：

$$Q(x)=1-c_1x-c_2x^2-\cdots-c_kx^k.$$

---

解題方法

將遞迴式乘上 $x^n$，對 $n\ge k$ 加總：

$$\sum_{n=k}^{\infty}a_nx^n = c_1\sum_{n=k}^{\infty}a_{n-1}x^n +\cdots+ c_k\sum_{n=k}^{\infty}a_{n-k}x^n.$$

利用

$$A(x)=a_0+a_1x+a_2x^2+\cdots,$$

整理各項後得到

$$A(x)\left(1-c_1x-c_2x^2-\cdots-c_kx^k\right)=P(x),$$

其中 $P(x)$ 由初始值 $a_0,a_1,\ldots,a_{k-1}$ 決定。因此

$$A(x)=\frac{P(x)} {1-c_1x-c_2x^2-\cdots-c_kx^k}.$$

若分母可分解為

$$Q(x)=\prod_{i=1}^{r}(1-\lambda_i x)^{m_i},$$

則生成函數的部分分式分解形式為

$$A(x) = \sum_{i=1}^{r} \left( \frac{C_{i,1}}{1-\lambda_i x} +\frac{C_{i,2}}{(1-\lambda_i x)^2} +\cdots+ \frac{C_{i,m_i}}{(1-\lambda_i x)^{m_i}} \right).$$

若所有根互異，即 $m_i=1$，則可簡化為

此題為一個組合數學問題，要求計算不定方程非負整數解的數量，並計算結果對 11 取餘數。

問題是計算 $x_1 + x_2 + \dots + x_{12} \le 6$ 的非負整數解的數量。
為了方便計算，我們引入一個鬆弛變數 $s \ge 0$。
原不等式可以轉換為方程：
$x_1 + x_2 + \dots + x_{12} + s = 6$
其中 $x_1, x_2, \dots, x_{12}, s$ 都是非負整數。

這是一個標準的「星星與隔板」問題。
我們有 6 個「星星」（代表數值 6），需要將它們分配到 $12+1=13$ 個變數（$x_1, \dots, x_{12}, s$）中。
這相當於在 13 個位置之間放置 $13-1 = 12$ 個「隔板」。

然而，更直接的理解是，我們有 6 個單位，需要將它們分配給 13 個箱子。
這相當於從 13 個箱子中，選擇 6 個箱子來放置星星，允許重複選擇（因為每個箱子可以有多個星星）。
這等價於從 $n=13$ 個選項中，選取 $k=6$ 個，允許重複，順序不重要。
這可以用組合數公式 $\binom{n+k-1}{k}$ 或 $\binom{n+k-1}{n-1}$ 來計算。

在這裡，$n = 13$ (變數的數量)，$k = 6$ (總和)。
所以，解的數量 $N$ 為：
$N = \binom{13+6-1}{6} = \binom{18}{6}$

或者，我們也可以理解為，我們有 6 個星星和 $13-1=12$ 個隔板，總共有 $6+12=18$ 個位置，我們需要選擇 6 個位置放星星（或者選擇 12 個位置放隔板）。
$N = \binom{18}{6} = \binom{18}{12}$

現在我們需要計算 $\binom{18}{6} \pmod{11}$。
$\binom{18}{6} = \frac{18!}{6!(18-6)!} = \frac{18!}{6!12!} = \frac{18 \times 17 \times 16 \times 15 \times 14 \times 13}{6 \times 5 \times 4 \times 3 \times 2 \times 1}$

我們需要計算這個值對 11 取餘數。
直接計算 $\binom{18}{6}$：
$6 \times 3 \times 1 = 18$。 18 可以約掉。
$5 \times 2 = 10$。
$4$。
$\frac{18 \times 17 \times 16 \times 15 \times 14 \times 13}{18 \times 5 \times 4 \times 2 \times 1} = \frac{17 \times 16 \times 15 \times 14 \times 13}{5 \times 4 \times 2 \times 1}$
$16 / 4 = 4$
$15 / 5 = 3$
$14 / 2 = 7$
所以，$\binom{18}{6} = 17 \times 4 \times 3 \times 7 \times 13$
$= 17 \times 12 \times 91$
$= 204 \times 91$
$204 \times 91 = 204 \times (90 + 1) = 18360 + 204 = 18564$。

所以，$N = 18564$。

現在計算 $N \pmod{11}$：
$18564 \pmod{11}$。
使用除法：
$18564 \div 11$
$18564 = 11 \times 1000 + 7564$
$7564 = 11 \times 600 + 964$
$964 = 11 \times 80 + 84$
$84 = 11 \times 7 + 7$
所以 $18564 = 11 \times 1000 + 11 \times 600 + 11 \times 80 + 11 \times 7 + 7$
$18564 = 11 \times (1000 + 600 + 80 + 7) + 7$
$18564 = 11 \times 1687 + 7$
所以，$18564 \equiv 7 \pmod{11}$。

或者使用模運算直接計算：

核心觀念

本題是齊次線性方程組

$$A\mathbf{x}=\mathbf{0}$$

其中

$$A= \begin{bmatrix} 1&2&-2\\ 2&-1&\lambda\\ 3&\lambda&1 \end{bmatrix}.$$

齊次線性方程組具有非零解的充要條件是係數矩陣不可逆，也就是

$$\det(A)=0.$$

---

解題方法

計算係數矩陣的行列式：

$$\begin{aligned} \det(A) &= 1\begin{vmatrix} -1&\lambda\\ \lambda&1 \end{vmatrix} -2\begin{vmatrix} 2&\lambda\\ 3&1 \end{vmatrix} -2\begin{vmatrix} 2&-1\\ 3&\lambda \end{vmatrix}\\[6pt] &=1(-1-\lambda^2)-2(2-3\lambda)-2(2\lambda+3)\\ &=-1-\lambda^2-4+6\lambda-4\lambda-6\\ &=-\lambda^2+2\lambda-11. \end{aligned}$$

令行列式為零：

核心觀念

本題考查矩陣次方與特徵向量的應用。矩陣 $A$ 對向量

$$\mathbf{1}=\begin{pmatrix}1\\1\end{pmatrix}$$

的作用為：

$$A\mathbf{1} = \begin{pmatrix}1&4\\3&2\end{pmatrix} \begin{pmatrix}1\\1\end{pmatrix} = \begin{pmatrix}5\\5\end{pmatrix} = 5\mathbf{1}.$$

因此，$\mathbf{1}$ 是 $A$ 的特徵向量，對應特徵值為 $5$。由此可得：

$$A^{2004}\mathbf{1}=5^{2004}\mathbf{1}.$$

解題方法

設

$$A^{2004}= \begin{pmatrix}a&b\\c&d\end{pmatrix}.$$

題目所求的分子為矩陣所有元素的總和：

$$a+b+c+d = \begin{pmatrix}1&1\end{pmatrix} A^{2004} \begin{pmatrix}1\\1\end{pmatrix}.$$

利用上述特徵向量關係：

$$A^{2004} \begin{pmatrix}1\\1\end{pmatrix} = 5^{2004} \begin{pmatrix}1\\1\end{pmatrix}.$$

所以

此題要求求解一個線性系統 $Ax=b$ 的最小範數最小平方法解。

線性系統為：
$\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$
寫成方程組是：
$x_1 + x_2 = 1$
$0x_1 + 0x_2 = 1$

第二個方程 $0 = 1$ 是矛盾的，這意味著該線性系統是無解的。
對於無解的系統 $Ax=b$，我們尋找最小平方法解，即最小化 $\|Ax-b\|^2$。
最小平方法解 $\hat{x}$ 滿足正規方程 (normal equations)：
$A^T A \hat{x} = A^T b$

首先計算 $A^T A$ 和 $A^T b$。
$A^T = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}$。

$A^T A = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 1 \cdot 1 + 0 \cdot 0 & 1 \cdot 1 + 0 \cdot 0 \\ 1 \cdot 1 + 0 \cdot 0 & 1 \cdot 1 + 0 \cdot 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$。

$A^T b = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \cdot 1 + 0 \cdot 1 \\ 1 \cdot 1 + 0 \cdot 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$。

正規方程變為：
$\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$
這兩個方程是相同的：$x_1 + x_2 = 1$。
這意味著存在無窮多個最小平方法解。

題目要求的是「最小範數最小平方法解」(minimum-norm least-squares solution)。
這意味著在所有滿足 $x_1+x_2=1$ 的解中，我們需要找到範數 $\|x\| = \sqrt{x_1^2 + x_2^2}$ 最小的那一個。

我們需要最小化 $x_1^2 + x_2^2$ 使得 $x_1+x_2=1$。
從 $x_1+x_2=1$，我們可以得到 $x_2 = 1-x_1$。
代入目標函數：$f(x_1) = x_1^2 + (1-x_1)^2 = x_1^2 + 1 - 2x_1 + x_1^2 = 2x_1^2 - 2x_1 + 1$。
為了找到最小值，我們對 $x_1$ 求導並令其為零：
$f'(x_1) = 4x_1 - 2 = 0$
$4x_1 = 2 \implies x_1 = 1/2$。

當 $x_1 = 1/2$ 時， $x_2 = 1 - x_1 = 1 - 1/2 = 1/2$。

核心觀念

本題考查：

• Hermitian 矩陣的譜分解；
• 正半定矩陣的最大特徵值與 Rayleigh 商；
• 核範數與矩陣跡乘積的最佳化。

題目雖以 $\|X\|_2$ 表示核範數，以下記為 $\|X\|_*$ 以避免與通常的譜範數混淆。由於 $A$ 為正半定矩陣，且

$$\lambda_1>\lambda_2>\cdots>\lambda_n\ge 0,$$

所以 $A$ 的最大特徵值為 $\lambda_1$，對應的單位特徵向量為 $v_1$。

---

解題方法

因為 $X$ 是 Hermitian 矩陣，可寫成譜分解

$$X=\sum_{j=1}^n \mu_j u_j u_j^*,$$

其中 $\mu_j\in\mathbb{R}$，且 $\{u_j\}$ 為一組正交歸一特徵向量。核範數為

$$\|X\|_*=\sum_{j=1}^n|\mu_j|\le c.$$

另一方面，

$$\begin{aligned} f(X) &=\operatorname{trace}(AX)\\ &=\operatorname{trace}\left(A\sum_{j=1}^n\mu_j u_j u_j^*\right)\\ &=\sum_{j=1}^n\mu_j u_j^*Au_j. \end{aligned}$$

由 Rayleigh 商性質，

$$0\le u_j^*Au_j\le \lambda_1.$$

若 $\mu_j<0$，因為乘上負數會反向改變不等號，因此

$$\mu_j u_j^*Au_j\ge \mu_j\lambda_1.$$

若 $\mu_j\ge 0$，則

$$\mu_j u_j^*Au_j\ge 0.$$

因此

$$\begin{aligned} f(X) &\ge \lambda_1\sum_{\mu_j<0}\mu_j\\ &=-\lambda_1\sum_{\mu_j<0}|\mu_j|\\ &\ge -\lambda_1\sum_{j=1}^n|\mu_j|\\ &\ge -c\lambda_1. \end{aligned}$$

所以對所有符合條件的 $X$，都有

核心觀念

相對平滑性的定義要求

$$\nabla^2(Lg-f)(x)\succeq 0$$

對所有 $x\in S$ 成立，其中 $\succeq 0$ 表示矩陣為半正定。關鍵是計算 $f$ 與 $g$ 的 Hessian 矩陣，並判斷其正定性。

---

依題面所給函數計算

由

$$f(x)=-\alpha\ln(a_1^Tx)-\beta\ln(a_2^Tx),$$

可得

$$\nabla^2 f(x) = \frac{\alpha a_1a_1^T}{(a_1^Tx)^2} + \frac{\beta a_2a_2^T}{(a_2^Tx)^2}.$$

因為 $\alpha,\beta>0$，所以 $\nabla^2 f(x)$ 為半正定矩陣。

題目給定

$$g(x)=\sum_{i=1}^n\ln(x[i]),$$

因此

$$\nabla^2g(x) = -\operatorname{diag}\left( \frac1{x[1]^2},\ldots,\frac1{x[n]^2} \right).$$

所以

$$\begin{aligned} \nabla^2(Lg-f)(x) ={}& -L\operatorname{diag}\left( \frac1{x[1]^2},\ldots,\frac1{x[n]^2} \right)\\ &-\frac{\alpha a_1a_1^T}{(a_1^Tx)^2} -\frac{\beta a_2a_2^T}{(a_2^Tx)^2}. \end{aligned}$$

對任意非零向量 $z$，

$$\begin{aligned} z^T\nabla^2(Lg-f)(x)z ={}& -L\sum_{i=1}^n\frac{z[i]^2}{x[i]^2}\\ &-\alpha\frac{(a_1^Tz)^2}{(a_1^Tx)^2} -\beta\frac{(a_2^Tz)^2}{(a_2^Tx)^2}<0. \end{aligned}$$

因此 $\nabla^2(Lg-f)(x)$ 實際上是負定矩陣，不可能是半正定矩陣。

---

題目中的符號問題

標準的對數障礙函數應為

$$\widetilde g(x)=-\sum_{i=1}^n\ln(x[i]),$$

而不是題目所寫的 $g(x)=\sum_i\ln(x[i])$。若題目原意為此標準形式，則