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

核心觀念

把每個標記 $+1$、$-1$ 的點視為一個數字。從起點沿順時針方向依序經過各點時，累積和就是當下「$+1$ 點數減去 $-1$ 點數」的差。

因此，起點能贏的條件是：從起點開始的每個累積和都不小於 $0$。由於全圈有 $n$ 個 $+1$ 與 $n$ 個 $-1$，走完一圈的總和恰為 $0$。

解題方法：數學歸納法

基礎步驟：$n=1$

圓上有一個 $+1$ 點與一個 $-1$ 點。從 $+1$ 點開始，累積和依序為 $1、0$，全程不小於 $0$，所以可以獲勝。

歸納假設

假設對某個 $n-1\geq 1$ 成立：任意由 $n-1$ 個 $+1$ 與 $n-1$ 個 $-1$ 組成的圓，都有一個起點能使沿途累積和不小於 $0$。

歸納步驟

考慮有 $n$ 個 $+1$ 與 $n$ 個 $-1$ 的圓。順著行進方向，必定有一對相鄰點依序標為 $+1、-1$：因為圓上同時有兩種標記，沿圈前進時至少會遇到一次由 $+1$

核心觀念

• 費馬小定理（Fermat's Little Theorem）：
  設 $p$ 為質數，且 $a$ 為整數。若 $\gcd(a, p) = 1$（即 $a$ 與 $p$ 互質），則：
  $a^{p-1} \equiv 1 \pmod{p}$
• 同餘性質與指數降次（Exponent Reduction）：
  在同餘運算中，若 $a \equiv b \pmod{m}$，則對任意非負整數 $k$，皆滿足 $a^k \equiv b^k \pmod{m}$。求大數字次方 $a^n \pmod{p}$ 時，可透過除法原理將指數 $n$ 表示為 $n = (p-1) \cdot q + r$（其中 $0 \le r < p-1$），將式子化簡為：
  $a^n = (a^{p-1})^q \cdot a^r \equiv (1)^q \cdot a^r \equiv a^r \pmod{p}$

解題方法

1. 確認定理適用條件：
   本題欲求 $3^{302} \pmod{5}$。

   • 模數 $p = 5$ 為質數。
   • 底數 $a = 3$，滿足 $\gcd(3, 5) = 1$（$3$ 與 $5$ 互質）。
     符合費馬小定理的適用前提。

2. 套用費馬小定理：
   由費馬小定理，取得週期同餘關係：
   $3^{5-1} = 3^4 \equiv 1 \pmod{5}$

3. 指數拆解與推導：
   將指數 $302$ 除以週期 $4$，得到商數與餘數：
   $302 = 4 \times 75 + 2$
   利用次方的指數律展開：
   $3^{302} = 3^{4 \times 75 + 2} = (3^4)^{75} \cdot 3^2$

核心觀念

設二元關係為 $R$：

• 反身性（Reflexive）：對所有 $x$，皆有 $(x,x)\in R$。
• 對稱性（Symmetric）：若 $(x,y)\in R$，則 $(y,x)\in R$。
• 遞移性（Transitive）：若 $(x,y)\in R$ 且 $(y,z)\in R$，則 $(x,z)\in R$。
• 反自反性（Irreflexive）：對所有 $x$，皆有 $(x,x)\notin R$。
• 反對稱性中的非對稱（Asymmetric）：若 $(x,y)\in R$，則 $(y,x)\notin R$。
• 等價關係（Equivalence Relation）：反身、對稱且遞移。
• 嚴格序（Strict Order）：反自反且遞移。

依原圖判讀：Relation 1 沒有自迴圈，右側為三個頂點形成的有向循環；Relation 2 為具有自迴圈且各群組內雙向連接的等價關係圖；Relation 3 為空關係。

解題方法與各關係判定

Relation 1

• 沒有任何頂點的自迴圈，因此不是反身，且是反自反。
• 圖中存在單向邊，但沒有對應的反向邊，因此不是對稱。
• 右側三點形成有向循環，例如 $a\to b$、$b\to c$，但沒有 $a\to c$，所以不具遞移性。
• 雖然存在有向循環，但沒有互為反向的兩條邊，因此符合非對稱。
• 因為不具遞移性，所以不是嚴格序。
• 因為不是反身、對稱、遞移三者兼具，所以不是等價關係。

Relation 2

• 每個頂點都有自迴圈，因此具反身性。
• 圖中的連線皆成雙向，例如 $a\to b$ 同時有 $b\to a$，因此具對稱性。
• 關係圖分成數個等價類；

核心觀念

1. 生成樹 (Spanning Tree) 的基本性質：
   設 $G=(V, E)$ 為包含 $n$ 個頂點的連通圖。若 $T$ 為 $G$ 的生成樹，則 $T$ 為無迴圈的連通子圖，且其邊數必為 $|E(T)| = n - 1$。

2. 基本割集 (Fundamental Cutset)：
   若自生成樹 $T$ 中移除任一邊 $e \in E(T)$，則 $T - e$ 會恰好分裂為兩個不相交的連通元件（頂點集分別設為 $V_1$ 與 $V_2$）。原圖 $G$ 中所有一個端點在 $V_1$、另一個端點在 $V_2$ 的邊所構成的集合稱為由 $e$ 引發的基本割集 $C(e, T)$。注意：$T$ 中跨越此割集的邊恰好只有 $e$ 本身，即 $E(T) \cap C(e, T) = \{e\}$。

3. 基本迴圈 (Fundamental Cycle)：
   若將不在生成樹 $T$ 中的一條邊 $e' \notin E(T)$ 加入 $T$ 中，則 $T + e'$ 會包含唯一的一個迴圈，稱為由 $e'$ 引發的基本迴圈 $C(e', T)$。

4. 割集與迴圈的正交性 (Cut-Cycle Intersection Theorem)：
   在任意圖形中，任何一個迴圈與任何一個割集的交集邊數必為偶數（即 $0, 2, 4, \dots$ 條邊）。

解題方法

本題採用構造法 (Constructive Proof)，利用基本割集與基本迴圈的正交性質來尋找同時滿足兩棵樹交換要求的邊。

詳細推導與證明步驟：

1. 挑選邊 $e_1$ 與建立割集 $C$：
   因為 $T_1$ 與 $T_2$ 為不同的生成樹（$T_1 \neq T_2$），且兩者邊數相等（均為 $n-1$），故集合差集 $E(T_1) \setminus E(T_2)$ 必然非空。
   任意挑選一條邊 $e_1 \in E(T_1) \setminus E(T_2)$。
   將 $e_1$ 從 $T_1$ 中移除，此時 $T_1 - e_1$ 分裂為兩個不相交的連通元件，其頂點集分別記為 $V_1$ 與 $V_2$，其中 $V_1 \cup V_2 = V$ 且 $V_1 \cap V_2 = \emptyset$。
   定義由 $e_1$ 引發的割集為：
   $C = \{ uv \in E(G) \mid u \in V_1, v \in V_2 \}$
   由割集定義可知 $e_1 \in C$，且在生成樹 $T_1$ 中，跨越 $V_1$ 與 $V_2$ 的邊僅有 $e_1$ 一條，即 $E(T_1) \cap C = \{e_1\}$。

2. 構造邊 $e_2$：
   考慮將邊 $e_1$ 加入生成樹 $T_2$ 中。由於 $e_1 \notin E(T_2)$，圖形 $T_2 + e_1$ 中必存在唯一的迴圈，記作 $Q = C(e_1, T_2)$。
   因為 $e_1 \in Q$ 且 $e_1 \in C$，迴圈 $Q$ 包含至少一條屬於割集 $C$ 的邊。
   根據「割集與迴圈交集邊數必為偶數」的定理，迴圈 $Q$ 與割集 $C$ 的交集 $|E(Q) \cap C|$ 至少為 $2$。
   因此，在迴圈 $Q$ 中必存在另一條不同於 $e_1$ 的邊 $e_2$，滿足：
   $e_2 \in E(Q) \setminus \{e_1\} \quad \text{且} \quad e_2 \in C$

3. 驗證 $e_2 \in E(T_2) \setminus E(T_1)$：

   • 由於 $e_2$ 屬於迴圈 $Q = C(e_1, T_2)$ 且 $e_2 \neq e_1$，根據基本迴圈的定義，迴圈中除了 $e_1$ 以外的所有邊都來自 $T_2$，故 $e_2 \in E(T_2)$。
   • 又因為 $e_2 \in C$，而 $T_1$ 在割集 $C$ 中的邊只有 $e_1$，且 $e_2 \neq e_1$，故 $e_2 \notin E(T_1)$。

核心觀念

本題屬於離散數學中的格點幾何（Grid Geometry）與不變量原理（Invariant Principle），亦可從**二元一次不定方程組（System of Diophantine Equations）**與整數格點空間的角度進行分析。

主要涵蓋以下核心觀念：

1. 向量整數線性組合（Integer Linear Combination of Vectors）：在二維整數格點 $\mathbb{Z}^2$ 上，若機器人自原點 $(0,0)$ 出發，經由允許的向量集合所能到達的任意點 $(x,y)$，必定可表為該組向量的整數係數線性組合。
2. 聯立不定方程式的整數解判定：目標點是否可達，等價於對應的二元一次方程組是否存在整數解 $(k_1, k_2) \in \mathbb{Z}^2$。若解出之係數含有非整數（分數），則代表該目標點絕對無法到達。
3. 同餘不變量（Modular Invariant）：尋找一個線性映射 $f(x,y) = ax + by$，使得所有允許的位移向量在該映射下皆滿足特定模數（Modulo）的同餘特性。若目標點不滿足該同餘性質，即證明其不可達。

解題方法

【方法一：整數聯立方程組求解（標準推導）】

機器人的四種允許移動向量分別為：

• $v_1 = (+2, -1)$
• $v_2 = (-2, +1) = -v_1$
• $v_3 = (+1, +3)$
• $v_4 = (-1, -3) = -v_3$

注意到 $v_2$ 與 $v_4$ 分別為 $v_1$ 與 $v_3$ 的反向向量。因此，機器人自原點 $(0,0)$ 出發，移動任意步數後所達到的座標 $(x,y)$，皆可表示為 $v_1$ 與 $v_3$ 的整數線性組合：
$(x, y) = k_1 (2, -1) + k_2 (1, 3), \quad k_1, k_2 \in \mathbb{Z}$
其中 $k_1$ 代表沿 $v_1$ 方向的淨移動步數，$k_2$ 代表沿 $v_3$ 方向的淨移動步數。

將其拆解為 $x$ 與 $y$ 的分量方程式：
$\begin{cases} 2k_1 + k_2 = x \\ -k_1 + 3k_2 = y \end{cases}$

將目標點 $(x, y) = (1, 1)$ 代入方程組：
$\begin{cases} 2k_1 + k_2 = 1 & \text{--- (1)} \\ -k_1 + 3k_2 = 1 & \text{--- (2)} \end{cases}$

求解此聯立方程式：
由式 (1) 可得 $k_2 = 1 - 2k_1$，代入式 (2)：
$-k_1 + 3(1 - 2k_1) = 1$
$-k_1 + 3 - 6k_1 = 1$
$-7k_1 = -2 \implies k_1 = \frac{2}{7}$

再將 $k_1 = \frac{2}{7}$ 代回求 $k_2$：
$k_2 = 1 - 2\left(\frac{2}{7}\right) = \frac{3}{7}$

題目簡析

給定圖 $G = (V, E)$，點集 $V = \{1, 2, \dots, 40\}$。當 $i \neq j$ 且 $\gcd(i, j) \neq 1$（即不互質）時，$i$ 與 $j$ 相連。求圖 $G$ 的著色數（Chromatic Number, $\chi(G)$）。

觀念與解題步驟

1. 考慮獨立集與著色數的下界（Cliques）：
   著色數 $\chi(G)$ 至少等於圖中最大團（Maximum Clique）的大小 $\omega(G)$，亦即 $\chi(G) \ge \omega(G)$。

   考慮質數 $2, 3, 5, 7, 11, 13, 17, 19$：

   • 最多只能選擇 8 個彼此互質的質數。
   • 任何大於 1 的合數必含有至少一個質因數。

   在集合 $\{2, 3, 5, 7, 11, 13, 17, 19\}$ 中，任意兩數均互質，因此它們在圖 $G$ 中互相沒有連線（屬於獨立集）。

   反過來，考慮以下 8 個頂點構成的子圖：
   $C = \{2 \times 3 \times 5 \times 7, \dots\}$？更直接地，尋找互相連線的頂點子集（Clique）：
   選擇點集 $K = \{2\cdot 3, 2\cdot 5, 2\cdot 7, 2\cdot 11, 2\cdot 13, 2\cdot 17, 2\cdot 19, 2\cdot 23\}$ 不成立（任意兩數均含有公因數 2，故任意兩數都有邊相連）。

   小於等於 40 的質數共有 12 個：$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$。
   考慮點集 $S = \{2\times 3, 2\times 5, 2\times 7, 2\times 11, 2\times 13, 2\times 17, 2\times 19\} = \{6, 10, 14, 22, 26, 34, 38\}$。

   更精準地，圖 $G$ 的補圖 $\bar{G}$ 中，兩點相連當且僅當它們互質。
   求 $\chi(G)$ 等價於將 $V$ 拆分成最少個獨立集，亦即在補圖 $\bar{G}$ 中拆分成最少個團（Clique Cover）。

2. 質數分類著色法：
   頂點 1 與其他所有頂點均互質，故 1 在 $G$ 中為孤立點（Degree 0），可單獨塗一色或與任意點同色。

   將所有大於 1 的元素 $x \in \{2, \dots, 40\}$ 按其最小質因數（Smallest Prime Factor, SPF）分類：

   • 最小質因數為 2 的元素：$\{2, 4, 6, 8, \dots, 40\}$。這些數兩兩皆有公因數 2，故在 $G$ 中形成一個團（Clique）。要為這個團著色，每個元素必須用不同顏色嗎？不，團中的點互相有邊相連，故團內的每一點都必須著不同顏色！

   正確分析補圖與著色：

   • $G$ 中兩點有邊 $\iff \gcd(i, j) > 1$。
   • 著色規則：若兩點顏色相同，則它們之間不能有邊 $\iff \gcd(i, j) = 1$（兩數必須互質）。

命題
設 $G$ 為一個 $k$-clique，且其每條邊被著色為紅色或藍色。若 $G$ 中包含一個僅由藍邊組成的奇數長度迴路（奇藍迴路），則 $G$ 中必包含一個邊長為 3 且擁有奇數條藍邊（即恰有 1 條或 3 條藍邊）的迴路（三角型）。

證明
對藍邊奇迴路的長度 $m$ 進行數學歸納法。由於迴路由邊組成，奇迴路長度 $m \ge 3$ 且 $m$ 為奇數。

1. 基礎步驟（Base Step）：
   當 $m = 3$ 時，該迴路本身即為一個長度為 3 的迴路，且包含 3 條藍邊（3 為奇數）。命題顯然成立。

2. 歸納假設（Inductive Hypothesis）：
   假設長度為 $k$（其中 $k < m$ 且 $k$ 為奇數）的所有藍邊奇迴路，所在圖中均包含至少一個具奇數條藍邊的三角形。

3. 歸納步驟（Inductive Step）：
   考慮長度為 $m$（$m \ge 5$ 且 $m$ 為奇數）的藍邊奇迴路 $C = (v_1, v_2, \dots, v_m, v_1)$。
   因為原圖為 $k$-clique，點 $v_1$ 與 $v_3$ 之間必定存在一條邊 $e = (v_1, v_3)$。
   討論邊 $e$ 的顏色：

   • 情況一：邊 $e$ 為藍色
     邊 $e$ 將迴路 $C$ 切割成兩個較短的藍邊迴路：
     • $C_1 = (v_1, v_2, v_3, v_1)$，長度為 3。
     • $C_2 = (v_1, v_3, v_4, \dots, v_m, v_1)$，長度為 $m - 1$。
       由於 $C_1$ 為長度 3 的全藍迴路（有 3 條藍邊），即已找到符合條件的三角形。
   • 情況二：邊 $e$ 為紅色

(a) Master Theorem 無法適用的遞迴關係式範例與原因

Master Theorem 要求遞迴式 $T(n) = aT(n/b) + f(n)$ 滿足 $a \ge 1$, $b > 1$，且 $f(n)$ 與 $n^{\log_b a}$ 之間必須滿足多項式漸進比較（polynomial condition）或常數比較條件。

反例

$T(n) = 2T(n/2) + n \log n$

無法使用 Master Theorem 的原因

1. 此式中 $a = 2$, $b = 2$，故 $n^{\log_b a} = n^1 = n$。
2. 雖然 $f(n) = n \log n > n$，但 $\frac{f(n)}{n^{\log_b a}} = \frac{n \log n}{n} = \log n$。
3. 由於 $\log n$ 的成長速度低於任何 $n^\epsilon$ ($\epsilon > 0$)，因此 $f(n)$ 並非多項式大於（polynomially larger） $n^{\log_b a}$（即不存在 $\epsilon > 0$ 使得 $f(n) = \Omega(n^{1+\epsilon})$），不符合 Master Theorem 的 Case 3；同時它也不符合 Case 1 與 Case 2。

(b) 使用遞迴樹法（Recurrence Tree Method）求解 $T(n)$

遞迴關係式：
$T(n) = \sqrt{n} T(\sqrt{n}) + n$

假設邊界條件 $T(2) = \Theta(1)$。

1. 樹的結構與各層工作量分析

• 第 $0$ 層（樹根）：
  • 子問題個數：$1$
  • 每個子問題規模：$n$
  • 本層總工作量：$n$

核心觀念

• 數進位制與結尾 0 的意義：整數 $N$ 在 $b$ 進位制下的末尾 0 個數，等於能整除 $N$ 的 $b$ 之最高次方數，即求最大整數 $k$ 使得 $b^k \mid N$。
• 進位底數的質因數分解：若進位底數 $b$ 為合數，必須將其分解為質因數乘積。八進位底數為 $8 = 2^3$，因此求 $8^k \mid 20!$ 等價於求 $2^{3k} \mid 20!$。
• 勒讓德定理（Legendre's Formula）：用於計算 $n!$ 中質因數 $p$ 的最高次方數 $E_p(n!)$：
  $E_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots$

解題方法

1. 計算 $20!$ 中質因數 2 的最高次方數 $E_2(20!)$
   代入勒讓德定理公式，計算 $n = 20, p = 2$ 各項：
   $\left\lfloor \frac{20}{2} \right\rfloor = 10$
   $\left\lfloor \frac{20}{4} \right\rfloor = 5$
   $\left\lfloor \frac{20}{8} \right\rfloor = 2$
   $\left\lfloor \frac{20}{16} \right\rfloor = 1$
   $\left\lfloor \frac{20}{32} \right\rfloor = 0$
   加總可得：
   $E_2(20!) = 10 + 5 + 2 + 1 = 18$
   即 $20!$ 可被 $2^{18}$ 整除，但無法被 $2^{19}$ 整除。

2. 轉換為八進位底數 $8 = 2^3$ 的次方數
   欲使 $8^k \mid 20!$，亦即 $(2^3)^k = 2^{3k} \mid 20!$。