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

這題主要在考查向量空間中的基底變換以及轉換矩陣的應用。

核心概念：

1. 轉換矩陣：從一個基底轉換到另一個基底的矩陣。
2. 標準基底：$\mathbb{R}^n$ 的標準基底通常是 $e_1, e_2, \dots, e_n$，其中 $e_i$ 的第 $i$ 個分量為 1，其餘為 0。
3. 向量的座標表示：一個向量在不同基底下的座標表示是不同的。

解題步驟：

a) 求從 B 轉換到 S 的轉換矩陣
從基底 $B$ 轉換到基底 $S$ 的轉換矩陣，其行向量就是基底 $B$ 中的向量在基底 $S$ 下的座標表示。由於 $S$ 是標準基底，向量在標準基底下的座標就是向量本身。
因此，從 $B$ 到 $S$ 的轉換矩陣 $P_{S \leftarrow B}$ 是由基底 $B$ 的向量 $u_1, u_2, u_3$ 組成的矩陣：
$P_{S \leftarrow B} = \begin{pmatrix} u_1 & u_2 & u_3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 5 & 3 \\ 1 & 0 & 8 \end{pmatrix}$

b) 求從 S 轉換到 B 的轉換矩陣
從標準基底 $S$ 轉換到另一個基底 $B$ 的轉換矩陣 $P_{B \leftarrow S}$，是 $P_{S \leftarrow B}$ 的反矩陣。
我們需要計算 $P_{S \leftarrow B}$ 的反矩陣。
$P = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 5 & 3 \\ 1 & 0 & 8 \end{pmatrix}$
計算行列式：
$\det(P) = 1(5 \cdot 8 - 3 \cdot 0) - 2(2 \cdot 8 - 3 \cdot 1) + 3(2 \cdot 0 - 5 \cdot 1)$
$\det(P) = 1(40) - 2(16 - 3) + 3(-5)$
$\det(P) = 40 - 2(13) - 15$
$\det(P) = 40 - 26 - 15 = -1$
計算伴隨矩陣（adjoint matrix）：
Cofactor $C_{11} = (5 \cdot 8 - 3 \cdot 0) = 40$
Cofactor $C_{12} = -(2 \cdot 8 - 3 \cdot 1) = -(16 - 3) = -13$
Cofactor $C_{13} = (2 \cdot 0 - 5 \cdot 1) = -5$
Cofactor $C_{21} = -(2 \cdot 8 - 3 \cdot 0) = -16$
Cofactor $C_{22} = (1 \cdot 8 - 3 \cdot 1) = 8 - 3 = 5$
Cofactor $C_{23} = -(1 \cdot 0 - 2 \cdot 1) = -(-2) = 2$
Cofactor $C_{31} = (2 \cdot 3 - 3 \cdot 5) = 6 - 15 = -9$
Cofactor $C_{32} = -(1 \cdot 3 - 3 \cdot 2) = -(3 - 6) = 3$

這題主要考查向量投影的概念，將一個向量分解為沿著另一個向量的方向和垂直於該向量的方向。

核心概念：

1. 向量投影：向量 $u$ 在向量 $a$ 上的投影，記為 $\text{proj}_a u$。
2. 向量分量：向量 $u$ 可以分解為沿著 $a$ 的分量和垂直於 $a$ 的分量。

解題步驟：

a) 求 $u$ 沿著 $a$ 的向量分量
向量 $u$ 沿著向量 $a$ 的分量是向量 $u$ 在向量 $a$ 方向上的投影。
投影公式為：
$\text{proj}_a u = \frac{u \cdot a}{\|a\|^2} a$
首先計算點積 $u \cdot a$：
$u \cdot a = (1)(0) + (1)(2) + (1)(-1) = 0 + 2 - 1 = 1$
然後計算 $\|a\|^2$：
$\|a\|^2 = 0^2 + 2^2 + (-1)^2 = 0 + 4 + 1 = 5$
將這些值代入投影公式：
$\text{proj}_a u = \frac{1}{5} a = \frac{1}{5} (0, 2, -1)^T = \left(0, \frac{2}{5}, -\frac{1}{5}\right)^T$
這是向量 $u$ 沿著 $a$ 的分量。

b) 求 $u$ 垂直於 $a$ 的向量分量
向量 $u$ 可以分解為沿著 $a$ 的分量（即投影）和垂直於 $a$ 的分量。
若令 $u = u_{\parallel} + u_{\perp}$，其中 $u_{\parallel} = \text{proj}_a u$ 是沿著 $a$ 的分量，而 $u_{\perp}$ 是垂直於 $a$ 的分量，則：

這題考查最小平方法（Least Squares Method）的應用，用來找出最符合給定數據點的直線。

核心概念：

1. 最小平方法：透過最小化實際觀測值與模型預測值之間誤差的平方和，來找到最佳模型參數。
2. 線性迴歸：尋找一條直線 $y = ax + b$ 來擬合數據。

解題步驟：
我們要找一條直線 $y = ax + b$ 來擬合三個數據點：$(-2, -11)$, $(0, -2)$, $(4, 2)$。
將這些點代入直線方程式，我們得到一個超定方程組（overdetermined system）：
$-2a + b = -11$
$0a + b = -2$
$4a + b = 2$

我們可以將這個系統寫成矩陣形式 $Ax = y'$：
$\begin{pmatrix} -2 & 1 \\ 0 & 1 \\ 4 & 1 \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} -11 \\ -2 \\ 2 \end{pmatrix}$
其中 $A = \begin{pmatrix} -2 & 1 \\ 0 & 1 \\ 4 & 1 \end{pmatrix}$，$x = \begin{pmatrix} a \\ b \end{pmatrix}$，$y' = \begin{pmatrix} -11 \\ -2 \\ 2 \end{pmatrix}$。

最小平方法的目标是找到向量 $x$ 使得 $\|y' - Ax\|$ 最小。這對應於求解正規方程（normal equation）：
$A^T A x = A^T y'$
首先計算 $A^T$：
$A^T = \begin{pmatrix} -2 & 0 & 4 \\ 1 & 1 & 1 \end{pmatrix}$
計算 $A^T A$：
$A^T A = \begin{pmatrix} -2 & 0 & 4 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} -2 & 1 \\ 0 & 1 \\ 4 & 1 \end{pmatrix} = \begin{pmatrix} (-2)(-2)+0(0)+4(4) & (-2)(1)+0(1)+4(1) \\ 1(-2)+1(0)+1(4) & 1(1)+1(1)+1(1) \end{pmatrix}$

這題考查特徵值（eigenvalues）與特徵向量（eigenvectors）的概念，以及如何從這些資訊建構出一個對稱矩陣。

核心概念：

1. 特徵值與特徵向量的定義：對於一個方陣 $A$，若存在非零向量 $v$ 和純量 $\lambda$，使得 $Av = \lambda v$，則 $\lambda$ 為 $A$ 的一個特徵值，而 $v$ 為對應於 $\lambda$ 的特徵向量。
2. 對稱矩陣的性質：一個實對稱矩陣，其相異特徵值對應的特徵向量是正交的。
3. 譜定理（Spectral Theorem）：任何一個實對稱矩陣都可以被對角化，即 $A = PDP^T$，其中 $D$ 是由特徵值組成的對角矩陣，而 $P$ 的行向量是正規化後的特徵向量組成的正交矩陣。

解題步驟：
給定三個特徵值 $\lambda_1 = 4$, $\lambda_2 = 2$, $\lambda_3 = 0$ 和對應的特徵向量 $v_1 = (1, 1, 0)^T$, $v_2 = (0, 0, 1)^T$, $v_3 = (-1, 1, 0)^T$。
首先，我們需要檢查給定的特徵向量是否彼此正交。
$v_1 \cdot v_2 = (1)(0) + (1)(0) + (0)(1) = 0$
$v_1 \cdot v_3 = (1)(-1) + (1)(1) + (0)(0) = -1 + 1 + 0 = 0$
$v_2 \cdot v_3 = (0)(-1) + (0)(1) + (1)(0) = 0$
由於所有相異特徵值對應的特徵向量都正交，這表示我們找到的特徵向量集是一個正交集。這符合實對稱矩陣的性質。

接下來，我們需要將這些特徵向量正規化，以形成一個標準正交基（orthonormal basis）。
計算各特徵向量的範數（長度）：
$\|v_1\| = \sqrt{1^2 + 1^2 + 0^2} = \sqrt{2}$
$\|v_2\| = \sqrt{0^2 + 0^2 + 1^2} = \sqrt{1} = 1$
$\|v_3\| = \sqrt{(-1)^2 + 1^2 + 0^2} = \sqrt{1 + 1 + 0} = \sqrt{2}$

正規化後的特徵向量（單位向量）$u_i = \frac{v_i}{\|v_i\|}$：
$u_1 = \frac{1}{\sqrt{2}} v_1 = \frac{1}{\sqrt{2}}(1, 1, 0)^T = \left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0\right)^T$
$u_2 = \frac{1}{1} v_2 = (0, 0, 1)^T$
$u_3 = \frac{1}{\sqrt{2}} v_3 = \frac{1}{\sqrt{2}}(-1, 1, 0)^T = \left(-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0\right)^T$

根據譜定理，一個實對稱矩陣 $A$ 可以表示為 $A = PDP^T$，其中 $D$ 是由特徵值組成的對角矩陣，而 $P$ 是一個由正規化後的特徵向量組成的正交矩陣（其行向量是 $u_1, u_2, u_3$）。
$D = \begin{pmatrix} \lambda_1 & 0 & 0 \\ 0 & \lambda_2 & 0 \\ 0 & 0 & \lambda_3 \end{pmatrix} = \begin{pmatrix} 4 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 0 \end{pmatrix}$
$P = \begin{pmatrix} u_1 & u_2 & u_3 \end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} \\ 0 & 1 & 0 \end{pmatrix}$
由於 $P$ 是由標準正交向量組成的矩陣，所以 $P^T = P^{-1}$。
$P^T = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \end{pmatrix}$
現在計算 $A = PDP^T$：

這題考查子空間、正交補空間以及向量投影的概念。

核心概念：

1. 子空間 (Subspace)：向量空間的子集，它本身也構成一個向量空間。
2. 張成 (Span)：由一組向量線性組合所能達到的所有向量的集合。
3. 正交補空間 (Orthogonal Complement)：對於一個子空間 $W$，其正交補空間 $W^\perp$ 是所有與 $W$ 中所有向量都正交的向量的集合。
4. 向量投影：將一個向量投影到另一個向量或子空間上。

解題步驟：

a) 求 $W^\perp$ 的一組標準正交基
子空間 $W$ 由向量 $w = (1, 1, 1)^T$ 張成。這意味著 $W$ 是一個一維的子空間，即一條通過原點的直線。
$W = \text{span}\{(1, 1, 1)^T\}$。
$W^\perp$ 是所有與 $W$ 中的向量正交的向量組成的集合。也就是說，$W^\perp$ 中的任何向量 $x$ 都必須滿足 $x \cdot w = 0$。
設 $x = (x_1, x_2, x_3)^T \in \mathbb{R}^3$。則 $x \cdot w = 0$ 意味著：
$x_1(1) + x_2(1) + x_3(1) = 0$
$x_1 + x_2 + x_3 = 0$
這個方程式定義了 $W^\perp$。這是一個平面，它是通過原點且法向量為 $(1, 1, 1)^T$ 的平面。
$W^\perp$ 是 $\mathbb{R}^3$ 的一個二維子空間。
為了找到 $W^\perp$ 的一組標準正交基，我們需要找到兩個相互正交且長度為 1 的向量，它們滿足 $x_1 + x_2 + x_3 = 0$。
我們可以先找一組正交基，然後再進行正規化。
從 $x_1 + x_2 + x_3 = 0$ 中，我們可以選擇兩個線性獨立的向量。
例如，令 $x_1=1, x_2=0$，則 $x_3 = -1$。得到向量 $v_1 = (1, 0, -1)^T$。
令 $x_1=0, x_2=1$，則 $x_3 = -1$。得到向量 $v_2 = (0, 1, -1)^T$。
這兩個向量 $v_1, v_2$ 顯然是線性獨立的，並且都屬於 $W^\perp$。
檢查它們是否正交：
$v_1 \cdot v_2 = (1)(0) + (0)(1) + (-1)(-1) = 0 + 0 + 1 = 1 \neq 0$。
所以 $v_1$ 和 $v_2$ 並不相互正交。我們需要使用格拉姆-施密特正交化（Gram-Schmidt process）來找到正交基。

令 $u_1 = v_1 = (1, 0, -1)^T$。
下一個向量 $u_2$ 可以通過從 $v_2$ 中減去 $v_2$ 在 $u_1$ 上的投影來得到：
$\text{proj}_{u_1} v_2 = \frac{v_2 \cdot u_1}{\|u_1\|^2} u_1$
$v_2 \cdot u_1 = (0)(1) + (1)(0) + (-1)(-1) = 1$
$\|u_1\|^2 = 1^2 + 0^2 + (-1)^2 = 2$
$\text{proj}_{u_1} v_2 = \frac{1}{2} (1, 0, -1)^T = \left(\frac{1}{2}, 0, -\frac{1}{2}\right)^T$
$u_2 = v_2 - \text{proj}_{u_1} v_2 = (0, 1, -1)^T - \left(\frac{1}{2}, 0, -\frac{1}{2}\right)^T = \left(0 - \frac{1}{2}, 1 - 0, -1 - \left(-\frac{1}{2}\right)\right)^T = \left(-\frac{1}{2}, 1, -\frac{1}{2}\right)^T$
現在我們得到一組正交基 $\{u_1, u_2\}$：
$u_1 = (1, 0, -1)^T$
$u_2 = \left(-\frac{1}{2}, 1, -\frac{1}{2}\right)^T$
驗證它們是否正交：

這題考查集合論中的基本概念，特別是關於空集合 ($\emptyset$) 和集合的成員關係 ($\in$)、子集關係 ($\subseteq$) 的理解。

核心概念：

1. 空集合 ($\emptyset$)：不包含任何元素的集合。
2. 成員關係 ($\in$)：表示一個元素屬於某個集合。
3. 子集關係 ($\subseteq$)：表示一個集合的所有元素都屬於另一個集合。
4. 集合的定義：集合是由獨立的、不重複的元素組成的。

解題步驟：
我們逐一判斷每個敘述的真偽。

a) $\emptyset \in \{\emptyset\}$
這個敘述的意思是「空集合是集合 $\{\emptyset\}$ 的一個元素」。
集合 $\{\emptyset\}$ 包含一個元素，這個元素就是空集合 $\emptyset$。
所以，這個敘述是真的。

b) $\emptyset \subseteq \{\emptyset\}$
這個敘述的意思是「空集合是集合 $\{\emptyset\}$ 的一個子集」。
任何集合的子集都包含空集合。因此，空集合是任何集合的子集。
所以，這個敘述是真的。

c) $\{\emptyset\} \in \{\emptyset, \{\emptyset\}\}$
這個敘述的意思是「集合 $\{\emptyset\}$ 是集合 $\{\emptyset, \{\emptyset\}\}$ 的一個元素」。
集合 $\{\emptyset, \{\emptyset\}\}$ 包含兩個元素：
第一個元素是 $\emptyset$ (空集合)。
第二個元素是 $\{\emptyset\}$ (包含空集合的集合)。
因此，$\{\emptyset\}$ 確實是這個集合的一個元素。
所以，這個敘述是真的。

d) $\{\emptyset\} \subseteq \{\emptyset\}$
這個敘述的意思是「集合 $\{\emptyset\}$ 是集合 $\{\emptyset\}$ 的一個子集」。
任何集合都是其自身的子集。
所以，這個敘述是真的。

e) $\{\emptyset\} \subseteq \{\emptyset, \{\emptyset\}\}$
這個敘述的意思是「集合 $\{\emptyset\}$ 是集合 $\{\emptyset, \{\emptyset\}\}$ 的一個子集」。
我們要檢查集合 $\{\emptyset\}$ 的所有元素是否都在集合 $\{\emptyset, \{\emptyset\}\}$ 中。
集合 $\{\emptyset\}$ 只有一個元素，就是 $\emptyset$。
集合 $\{\emptyset, \{\emptyset\}\}$ 包含 $\emptyset$ 和 $\{\emptyset\}$。
由於 $\emptyset$ 是集合 $\{\emptyset, \{\emptyset\}\}$ 的一個元素，所以 $\{\emptyset\}$ 是 $\{\emptyset, \{\emptyset\}\}$ 的一個子集。
所以，這個敘述是真的。

f) $\{\{\emptyset\}, \{\emptyset\}\} \subseteq \emptyset, \{\emptyset\}\}$
首先，我們需要釐清左邊集合的元素。集合的元素是獨立的，不重複的。所以 $\{\{\emptyset\}, \{\emptyset\}\}$ 實際上就是 $\{\{\emptyset\}\}$。它只包含一個元素，這個元素是 $\{\emptyset\}$。

這是一道經典的邏輯謎題，考驗對資訊傳遞、共同知識（common knowledge）以及策略推理的理解。

核心概念：

1. 共同知識 (Common Knowledge)：資訊是共同知識，如果每個人都知道，並且每個人都知道別人知道，並且每個人都知道別人知道別人知道，以此類推，無限循環。
2. 資訊推理：根據觀察到的資訊和假設的誠實性，推斷出自己未知的事實。
3. 策略性思考：考慮對方可能的反應和推理過程。

設定：

• 有兩個孩子，男孩 (B) 和女孩 (G)。
• 兩人額頭上都有泥巴。
• 孩子們能看到對方的額頭，但看不到自己的。
• 孩子們都很誠實。
• 父親說：「你們至少有一個人額頭上有泥巴。」
• 父親問兩次：「你知道你的額頭上有泥巴嗎？」
• 孩子們同時回答。

分析過程：
我們假設孩子們的推理能力和誠實程度是相同的。

第一次提問：「你知道你的額頭上有泥巴嗎？」

• 男孩 (B) 的視角：
  • 男孩看到女孩 (G) 的額頭上有泥巴。
  • 父親說「至少有一個人有泥巴」。
  • 如果男孩自己的額頭是乾淨的，那麼他會看到女孩額頭上有泥巴，並且知道父親說的話（至少一人有泥巴）是因為女孩的泥巴。此時，他就會知道自己的額頭是乾淨的。
  • 然而，男孩並不知道自己的額頭是否有泥巴。這意味著，他不可能僅憑看到女孩有泥巴就確定自己的額頭是乾淨的。
  • 更關鍵的是，如果男孩的額頭是乾淨的，而女孩的額頭也有泥巴，那麼他看到女孩有泥巴，他就可以推斷出「至少一人有泥巴」這個前提是成立的。此時，他無法確定自己的額頭是否是乾淨的。
  • 重點推理： 如果男孩的額頭是乾淨的，而女孩的額頭也有泥巴，那麼男孩看到女孩額頭有泥巴，他就能立刻推斷出「至少一人有泥巴」這個前提成立，但這並不能幫助他判斷自己的額頭。
  • 反向思考： 假設男孩的額頭是乾淨的。他看到女孩額頭有泥巴。他知道「至少一人有泥巴」。這情況下，他無法斷定自己的額頭。
  • 關鍵點： 如果男孩的額頭是乾淨的，他看到女孩額頭有泥巴，他就能確定「至少一個人有泥巴」（因為女孩有）。但這並不讓他知道「自己的額頭」是否有泥巴。
  • 如果男孩自己的額頭是乾淨的，他看到女孩額頭有泥巴。他知道父親說的話「至少一人有泥巴」是因為女孩。那麼他就可以推斷出自己的額頭是乾淨的。
  • 如果男孩自己的額頭有泥巴，他看到女孩額頭也有泥巴。他知道父親說的話「至少一人有泥巴」是因為女孩（或者因為自己，或者因為兩人都有）。他無法確定自己的額頭。
  • 什麼情況下，男孩會回答「Yes」？ 當他能排除自己額頭乾淨的可能性時。
  • 什麼情況下，男孩會回答「No」？ 當他看到對方額頭有泥巴，並且他自己額頭也是乾淨的（這種情況下他可以推斷自己是乾淨的，但問題是「你知道你的額頭上有泥巴嗎？」），或者他看到對方額頭有泥巴，但他自己額頭也有泥巴，因此他無法確定。
  • 共同知識的引入： 兩人都有泥巴。
    • 男孩看到女孩有泥巴。
    • 如果男孩的額頭是乾淨的，他知道「至少一人有泥巴」是因為女孩。他知道自己的額頭是乾淨的。但他無法知道「自己的額頭上有泥巴嗎？」。他應該回答「No」。
    • 如果男孩的額頭有泥巴，他看到女孩額頭也有泥巴。他知道「至少一人有泥巴」是因為女孩（也可能是自己）。他無法確定自己的額頭。他應該回答「No」。

這是一道關於組合遊戲（Combinatorial Game Theory）的經典問題，屬於尼姆遊戲（Nim game）的一種變體。我們要證明先手玩家（第一位玩家）有必勝策略。

核心概念：

1. 必勝狀態 (Winning Position) 與必敗狀態 (Losing Position)：
   • 必勝狀態：在這個狀態下，玩家可以採取某種行動，使對方進入必敗狀態。
   • 必敗狀態：在這個狀態下，玩家無論採取何種行動，都會使對方進入必勝狀態。
2. 狀態轉移：遊戲的進行就是從一個狀態轉移到另一個狀態。
3. 逆向歸納法 (Backward Induction)：從遊戲結束的狀態開始，逐步往前推導，判斷每個狀態的勝敗。

解題步驟：
遊戲規則：

• 初始石頭數：22 顆。
• 每次移除數量：1, 2, 3, 或 4 顆。
• 拿走最後一顆石頭者獲勝。

我們使用逆向歸納法來分析。遊戲的目標是讓對方處於無法移動（即石頭數為 0）的狀態。

1. 石頭數為 0： 這是遊戲結束的狀態。拿走最後一顆石頭的玩家獲勝。所以，輪到你時，如果你面對 0 顆石頭，你就輸了（因為你無法移動）。因此，0 是一個必敗狀態。

2. 石頭數為 1, 2, 3, 4：

   • 如果石頭數是 1, 2, 3, 或 4，你可以一次拿走所有石頭，讓對方面對 0 顆石頭。由於 0 顆石頭是必敗狀態，所以 1, 2, 3, 4 都是必勝狀態。

3. 石頭數為 5：

   • 如果你面對 5 顆石頭，你最多只能拿走 4 顆。
   • 如果你拿走 1 顆，剩下 4 顆。對方面對 4 顆，這是必勝狀態（對方可以拿走全部）。
   • 如果你拿走 2 顆，剩下 3 顆。對方面對 3 顆，這是必勝狀態。
   • 如果你拿走 3 顆，剩下 2 顆。對方面對 2 顆，這是必勝狀態。
   • 如果你拿走 4 顆，剩下 1 顆。對方面對 1 顆，這是必勝狀態。
   • 無論你怎麼拿，對方都面對一個必勝狀態。因此，5 顆石頭是一個必敗狀態。

4. 石頭數為 6, 7, 8, 9：

   • 如果石頭數是 6，你可以拿走 1 顆，剩下 5 顆。對方面對 5 顆，這是必敗狀態。所以 6 是必勝狀態。
   • 如果石頭數是 7，你可以拿走 2 顆，剩下 5 顆。對方面對 5 顆，這是必敗狀態。所以 7 是必勝狀態。
   • 如果石頭數是 8，你可以拿走 3 顆，剩下 5 顆。對方面對 5 顆，這是必敗狀態。所以 8 是必勝狀態。
   • 如果石頭數是 9，你可以拿走 4 顆，剩下 5 顆。對方面對 5 顆，這是必敗狀態。所以 9 是必勝狀態。

5. 石頭數為 10：

   • 如果你面對 10 顆石頭，你最多只能拿走 4 顆。
   • 如果你拿走 1 顆，剩下 9 顆。對方面對 9 顆，這是必勝狀態。
   • 如果你拿走 2 顆，剩下 8 顆。對方面對 8 顆，這是必勝狀態。
   • 如果你拿走 3 顆，剩下 7 顆。對方面對 7 顆，這是必勝狀態。
   • 如果你拿走 4 顆，剩下 6 顆。對方面對 6 顆，這是必勝狀態。
   • 無論你怎麼拿，對方都面對一個必勝狀態。因此，10 顆石頭是一個必敗狀態。

觀察模式：
我們發現必敗狀態是 0, 5, 10, ...
這些數字的共同點是它們是 5 的倍數。
每次玩家可以拿走 $k \in \{1, 2, 3, 4\}$ 顆石頭。
考慮數字 $1+2+3+4 = 10$。
這裡的關鍵數字是 $1 + (\text{最大移除數}) = 1 + 4 = 5$。
如果當前石頭數 $N$ 是 5 的倍數，那麼無論玩家拿走 $k$ 顆（其中 $k \in \{1, 2, 3, 4\}$），剩下的石頭數 $N-k$ 都不是 5 的倍數。
如果當前石頭數 $N$ 不是 5 的倍數，那麼玩家總是能拿走 $k$ 顆石頭，使得剩下的石頭數 $N-k$ 是 5 的倍數。
這是因為如果 $N \pmod 5 = r$，其中 $r \in \{1, 2, 3, 4\}$，那麼玩家可以拿走 $k=r$ 顆石頭，使得 $N-r$ 成為 5 的倍數。

證明：
一個狀態（石頭數 $N$）是必敗狀態，若且唯若 $N \pmod 5 = 0$。

• 基礎情況： $N=0$ 是必敗狀態，且 $0 \pmod 5 = 0$。

• 歸納假設： 假設對於所有小於 $N$ 的石頭數，如果 $N' \pmod 5 = 0$，則 $N'$ 是必敗狀態；如果 $N' \pmod 5 \neq 0$，則 $N'$ 是必勝狀態。

• 歸納步驟：

  • 情況 1：$N \pmod 5 = 0$
    玩家面對 $N$ 顆石頭。

核心觀念

本題考查「鴿巢原理」與「最壞情況分析」。

集合中的數字皆為奇數，總和為 $24$ 的配對如下：

$$(1,23),\ (3,21),\ (5,19),\ (7,17),\ (9,15),\ (11,13)$$

共形成 $6$ 對，而且每個數字恰好只屬於其中一對。

題目要求保證至少有 $3$ 對數字，其和為 $24$。

解題方法

要找出「保證至少出現三對」所需的最少選取數量，先分析最多能選多少個數字而仍然只有至多兩對完整配對。

為了避免出現第三對完整配對：

• 可以完整選取 $2$ 對，共選 $2 \times 2=4$ 個數字；
• 剩下的 $4$ 對，每一對最多只能選其中 $1$ 個，否則就會形成完整配對，因此可再選 $4$ 個數字。

所以，在尚未保證出現三對之前，最多可以選取

這題考查線性齊次遞迴關係式（Linear Homogeneous Recurrence Relation）的求解，並利用初始條件求出特解。

核心概念：

1. 特徵方程式：對於線性齊次遞迴關係式 $c_k a_n + c_{k-1} a_{n-1} + \dots + c_0 a_{n-k} = 0$，其特徵方程式為 $c_k r^k + c_{k-1} r^{k-1} + \dots + c_0 = 0$。
2. 特徵根的類型與通解形式：
   • 若特徵根為相異實根 $r_1, r_2, \dots, r_k$，則通解為 $a_n = C_1 r_1^n + C_2 r_2^n + \dots + C_k r_k^n$。
   • 若有重根 $r$ (k 次)，則通解包含 $r^n, nr^n, \dots, (n-1)r^n$ 等項。
3. 利用初始條件求解常數：將通解代入初始條件，解出常數 $C_i$。

解題步驟：
給定的遞迴關係式為 $a_n = 2a_{n-1} - a_{n-2}$，對於 $n > 1$。
將其改寫為標準形式：$a_n - 2a_{n-1} + a_{n-2} = 0$。
這個是一個二階線性齊次遞迴關係式。

1. 建立特徵方程式：
   將 $a_n$ 替換為 $r^n$ (或 $r^2$)，將 $a_{n-1}$ 替換為 $r^{n-1}$ (或 $r^1$)，將 $a_{n-2}$ 替換為 $r^{n-2}$ (或 $r^0$)。
   特徵方程式為：
   $r^2 - 2r + 1 = 0$

2. 求解特徵根：
   這個二次方程式可以因式分解為：
   $(r - 1)^2 = 0$
   因此，我們得到一個重根 $r = 1$ (重數為 2)。

這題考查圖論中補圖（Complementary Graph）的概念，以及圖的邊數、頂點數之間的關係。

核心概念：

1. 簡單圖 (Simple Graph)：無自環（self-loop）且任意兩頂點之間最多只有一條邊的圖。
2. 補圖 ($\overline{G}$)：對於一個簡單圖 $G=(V, E)$，其補圖 $\overline{G}=(V, \overline{E})$ 具有相同的頂點集合 $V$。對於 $V$ 中的任意兩個不同頂點 $u, v$，它們在 $\overline{G}$ 中是相鄰的，當且僅當它們在 $G$ 中不相鄰。
3. 完全圖 ($K_n$)：一個有 $n$ 個頂點的圖，其中任意兩個不同的頂點之間都有邊相連。完全圖的邊數為 $\binom{n}{2}$。
4. 邊數與頂點數的關係：在一個有 $n$ 個頂點的簡單圖中，最大可能的邊數是構成完全圖 $K_n$ 的邊數，即 $\binom{n}{2}$。

解題步驟：
設圖 $G$ 有 $n$ 個頂點。
由於 $G$ 是簡單圖，它最多可以有 $\binom{n}{2}$ 條邊。
補圖 $\overline{G}$ 具有相同的頂點集合，也有 $n$ 個頂點。
補圖 $\overline{G}$ 的邊數與原圖 $G$ 的邊數之間有如下關係：
圖 $G$ 的邊數 $|E(G)|$ 加上補圖 $\overline{G}$ 的邊數 $|E(\overline{G})|$ 等於頂點數為 $n$ 的完全圖 $K_n$ 的邊數。