111 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《離散數學》

(1-1)

題目引文：$n \leq 3^3$ for every non-negative integer, $n$.

• 核心觀念：非負整數的界限與全稱命題（Universal Quantifier $\forall$）的否定。
• 解題方法：全稱命題宣稱「對所有非負整數 $n$ 均成立」。要證明其為假，只需舉出一個不滿足該不等式的**反例（Counterexample）**即可。
• 選項分析：
  計算右式得 $3^3 = 27$。題目敘述「所有非負整數 $n$ 皆滿足 $n \le 27$」。若取 $n = 28$，則 $28$ 確實為非負整數，但 $28 \le 27$ 不成立。因此該敘述為假。
• 解題技巧：看到含有「for every」、「for all」的全稱敘述，優先尋找反例。只要取一個足夠大的數字即可快速說明其不成立。

【答案】False

---

(1-2)

題目引文：In a group of five people, where each two are either friends or enemies, there must be either three mutual friends, or three mutual enemies.

• 核心觀念：拉姆齊理論（Ramsey Theory）與拉姆齊數 $R(3,3) = 6$。
• 解題方法：將 5 個人視為完全圖 $K_5$ 的 5 個頂點，兩人之間的關係（朋友或敵人）視為邊的雙色著色（2-coloring）。若要保證必定存在 3 個互相為朋友或 3 個互相為敵人（即同色 $K_3$），需要檢驗 5 個頂點是否達到拉姆齊數的門檻。
• 選項分析：
  根據拉姆齊定理（6 人聚會定理），保證存在 3 個互相為朋友或 3 個互相為敵人的最小人數為拉姆齊數 $R(3,3) = 6$。當人數僅有 5 人時，可以構造以下反例：
  將 5 個人排成一圈（構形為 5-環圖 $C_5$），規定每個人只與相鄰的 2 人為朋友，與不相鄰的 2 人為敵人。在此配置下：
  1. 朋友關係形成的圖為 $C_5$，最大團（Clique）大小為 2，不存在 3 個互相為朋友的人。
  2. 敵人關係形成的圖為 $C_5$ 的補圖（同構於 $C_5$），最大團大小亦為 2，不存在 3 個互相為敵人的人。
     因此，在 5 人的群體中不必然存在 3 個互相為朋友或敵人的人，該敘述為假。
• 解題技巧：熟記經典拉姆齊數 $R(3,3) = 6$。當人數少於 6 人（例如 5 人）時，五邊形 $C_5$ 是無同色三角形（Monochromatic $K_3$）的最標準反例構造。

【答案】False

---

(1-3)

題目引文：If $a$ is an integer and $m$ is a positive integer, then $a^{m-1} \equiv 1 \pmod{m}$.

• 核心觀念：費馬小定理（Fermat's Little Theorem）的前提條件與同餘性質。
• 解題方法：費馬小定理指出，若 $p$ 為質數且整數 $a$ 與 $p$ 互質（即 $\gcd(a, p) = 1$），則 $a^{p-1} \equiv 1 \pmod p$。檢視本題是否滿足定理所需的兩大關鍵前提條件。
• 選項分析：
  題目僅假設 $m$ 為正整數、 $a$ 為整數，並未限定 $m$ 為質數，亦未限定 $\gcd(a, m) = 1$：
  • 反例 1（模數非質數）：取 $a = 2, m = 4$，則 $a^{m-1} = 2^3 = 8 \equiv 0 \pmod 4 \neq 1$。
  • 反例 2（不互質）：即使取質數 $m = 2$，若取 $a = 2$，則 $2^{2-1} = 2 \equiv 0 \pmod 2 \neq 1$。
    由於缺乏前提條件，同餘式不必然成立，該敘述為假。
• 解題技巧：數論定理的前提條件（如「質數」、「互質」）是考試極常見的陷阱。看到 $a^{m-1} \equiv 1 \pmod m$ 卻沒寫明 $m$ 為質數且 $\gcd(a,m)=1$ 時，可直接代入小合數（如 $m=4$）驗證反例。

【答案】False

---

(1-4)

題目引文：If all the edge weights on a graph are distinct, the minimum spanning tree is unique.

• 核心觀念：最小生成樹（Minimum Spanning Tree, MST）的唯一性、切集性質（Cut Property）與環性質（Cycle Property）。
• 解題方法：利用反證法搭配環性質進行證明。在連通加權圖中，若所有邊的權重皆不相同，則任何環上的最大權重邊都是嚴格唯一的，同理任何切集上的最小權重邊也是嚴格唯一的，這將確保生成樹的唯一性。
• 選項分析：
  假設圖中存在兩棵不同的最小生成樹 $T_1$ 與 $T_2$。因為 $T_1 \neq T_2$，必存在至少一條邊 $e_1 \in T_1 \setminus T_2$。
  將 $e_1$ 加入 $T_2$ 中會形成唯一的環 $C$。由於 $T_1$ 不含環，$C$ 中必定存在另一條邊 $e_2 \in T_2 \setminus T_1$。
  因為圖中所有邊的權重互不相同，故 $w(e_1) \neq w(e_2)$：
  1. 若 $w(e_1) < w(e_2)$，則將 $T_2$ 中的 $e_2$ 替換為 $e_1$ 可得到權重更小的生成樹，與 $T_2$ 為最小生成樹矛盾。
  2. 若 $w(e_2) < w(e_1)$，則將 $T_1$ 中的 $e_1$ 替換為 $e_2$ 可得到權重更小的生成樹，與 $T_1$ 為最小生成樹矛盾。
     由矛盾可知，不可能存在兩棵不同的最小生成樹，故最小生成樹必為唯一，該敘述為真。
• 解題技巧：記住重要定理「邊權重互異 $\implies$ 最小生成樹唯一」。注意其逆命題不一定成立（即使有相同權重的邊，最小生成樹仍可能唯一）。

【答案】True

---

(1-5)

題目引文：Let $p$ be a positive integer, and $s_1, s_2, \dots, s_n$ be integers. If $p$ divides $s_1 s_2 \dots s_n$, then $p$ divides $s_i$ for some $i$.

• 核心觀念：歐幾里得引理（Euclid's Lemma）與質數的整除性質。

(2-1)

命題與條件分析

設命題 $P$: 「$31$ 是質數」，命題 $Q$: 「$31$ 是我最喜歡的數字」。
根據題意，$P$ 的真值為 真 (True)，而 $Q$ 的真值 未知。

各選項分析

• (a) 錯誤：$P \to Q$。當 $P$ 為 True 且 $Q$ 未知時，$P \to Q$ 的真值取決於 $Q$，故無法確定為真。
• (b) 正確：$Q \to P$。因為結論 $P$ 為 True，根據蘊涵式（Implication）的真值表，若結論為 True，則不論前提 $Q$ 為何，$Q \to P$ 恆為 真 (True)。
• (c) 正確：$\neg P \to Q$。因為前提 $\neg P$ 為 False，根據蘊涵式的性質，前提為假時，命題（Vacuously True）恆為 真 (True)。
• (d) 正確：$Q \lor P$。因為 $P$ 為 True，由邏輯或（OR）的性質，只要其中一個命題為 True，整體即為 真 (True)。
• (e) 正確：$Q \lor \neg Q$。此為排中律（Law of Excluded Middle），恆為 重言式 (Tautology)，真值必為 真 (True)。

【答案】(b)(c)(d)(e)

---

(2-2)

核心觀念

1. 競賽圖（Tournament Digraph）：設 $G = (V, E)$ 為一有向圖。若對任意相異頂點對 $u, v \in V$，恰有 $u \to v$ 或 $v \to u$ 其中一條有向邊存在，則稱 $G$ 為競賽圖。即競賽圖是由完全圖（Complete Graph $K_n$）將每條邊賦予方向後得到的有向圖。
2. 排名（Ranking）與哈密頓路徑（Hamiltonian Path）：題目定義 Ranking 為包含所有選手（頂點）的有向路徑（Directed Path）。在圖論中，經過圖中每一個頂點恰好一次的有向簡單路徑稱為哈密頓路徑。因此，尋找 Ranking 即為尋找競賽圖中的哈密頓路徑。
3. 有向無環圖（Directed Acyclic Graph, DAG）與拓撲排序（Topological Sort）：若有向圖中不包含任何有向迴圈（Directed Cycle），則稱為 DAG。每一個 DAG 都至少存在一組拓撲排序 $v_1, v_2, \dots, v_n$，使得若存在邊 $v_i \to v_j$，則必有 $i < j$。
4. 雷代定理（Rédei's Theorem）：圖論著名定理，指出「任何有限競賽圖皆至少包含一條哈密頓路徑（Ranking）」。

---

解題方法

針對題目三個子題的具體切入點與解題架構：

• (3-1)：構造一個最小且包含有向迴圈的競賽圖。取 $n=3$ 的有向 3-迴圈競賽圖，列出其包含的所有相異 Ranking。
• (3-2)：利用 DAG 的拓撲排序性質與競賽圖的完全性（Completeness），導出 DAG 競賽圖的頂點順序完全由邊的方向唯一確定，進而證明 Ranking 至多只有一種。
• (3-3)：採用**數學歸納法（Mathematical Induction）**對頂點數 $n$ 進行歸納證明（即雷代定理 Rédei's Theorem 的標準證明），構造出將第 $k+1$ 個頂點插入已知 $k$ 個頂點 Ranking 中的明確方法。

---

子題詳細解答與證明

(3-1) 給出一具有超過一個 Ranking 的競賽圖範例

構造範例：
設頂點集合 $V = \{A, B, C\}$，邊集合 $E = \{(A, B), (B, C), (C, A)\}$。
此有向圖 $G = (V, E)$ 在任意兩點間均恰有一條有向邊，故為一競賽圖。

Ranking 驗證：
在此競賽圖中，包含所有頂點的有向路徑（Ranking）有以下三條：

1. $A \to B \to C$ （選手排名為 $A, B, C$）
2. $B \to C \to A$ （選手排名為 $B, C, A$）
3. $C \to A \to B$ （選手排名為 $C, A, B$）

因為找到了 3 條相異的 Ranking（$3 > 1$），故此競賽圖滿足題意要求。

---

(3-2) 證明若競賽圖為 DAG，則其至多只有一個 Ranking

證明：

1. 建立拓撲排序：
   設 $T = (V, E)$ 為一個包含 $n$ 個頂點的 DAG 競賽圖。
   因為 $T$ 為有向無環圖（DAG），故 $V$ 中存在頂點的拓撲排序（Topological Sort），記為 $v_1, v_2, \dots, v_n$。
   根據拓撲排序的定義，若存在有向邊 $v_i \to v_j$，則必滿足 $i < j$。

2. 確定邊的方向唯一性：
   對於任意一對頂點 $v_i$ 與 $v_j$（其中 $1 \le i < j \le n$）：
   由於 $T$ 是競賽圖，在 $v_i$ 與 $v_j$ 之間必存在邊 $v_i \to v_j$ 或 $v_j \to v_i$。
   若存在邊 $v_j \to v_i$，將與拓撲排序之性質（邊只能由小索引指向大索引）矛盾。
   因此，對所有 $1 \le i < j \le n$，在 $T$ 中必有邊 $v_i \to v_j$。

3. 分析 Ranking 的唯一性：
   設 $P = u_1 \to u_2 \to \dots \to u_n$ 為 $T$ 中的任一 Ranking（包含所有 $n$ 個頂點的有向路徑）。
   對於路徑上的每一條邊 $u_k \to u_{k+1}$（其中 $1 \le k \le n-1$），在拓撲排序中，$u_k$ 的索引必須嚴格小於 $u_{k+1}$ 的索引。
   亦即，若設 $\text{pos}(u)$ 為頂點 $u$ 在拓撲排序中的位置（$1$ 到 $n$ 的整數），則必有：
   $\text{pos}(u_1) < \text{pos}(u_2) < \dots < \text{pos}(u_n)$
   由於 $\{u_1, u_2, \dots, u_n\} = \{v_1, v_2, \dots, v_n\}$ 且長度為 $n$，唯一的嚴格遞增正整數序列為 $1, 2, \dots, n$。
   因此必有：
   $\text{pos}(u_1) = 1, \quad \text{pos}(u_2) = 2, \quad \dots, \quad \text{pos}(u_n) = n$
   即唯一可能的 Ranking 必須嚴格為 $v_1 \to v_2 \to \dots \to v_n$。

故若競賽圖為 DAG，則其至多存在一個 Ranking（事實上恰有一個）。 $\blacksquare$

---

(3-3) 證明任何有限競賽圖皆存在 Ranking（Rédei 定理）

證明（採用數學歸納法）：
對競賽圖的頂點個數 $n = |V|$ 進行數學歸納。

1. 基礎步驟（Base Case）：
   • 當 $n = 1$ 時，單一頂點顯然構成一條長度為 0 的 Ranking。
   • 當 $n = 2$ 時，設頂點為 $v_1, v_2$。由競賽圖定義，必有 $v_1 \to v_2$ 或 $v_2 \to v_1$。無論何者，皆構成一條包含所有 2 個頂點的 Ranking。
     基礎步驟成立。

題目題目解析與定案解法

本題為經典「蒙提霍爾問題（Monty Hall Problem）」的變形問題。

1. 條件機率與賽制分析

每次遊戲進行時，房產隨機置於三扇門之一，機率各為 $\frac{1}{3}$。玩家（Dr. X）先隨機選擇一扇門。

• 設 $H$ 為「Dr. X 初次選擇的門後面是房產」的事件，$P(H) = \frac{1}{3}$。
• 設 $G$ 為「Dr. X 初次選擇的門後面是山羊」的事件，$P(G) = \frac{2}{3}$。

Dr. YY 從剩下的兩扇門中隨機選擇一扇打開：

1. 若 $H$ 發生：剩下的兩扇門後面都是山羊，故 Dr. YY 開門必定揭露山羊。
   $P(\text{開出山羊} \mid H) = 1$
2. 若 $G$ 發生：剩下的兩扇門中是一隻山羊與一份房產，故 Dr. YY 隨機開門揭露山羊的機率為 $\frac{1}{2}$。
   $P(\text{開出山羊} \mid G) = \frac{1}{2}$

2. 重複賽制下的條件機率計算

題目規定：若 Dr. YY 開出房產則遊戲重新開始，直到 Dr. YY 開出山羊時才進入最終選擇（換門或不換門）。因此，本題討論的樣本空間已條件限制於「Dr. YY 開出山羊」的有效局。

由全機率公式，Dr. YY 揭露山羊的總機率為：

第 5 題 詳解

---

(5-1)

定理： 由 $n$ 個單位正方形邊對邊拼接而成的連通圖形，其外圍周長必為偶數。

證明（數學歸納法）：

1. 基礎步驟 (Base Step)：
   當 $n=1$ 時，單一單位正方形的外圍周長為 $4$，為偶數。成立。

2. 歸納假設 (Induction Hypothesis)：
   假設當正方形個數為 $n=k$ ($k \ge 1$) 時，其外圍周長 $P_k$ 為偶數。

3. 歸納步驟 (Induction Step)：
   考慮加入第 $k+1$ 個單位正方形。新加入的正方形有 4 條邊，假設它與原先 $k$ 個正方形形成的圖形共享 $m$ 條邊 ($1 \le m \le 4$)：

   • 加入該正方形會覆蓋原有的 $m$ 條外圍邊（周長減少 $m$）。
   • 該正方形剩餘的 $4-m$ 條邊成為新的外圍邊（周長增加 $4-m$）。

   因此，新的周長為：
   $P_{k+1} = P_k - m + (4 - m) = P_k + 4 - 2m$
   由於 $P_k$ 根據歸納假設為偶數，且 $4 - 2m = 2(2 - m)$ 亦為偶數，故兩偶數之和 $P_{k+1}$ 必為偶數。

由數學歸納法得證，對所有正整數 $n$，周長皆為偶數。

【答案】得證

---

(5-2)

[!NOTE]
題目給定的通式 $a_n = a_0 \left(\frac{8}{5}\right)^n$ 為題意印製錯誤（此通式為公比之誤用，科克雪花的極限面積應為 $\frac{8}{5}a_0$）。以下按標準科克雪花面積之正確推導過程給出嚴謹證明。

科克雪花面積遞迴分析：

• 邊數與新增三角形：

  • $S_0$ 有 $N_0 = 3$ 條邊，面積為 $a_0$。
  • $S_n$ 的邊數 $N_n = 3 \times 4^n$。
  • 從 $S_n$ 到 $S_{n+1}$，每條邊上新增一個邊長為原本 $\frac{1}{3}$ 的正三角形，其面積為 $\left(\frac{1}{3}\right)^2 a_0 = \frac{1}{9} a_0$。
  • 因此在第 $n+1$ 步新增的總面積為：
    $\Delta a_{n+1} = N_n \times \left( \frac{1}{9^{n+1}} a_0 \right) = (3 \times 4^n) \times \frac{a_0}{9^{n+1}} = \frac{1}{3} \cdot \left(\frac{4}{9}\right)^n a_0$

• 面積通式正確值：

(6-1)

【詳解】
目前 Table 2(b) 為一個 $3 \times 5$ 的拉丁矩陣（Latin rectangle）：

$$\begin{pmatrix} 3 & 2 & 1 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \\ 2 & 5 & 3 & 1 & 4 \end{pmatrix}$$

填入第 4 列與第 5 列，需滿足每列與每行皆恰好包含 $1, 2, 3, 4, 5$ 各一次。

• 第 1 行已出現 $\{3, 1, 2\}$，剩餘數字為 $\{4, 5\}$。
• 第 2 行已出現 $\{2, 4, 5\}$，剩餘數字為 $\{1, 3\}$。
• 第 3 行已出現 $\{1, 2, 3\}$，剩餘數字為 $\{4, 5\}$。
• 第 4 行已出現 $\{4, 5, 1\}$，剩餘數字為 $\{2, 3\}$。
• 第 5 行已出現 $\{5, 3, 4\}$，剩餘數字為 $\{1, 2\}$。

選定第 4 列為：$4, 1, 5, 2, 3$。
則第 5 列為：$5, 3, 4, 1, 2$。

【答案】
第 4 列與第 5 列可填入如下（完整 $5 \times 5$ 拉丁方陣）：

$$\begin{pmatrix} 3 & 2 & 1 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \\ 2 & 5 & 3 & 1 & 4 \\ 4 & 1 & 5 & 2 & 3 \\ 5 & 3 & 4 & 1 & 2 \end{pmatrix}$$

---

(6-2)

【詳解】
設目前為 $k \times n$ 拉丁矩陣（$k < n$）。若要填入第 $(k+1)$ 列：

1. 構建二分圖 $G = (X, Y, E)$：
   • 左側頂點集 $X = \{c_1, c_2, \dots, c_n\}$ 代表第 $1$ 到第 $n$ 行（Columns）。
   • 右側頂點集 $Y = \{v_1, v_2, \dots, v_n\}$ 代表數字元素集合 $\{1, 2, \dots, n\}$。
   • 邊集 $E$：若數字 $j$ 在第 $i$ 行的前 $k$ 列中尚未出現過，則在二分圖中連一條邊 $(c_i, v_j)$。
2. 匹配與第 $(k+1)$ 列的等價性：
   • 找到 $G$ 中的一個完美匹配（Perfect Matching）$M = \{(c_1, v_{j_1}), (c_2, v_{j_2}), \dots, (c_n, v_{j_n})\}$。
   • 這意味著將數字 $v_{j_i}$ 填入第 $(k+1)$ 列的第 $i$ 行。
   • 因為 $M$ 為匹配：

核心觀念

本題考查數論（Number Theory）中的整除性（Divisibility）與質數性質（Properties of Primes）。核心定義與定理包含：

1. 因式分解與連續整數性質：利用平方差公式將 $p^2 - 1$ 分解為 $(p - 1)(p + 1)$，轉化為分析連續偶數與連續三整數的整除特性。
2. 質數的同餘性質：
   • 若質數 $p > 2$，則 $p$ 必為奇數。
   • 若質數 $p > 3$，則 $p$ 不可能被 3 整除，即 $p \equiv 1 \pmod 3$ 或 $p \equiv 2 \pmod 3$。
3. 互質與乘法整除性質：若 $a \mid n$ 且 $b \mid n$，且 $\gcd(a, b) = 1$，則 $(a \times b) \mid n$。因為 $\gcd(8, 3) = 1$，證明 $24 \mid (p^2 - 1)$ 可拆解為分別證明 $8 \mid (p^2 - 1)$ 與 $3 \mid (p^2 - 1)$。

---

解題方法

本題命題為真（Prove）。以下為嚴謹的推導證明過程：

步驟一：因式分解
將 $p^2 - 1$ 表示為兩個連續偶數的乘積：
$p^2 - 1 = (p - 1)(p + 1)$

步驟二：證明 $8 \mid (p^2 - 1)$
因為 $p$ 是大於 3 的質數，故 $p$ 必為奇數。
設 $p = 2k + 1$（其中 $k \ge 2$ 為正整數），帶入可得：
$p - 1 = 2k$
$p + 1 = 2k + 2 = 2(k + 1)$
乘積為：
$(p - 1)(p + 1) = 2k \cdot 2(k + 1) = 4k(k + 1)$
由於 $k$ 與 $k + 1$ 為兩個連續整數，其中必恰有一個為偶數，故 $k(k + 1)$ 必能被 2 整除，即 $k(k + 1) = 2m$（$m \in \mathbb{Z}$）。
代回得：
$(p - 1)(p + 1) = 4(2m) = 8m$
因此，$p^2 - 1$ 必能被 8 整除，即 $8 \mid (p^2 - 1)$。

步驟三：證明 $3 \mid (p^2 - 1)$
考慮三個連續整數 $p - 1, p, p + 1$。
在任意三個連續整數中，恰有一個數能被 3 整除。
因為 $p$ 為大於 3 的質數，故 $p$ 本身不能被 3 整除（$3 \nmid p$）。

(a)

核心觀念

1. $f = O(n^2)$：存在常數 $C > 0$ 及 $N > 0$，使得對所有 $n \ge N$，$|f(n)| \le C n^2$。即當 $n \to \infty$ 時，$\limsup_{n\to\infty} \left|\frac{f(n)}{n^2}\right| < \infty$。
2. $f \sim n^2$（漸近等價）：$\lim_{n\to\infty} \frac{f(n)}{n^2} = 1$。

解答

定義函數 $f(n) = 2n^2$（或 $f(n) = n$）。

檢驗：

1. $\lim_{n\to\infty} \frac{f(n)}{n^2} = \lim_{n\to\infty} \frac{2n^2}{n^2} = 2 \le 2$，故 $f(n) = O(n^2)$。
2. 因為 $\lim_{n\to\infty} \frac{f(n)}{n^2} = 2 \neq 1$，故 $f \nsim n^2$。

【答案】$f(n) = 2n^2$

---

(b)

核心觀念

1. $g = O(n^2)$：當 $n$ 足夠大時，$g(n)$ 上界受限於 $C n^2$。
2. $g \neq \Theta(n^2)$：不存在下界常數 $c > 0$ 使得 $g(n) \ge c n^2$ 恆成立（或 $g(n)$ 無法與 $n^2$ 同階）。
3. $g \neq o(n^2)$：$\limsup_{n\to\infty} \frac{g(n)}{n^2} > 0$，即 $g(n)$ 成長速度並非嚴格小於 $n^2$。