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

核心觀念

本題為國立臺灣聯合大學系統（清華、政治、陽明交通、中央）電機類研究所離散數學考古題，綜合考察離散數學四大核心主題：

1. 數論與模運算 (Modular Arithmetic & Number Theory)：
   • 同餘運算的消去律 (Cancellation Law)：$ax \equiv ay \pmod{n} \implies x \equiv y \pmod{\frac{n}{\gcd(a,n)}}$。消去律 $x \equiv y \pmod{n}$ 成立的充要條件為 $\gcd(a, n) = 1$。
   • 乘法模逆元 (Modular Multiplicative Inverse)：$a$ 在模 $b$ 下存在模逆元 $a^{-1} \pmod{b}$ 的充要條件為 $\gcd(a, b) = 1$。若 $\gcd(a, b) > 1$，則絕對不存在模逆元。
   • 費馬小定理 (Fermat's Little Theorem)：若 $p$ 為質數，則對任意整數 $n$，均滿足 $n^p \equiv n \pmod{p}$，即 $p \mid (n^p - n)$。
2. 集合論與基數 (Set Theory & Cardinality)：
   • 可數無限集 (Countably Infinite Set)：基數為 $\aleph_0$。整數集 $\mathbb{Z}$ 與質數集 $P$ 均為可數無限集，故兩者基數相同（$|\mathbb{Z}| = |P| = \aleph_0$）。
   • 集合相等定義與元素個數：兩集合相等當且僅當兩者包含完全相同的元素。基數不同則集合必不相等。
3. 二元關係性質 (Binary Relation Properties)：
   • 自反性 (Reflexive)、對稱性 (Symmetric) 與 遞移性 (Transitive) 的嚴格邏輯定義。自反性要求定義域集合中的每一個元素均需滿足 $(x, x) \in R$。

---

解題方法

此類是非題（True or False）伴隨簡答理由（1-2 句話說明），切入點如下：

• 判斷為 False 者：最迅速且精準的證明方式為舉出明確反例 (Counterexample)。
• 判斷為 True 者：直接引用離散數學知名定理（如費馬小定理、歐幾里得質數無限定理）或邏輯直接推導。
• 寫作時先給出明確的判斷結果（True / False），接著列出精煉的 1~2 句英文答題示範（符合考題規範），最後給出詳細的繁體中文推導說明。

---

選項分析

(a) If $ax = ay \pmod{n}$, then $x = y \pmod{n}$.

• 判斷：False
• 推導與解析：
  在模運算中，消去律成立的前提為 $a$ 與模數 $n$ 互質（即 $\gcd(a, n) = 1$）。一般的消去律公式為 $ax \equiv ay \pmod{n} \implies x \equiv y \pmod{\frac{n}{\gcd(a, n)}}$。當 $\gcd(a, n) > 1$ 時，無法直接消去 $a$。
• 反例驗證：
  取 $a = 2, x = 1, y = 4, n = 6$。
  此時 $ax = 2 \cdot 1 = 2$，且 $ay = 2 \cdot 4 = 8 \equiv 2 \pmod{6}$，滿足 $ax \equiv ay \pmod{n}$。
  然而 $x = 1 \not\equiv 4 = y \pmod{6}$，故命題不成立。
• 考試英文答題示範：
  False. The cancellation law holds only when $\gcd(a, n) = 1$. For example, $2 \cdot 1 \equiv 2 \cdot 4 \pmod{6}$, but $1 \not\equiv 4 \pmod{6}$.

(b) If $x = y \pmod{n}$, then $ax = ay \pmod{n}$.

• 判斷：True
• 推導與解析：
  同餘關係對整數乘法具備封閉性。依同餘定義：
  $x \equiv y \pmod{n} \iff n \mid (x - y) \iff x - y = kn \quad (k \in \mathbb{Z})$
  等式兩邊同乘以整數 $a$：
  $a(x - y) = a(kn) \iff ax - ay = (ak)n$
  因為 $ak \in \mathbb{Z}$，故 $n \mid (ax - ay)$，即 $ax \equiv ay \pmod{n}$ 對任意整數 $a$ 恆成立。
• 考試英文答題示範：
  True. If $x \equiv y \pmod{n}$, then $n \mid (x - y)$, which implies $n \mid a(x - y) = ax - ay$, so $ax \equiv ay \pmod{n}$.

(c) The set of integers and the set of prime numbers have the same cardinality.

• 判斷：True
• 推導與解析：
  整數集合 $\mathbb{Z}$ 為可數無限集，其基數為 $|\mathbb{Z}| = \aleph_0$。由歐幾里得定理可知質數有無限多個，故質數集合 $P = \{2, 3, 5, 7, 11, \dots\}$ 亦為可數無限集，基數為 $|P| = \aleph_0$。兩集合基數相同，皆與自然數集 $\mathbb{N}$ 一一對應。
• 考試英文答題示範：
  True. Both the set of integers $\mathbb{Z}$ and the set of prime numbers are countably infinite, so they both have cardinality $\aleph_0$.

(d) If a relation is symmetric and transitive, then the relation is reflexive.

• 判斷：False
• 推導與解析：

(a) 計算期望值

1. 剩餘頂點數之期望值 $\mathbb{E}[X]$

設頂點集為 $V$，$|V| = n$。定義指示隨機變數 $X_i$ 為頂點 $v_i$ 在刪除過程後留下的指示函數（留下來為 1，被刪除為 0）。

每個頂點保留的機率為：
$p = 1 - \left(1 - \frac{1}{d}\right) = \frac{1}{d}$

由期望值的線性性質（Linearity of Expectation），剩餘頂點數 $X = \sum_{i=1}^n X_i$ 的期望值為：
$\mathbb{E}[X] = \sum_{i=1}^n \mathbb{E}[X_i] = n \cdot p = \frac{n}{d}$

2. 剩餘邊數之期望值 $\mathbb{E}[Y]$

設邊集為 $E$，$|E| = m = \lfloor nd/2 \rfloor$。一條邊 $e = (u, v)$ 會在過程結束後保留，若且唯若其兩個端點 $u$ 與 $v$ 同時被保留。

由於各頂點獨立刪除，該邊保留的機率為：
$p_e = p \cdot p = \frac{1}{d} \cdot \frac{1}{d} = \frac{1}{d^2}$

定義指示隨機變數 $Y_j$ 為邊 $e_j$ 保留的指示函數，剩餘邊數 $Y = \sum_{j=1}^m Y_j$ 的期望值為：
$\mathbb{E}[Y] = \sum_{j=1}^m \mathbb{E}[Y_j] = m \cdot \frac{1}{d^2} = \lfloor nd/2 \rfloor \cdot \frac{1}{d^2}$

若取 upper bound 忽略取整數符號（$\lfloor nd/2 \rfloor \le nd/2$），則：

核心觀念

本題考查圖論（Graph Theory）中**生成樹（Spanning Tree）與最小生成樹（Minimum Cost Spanning Tree, MST）**的經典結構性質及其等價性定理。

設連通賦權圖為 $G = (V, E)$，其邊權重函數為 $c: E \to \mathbb{R}$，$T = (V, E_T)$ 為 $G$ 的一個生成樹。

1. 基本環路（Fundamental Cycle）與環路性質（Cycle Property）：
   對於任意非樹邊 $e' \notin T$，將 $e'$ 加入 $T$ 中會形成唯一的簡單環路，稱為由 $e'$ 誘發的基本環路 $C(T, e')$。若對該環路上所有的邊 $e \in C(T, e')$，皆滿足 $c(e') \ge c(e)$，則稱 $T$ 具備環路性質。
   （意即：任何非樹邊 $e'$ 都是其所產生的基本環路中權重最大者之一。）

2. 基本割集（Fundamental Cutset）與割集性質（Cut Property）：
   對於任意樹邊 $e \in T$，將 $e$ 自 $T$ 中刪除會使 $T$ 分裂為兩個獨立的連通元件，進而誘發點集劃分 $(V_1, V_2)$。由該劃分所決定的割集為 $D(T, e) = \{ (u, v) \in E \mid u \in V_1, v \in V_2 \}$。若對該割集中所有的邊 $e' \in D(T, e)$，皆滿足 $c(e) \le c(e')$，則稱 $T$ 具備割集性質。
   （意即：任何樹邊 $e$ 都是其所產生的基本割集中權重最小者之一。）

3. 最小生成樹（Minimum Cost Spanning Tree, MST）：
   生成樹 $T$ 的所有邊權重總和 $\sum_{e \in T} c(e)$ 在 $G$ 的所有可能生成樹中達到全域最小值。

為了證明三者等價（$1 \Leftrightarrow 2 \Leftrightarrow 3$），最簡潔嚴謹的方法是採取環狀推導法（Circular Proof）：分別證明 $(1) \Rightarrow (2)$、$(2) \Rightarrow (3)$ 與 $(3) \Rightarrow (1)$。

---

解題方法

步驟一：證明 $(1) \Rightarrow (2)$ （環路性質 $\Rightarrow$ 割集性質）

• 假設：$T$ 具備環路性質。
• 目標：證明 $T$ 亦具備割集性質。
• 證明推導：
  1. 任取一條樹邊 $e = (u, v) \in T$。刪除邊 $e$ 後，$T$ 分裂為兩個不相交的頂點子集 $V_1$ 與 $V_2$，其中 $u \in V_1, v \in V_2$。
  2. 由 $e$ 誘發的基本割集為 $D(T, e) = \{ (x, y) \in E \mid x \in V_1, y \in V_2 \}$。
  3. 對於割集 $D(T, e)$ 中的任意邊 $e'$：
     • 若 $e' = e$，顯然 $c(e) \le c(e')$ 恆成立。
     • 若 $e' \neq e$，則必有 $e' \notin T$。將 $e'$ 加入 $T$ 中會形成唯一的簡單基本環路 $C(T, e')$。
     • 由於 $e'$ 的兩端點分別位於 $V_1$ 與 $V_2$，在生成樹 $T$ 中連接這兩端點的唯一簡單路徑必然跨越割集 $(V_1, V_2)$。而在 $T$ 中跨越此割集的邊僅有 $e$ 自身。
     • 因此，樹邊 $e$ 必定落在基本環路 $C(T, e')$ 上，即 $e \in C(T, e')$。
     • 根據假設，$T$ 具備環路性質，故對環路 $C(T, e')$ 上的所有邊 $e$，均滿足 $c(e') \ge c(e)$，即 $c(e) \le c(e')$。
  4. 由於對所有 $e' \in D(T, e)$ 皆滿足 $c(e) \le c(e')$，故 $T$ 具備割集性質。 $\blacksquare$

---

步驟二：證明 $(2) \Rightarrow (3)$ （割集性質 $\Rightarrow$ 最小生成樹）

• 假設：$T$ 具備割集性質。
• 目標：證明 $T$ 為最小生成樹（MST）。
• 證明推導（採用替換論證法 Exchange Argument 與反證法）：
  1. 假設 $T$ 不是最小生成樹。設 $T^*$ 為圖 $G$ 的某個最小生成樹，且 $T^*$ 滿足「與 $T$ 擁有最多相同邊」的條件。
  2. 若 $T \neq T^*$，則必存在至少一條樹邊 $e \in T \setminus T^*$。
  3. 從 $T$ 中刪除邊 $e$ 將點集 $V$ 切割為 $V_1$ 與 $V_2$，對應的基本割集為 $D(T, e)$。
  4. 因為 $T^*$ 是連通的生成樹，在 $T^*$ 中必定存在至少一條邊 $e' \in T^*$ 跨越割集 $(V_1, V_2)$，即 $e' \in D(T, e)$。注意此時 $e' \notin T$（因為 $T$ 中跨越該割集的邊只有 $e$）。
  5. 根據假設 $T$ 具備割集性質，對於割集 $D(T, e)$ 中的邊 $e'$，必有 $c(e) \le c(e')$。

核心觀念

本題考查**中國剩餘定理（Chinese Remainder Theorem, CRT）與聯立同餘方程組（System of Linear Congruences）**的求解。

中國剩餘定理 (CRT)：
設 $m_1, m_2, \dots, m_n$ 為兩兩互質（relatively prime）的正整數，且總模數 $M = \prod_{i=1}^n m_i$。對於任意整數 $a_1, a_2, \dots, a_n$，聯立同餘方程組：
$x \equiv a_i \pmod{m_i}, \quad i = 1, 2, \dots, n$
在模 $M$ 下存在唯一解，表示為：
$x \equiv \left( \sum_{i=1}^n a_i M_i y_i \right) \pmod M$
其中 $M_i = \frac{M}{m_i}$，且 $y_i$ 為 $M_i$ 對模數 $m_i$ 的乘法反元素（乘法逆元），即滿足 $M_i y_i \equiv 1 \pmod{m_i}$。

---

解題方法

本題給定之同餘方程組為：
$\begin{cases} x \equiv 1 \pmod{3} \\ x \equiv 3 \pmod{7} \\ x \equiv 9 \pmod{11} \end{cases}$

步驟一：確認條件與計算總模數

模數分別為 $m_1 = 3, m_2 = 7, m_3 = 11$。
由於 $\gcd(3,7) = \gcd(7,11) = \gcd(3,11) = 1$，滿足兩兩互質條件。
總模數 $M = 3 \times 7 \times 11 = 231$。

步驟二：計算各項的 $M_i$ 與乘法反元素 $y_i$

1. 針對 $m_1 = 3$：
   $M_1 = \frac{231}{3} = 77$
   求解 $77 y_1 \equiv 1 \pmod 3$：
   $77 \equiv 2 \pmod 3 \implies 2 y_1 \equiv 1 \pmod 3 \implies y_1 \equiv 2 \pmod 3$

2. 針對 $m_2 = 7$：
   $M_2 = \frac{231}{7} = 33$
   求解 $33 y_2 \equiv 1 \pmod 7$：
   $33 \equiv 5 \pmod 7 \implies 5 y_2 \equiv 1 \pmod 7 \implies -2 y_2 \equiv 1 \pmod 7 \implies y_2 \equiv 3 \pmod 7$

3. 針對 $m_3 = 11$：
   $M_3 = \frac{231}{11} = 21$
   求解 $21 y_3 \equiv 1 \pmod{11}$：

核心觀念

1. 合數（Composite Number）的定義：
   正整數 $m > 1$ 若除了 $1$ 與自身之外，還存在其他正整數因數，即稱為合數。換言之，若存在整數 $k$ 滿足 $1 < k < m$ 且 $k \mid m$，則 $m$ 必為合數。

2. 階乘（Factorial）的整除性質：
   對於任意正整數 $m$，階乘 $m! = 1 \times 2 \times 3 \times \dots \times m$ 必能被 $2, 3, \dots, m$ 當中的任意整數整除。

3. 數論整除的線性組合性質：
   若整數 $d \mid a$ 且 $d \mid b$，則 $d \mid (a + b)$。

---

解題方法

本題要求證明對任意正整數 $n$，皆存在 $n$ 個連續的合數。最直接且嚴密的證明方式為顯式構造法（Explicit Construction）。

完整推導與證明步驟：

1. 構造目標數列：
   對任意給定的正整數 $n$，構造以下 $n$ 個連續整數：
   $a_k = (n+1)! + k, \quad \text{其中 } k = 2, 3, 4, \dots, n+1$

2. 驗證項數與連續性：
   數列從 $k = 2$ 開始至 $k = n+1$ 結束，其項數為：
   $(n+1) - 2 + 1 = n$
   且各項相差 $1$，故此 $n$ 個數為連續正整數。

3. 證明每一項皆為合數：
   對於數列中的任意一項 $a_k = (n+1)! + k$（其中 $2 \le k \le n+1$）：

   • 因為 $2 \le k \le n+1$，在連乘積 $(n+1)! = 1 \times 2 \times \dots \times k \dots \times (n+1)$ 中必然包含因子 $k$，故 $k \mid (n+1)!$。
   • 顯然 $k \mid k$。
   • 根據整除的可加性，可得 $k \mid \left( (n+1)! + k \right)$。
   • 又因為 $k \ge 2$，且 $(n+1)! \ge 2$，可知 $(n+1)! + k > k$。

(a) 證明：Sprouts 遊戲必在有限次移動內結束

令遊戲起始點數為 $n$。

1. 初始狀態：

   • 每個點最多能連接 $3$ 條邊，稱點的剩餘連接度（Degree capacity）總和為「可用點度數」（Lives）。
   • 初始狀態下，每個點有 $3$ 個 Lives，故初始總 Lives 為 $3n$。

2. 每一步移動對 Lives 的變動：

   • 連接兩個舊點（或同一個點的兩端）消耗 $2$ 個 Lives。
   • 在新畫的線上新增 $1$ 個新點，該點連接剛剛畫出的 $2$ 條新邊，故該新點消耗 $2$ 個 Lives，剩餘 $3 - 2 = 1$ 個 Life。
   • 因此，每次移動淨消耗的 Lives 數為：$2 - 1 = 1$ 個 Life。

3. 結論：

   • 遊戲過程中的總 Lives 數從 $3n$ 開始，每移動一次恰好減少 $1$。
   • 因為總 Lives 數恆為非負整數（$\ge 0$），所以總移動次數不可能超過 $3n$ 次。
   • 因此，任何 Sprouts 遊戲必在有限次移動內終止。

---

(b) 求解並證明初始 $n$ 個點的極限最大移動次數（Tight Upper Bound）

【答案】
最壞情況下的最大移動次數緊緻上界為 $3n - 1$ 次。

證明：

1. 點與邊的動態數量關係：
   • 設經歷 $m$ 次移動後，遊戲中的總點數為 $V$，總邊數為 $E$。
   • 初始時 $V = n$，$E = 0$。

【試題】 7. Act together, we go far. [12 points] Suppose we have two isomorphic graphs $G_1$ and $H_1$, as well as two isomorphic graphs $G_2$ and $H_2$. Prove or disprove that $G_1 \cup G_2$ and $H_1 \cup H_2$ are also isomorphic.

---

破題觀念

1. 圖聯集（Graph Union）定義：$G_1 \cup G_2 = (V(G_1) \cup V(G_2), E(G_1) \cup E(G_2))$。
2. 同構關鍵：同構的充分必要條件是頂點集合間存在一個保持邊對應關係的一對一且映射（Bijective）映射函數。若頂點集交集結構（重疊方式）不同，聯集後的結構可能改變。
3. 反例證明法：若要否定（Disprove）一個命題，只需舉出一個具體反例。

---

詳細證明與反例

本命題為不成立（Disprove）。

反例構造：

取四個頂點皆為 $\{1, 2, 3\}$ 的圖：

• 令 $G_1 = (V_1, E_1)$，其中 $V_1 = \{1, 2, 3\}$, $E_1 = \{(1, 2)\}$ （單條邊圖）。
• 令 $H_1 = (V_1', E_1')$，其中 $V_1' = \{1, 2, 3\}$, $E_1' = \{(1, 2)\}$ （單條邊圖）。

8(a)

【觀念要點】
畫出遞迴樹（Recurrence Tree），統計各層成本（Cost）後求和。

【關鍵步驟】

1. 樹的結構分析：

   • 頂點（第 $0$ 層）成本為 $c \cdot n^2$。
   • 每層一個節點分裂為 $3$ 個子節點，子問題規模為原本的 $\lfloor n/4 \rfloor$。
   • 第 $i$ 層的節點數為 $3^i$，每個節點成本為 $c \cdot \left(\frac{n}{4^i}\right)^2 = c \cdot n^2 \cdot \left(\frac{1}{16}\right)^i$。

2. 每層成本總和：
   $Cost_i = 3^i \cdot c \cdot n^2 \cdot \left(\frac{1}{16}\right)^i = c \cdot n^2 \left(\frac{3}{16}\right)^i$

3. 遞迴樹深度：
   最底層深度為 $k = \log_4 n$。
   葉節點數量為 $3^k = 3^{\log_4 n} = n^{\log_4 3}$，葉節點總成本為 $\Theta(n^{\log_4 3})$。

4. 總成本求和：
   $T(n) = \sum_{i=0}^{\log_4 n - 1} c \cdot n^2 \left(\frac{3}{16}\right)^i + \Theta(n^{\log_4 3})$
   由於無窮等比級數 $\sum_{i=0}^{\infty} \left(\frac{3}{16}\right)^i = \frac{1}{1 - 3/16} = \frac{16}{13}$ 收斂為常數：
   $T(n) \le c \cdot n^2 \sum_{i=0}^{\infty} \left(\frac{3}{16}\right)^i + \Theta(n^{\log_4 3}) = \frac{16}{13} c \cdot n^2 + \Theta(n^{\log_4 3}) = \Theta(n^2)$

【答案】$T(n) = \Theta(n^2)$

---

8(b)

本題原始試題內文僅標示「注意：背面有試題」，缺乏具體的試題敘述與選項內容。以下在合理假設下，補充台聯大電機類離散數學高頻考題「二階非齊次線性遞迴關係」進行完整解析。

題目內容（合理假設）
已知遞迴關係式 $a_n - 5a_{n-1} + 6a_{n-2} = 4^n$ （其中 $n \ge 2$），且初始條件為 $a_0 = 2, a_1 = 7$。試判斷下列選項何者正確：
(A) 齊次解之特徵根為 $r = 1, 6$
(B) 特解的形式可設為 $a_n^{(p)} = C \cdot 4^n$
(C) 特解常數為 $C = 8$
(D) 通解為 $a_n = 2^n + 3^n + 4^{n+1}$
(E) $a_2 = 37$

---

核心觀念

本題考查**常係數線性非齊次遞迴關係（Linear Non-homogeneous Recurrence Relation with Constant Coefficients）**的求解步驟：

1. 齊次解 $a_n^{(h)}$：考慮對應的齊次方程式 $a_n - 5a_{n-1} + 6a_{n-2} = 0$，求解特徵方程式（Characteristic Equation） $r^2 - 5r + 6 = 0$ 得到特徵根 $r_1, r_2$。齊次解形式為 $a_n^{(h)} = c_1 r_1^n + c_2 r_2^n$。
2. 特解 $a_n^{(p)}$：根據非齊次項 $F(n) = 4^n$ 的形式，利用待定係數法（Method of Undetermined Coefficients）假設特解形式。若 $F(n) = d \cdot k^n$ 且 $k$ 不是特徵根，則設 $a_n^{(p)} = C \cdot k^n$。
3. 通解與初始條件：將齊次解與特解相加得到通解 $a_n = a_n^{(h)} + a_n^{(p)}$，再代入初始條件 $a_0, a_1$ 聯立求解未定常數 $c_1, c_2$。

---

解題方法

第一步：求解齊次解 $a_n^{(h)}$

考慮齊次方程式：
$a_n - 5a_{n-1} + 6a_{n-2} = 0$

寫出特徵方程式：
$r^2 - 5r + 6 = 0$

因式分解得：
$(r - 2)(r - 3) = 0 \implies r_1 = 2, r_2 = 3$

因此齊次解為：
$a_n^{(h)} = c_1 \cdot 2^n + c_2 \cdot 3^n$

第二步：求解特解 $a_n^{(p)}$

非齊次項為 $F(n) = 4^n$。因為底數 $4$ 不等於任何特徵根（$2$ 與 $3$），故假設特解為：
$a_n^{(p)} = C \cdot 4^n$

將特解代入原遞迴關係式：
$C \cdot 4^n - 5 C \cdot 4^{n-1} + 6 C \cdot 4^{n-2} = 4^n$

兩邊同除以 $4^{n-2}$：
$16C - 20C + 6C = 16$

同類項合併：
$2C = 16 \implies C = 8$

故特解為：
$a_n^{(p)} = 8 \cdot 4^n$