112 年 國立臺灣大學電機工程研究所丙組《離散數學》

核心觀念：鴿籠原理（Pigeonhole Principle）

要保證存在四個頂點同色的矩形（即尋找兩列 $i, j$，在相同的兩行 $k, l$ 處擁有相同的顏色），我們可以分析每一行的顏色排列。

---

詳細證明

1. 定義列與行的顏色結構：
   consider 一個 $13 \times 13$ 的格子點集。每一行由 13 個點組成，每個點塗上 3 種顏色之一（紅、藍、綠）。
   由鴿籠原理，每一行 13 個點中，至少有一種顏色出現的次數 $\ge \lceil 13 / 3 \rceil = 5$ 次。

2. 選取代表顏色與點對：
   對第 $j$ 行（$1 \le j \le 13$），設出現至少 5 次的顏色為 $c_j \in \{\text{紅}, \text{藍}, \text{綠}\}$。
   在此行中選擇 5 個塗有顏色 $c_j$ 的位置，這 5 個位置可以形成 $\binom{5}{2} = 10$ 個列對（column pairs）。
   因此，每一行都可以標註一個有序對 $(c_j, S_j)$，其中 $c_j$ 為顏色，$S_j$ 為從 13 列中選出的 2 列組合，滿足在第 $j$ 行中這兩列的點顏色皆為 $c_j$。

3. 計算總數與鴿籠原理：

   • 顏色有 3 種選擇。
   • 從 13 列中選出 2 列的組合數為 $\binom{13}{2} = 78$ 種。
   • 因此，可能的顏色與列對組合 $(c, S)$ 總數為 $3 \times 78 = 234$ 種。

4. 調整與縮小範圍（更強的 pigeonhole 劃分）：
   共有 13 行。由鴿籠原理，13 行中至少有 $\lceil 13 / 3 \rceil = 5$ 行具有相同的代表顏色 $C \in \{\text{紅}, \text{藍}, \text{綠}\}$。
   不失一般性，設這 5 行各自選出了 5 個顏色為 $C$ 的列位置。

核心觀念

本題考驗**二階非齊次遞迴關係式（Second-order Non-homogeneous Recurrence Relation）**的精確解法。解題關鍵涵蓋以下核心觀念與步驟：

1. 變數變換（Change of Variables）：對於形式如 $T(n) = T(n/2) + 2T(n/4) + f(n)$ 且限定 $n$ 為 $2$ 的次方之遞迴式，可令 $n = 2^k$（即 $k = \log_2 n$），將對分型遞迴轉化為常係數線性遞迴關係式 $a_k = a_{k-1} + 2a_{k-2} + g(k)$。
2. 齊次解（Homogeneous Solution）：求解對應齊次方程 $a_k - a_{k-1} - 2a_{k-2} = 0$ 之特徵方程式（Characteristic Equation），求得特徵根後構建齊次解 $a_k^{(h)}$。
3. 特解（Particular Solution）：觀察非齊次項 $g(k)$。當非齊次項包含 $2^k$，且 $2$ 恰為特徵根之一時，使用**待定係數法（Method of Undetermined Coefficients）**需乘以 $k$，設特解形式為 $a_k^{(p)} = A \cdot k \cdot 2^k$。
4. 初始條件與通解（General Solution & Initial Conditions）：組合通解 $a_k = a_k^{(h)} + a_k^{(p)}$，利用初始條件 $T(1)$ 與 $T(2)$ 求解待定常數，最後還原變數至 $T(n)$。

---

解題方法

步驟一：變數變換

因為 $n$ 為 $2$ 的次方，令 $n = 2^k$（$k = 0, 1, 2, \dots$），並定義新數列 $a_k = T(2^k)$。
將 $n = 2^k$ 代入原遞迴關係式：
$T(2^k) = T(2^{k-1}) + 2T(2^{k-2}) + \frac{3 \cdot 2^k}{2}$
整理得：
$a_k = a_{k-1} + 2a_{k-2} + 3 \cdot 2^{k-1}, \quad \text{for } k \ge 2$
對應的初始條件為：

• $a_0 = T(2^0) = T(1) = 2$
• $a_1 = T(2^1) = T(2) = 3$

步驟二：求解齊次解 $a_k^{(h)}$

考慮齊次遞迴關係式：
$a_k - a_{k-1} - 2a_{k-2} = 0$
寫出特徵方程式：
$r^2 - r - 2 = 0 \implies (r - 2)(r + 1) = 0$
解得特徵根 $r_1 = 2, \, r_2 = -1$。
故齊次解為：
$a_k^{(h)} = C_1 \cdot 2^k + C_2 \cdot (-1)^k$

步驟三：求解特解 $a_k^{(p)}$

原式的非齊次項為 $g(k) = 3 \cdot 2^{k-1} = \frac{3}{2} \cdot 2^k$。
由於非齊次項的底數 $2$ 與特徵根 $r_1 = 2$ 重覆（單根），特解形式需乘上 $k$：
$a_k^{(p)} = A \cdot k \cdot 2^k$

將 $a_k^{(p)}$ 代入遞迴式 $a_k - a_{k-1} - 2a_{k-2} = 3 \cdot 2^{k-1}$：
$A \cdot k \cdot 2^k - A \cdot (k-1) \cdot 2^{k-1} - 2A \cdot (k-2) \cdot 2^{k-2} = 3 \cdot 2^{k-1}$
等號兩邊同除以 $2^{k-2}$：
$4Ak - 2A(k-1) - 2A(k-2) = 6$
展開並化簡左式：

核心觀念

本題為數論（Number Theory）的經典題型，核心考點在於利用質因數分解將大模數簡化，並結合以下三大數論定理：

1. 中國剩餘定理（Chinese Remainder Theorem, CRT）：
   若正整數 $N$ 可分解為兩兩互質的質因數乘積 $N = m_1 m_2 \cdots m_k$，則要求解 $x \pmod N$，可先求出 $x$ 在各小模數 $m_i$ 下的同餘值，再組合出唯一解 $x \pmod N$。
2. 費馬小定理（Fermat's Little Theorem, FLT）：
   若 $p$ 為質數，且整數 $a$ 與 $p$ 互質（$\gcd(a, p) = 1$），則 $a^{p-1} \equiv 1 \pmod p$。
3. 歐拉判別法（Euler's Criterion）與二次剩餘（Quadratic Residue）：
   若 $p$ 為奇質數且 $\gcd(a, p) = 1$，則 $a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p$，其中同餘值僅可能為 $1$（當 $a$ 為模 $p$ 之二次剩餘）或 $-1 \equiv p-1$（當 $a$ 為二次非剩餘）。

---

解題方法

第一步：質因數分解與互質判定

將模數 $182$ 進行質因數分解：
$182 = 2 \times 7 \times 13$
因為 $2, 7, 13$ 兩兩互質，且題目給定 $p$ 為大於 $20$ 的質數，故 $p$ 不可能為 $2, 7, 13$。因此：
$\gcd(p, 2) = 1, \quad \gcd(p, 7) = 1, \quad \gcd(p, 13) = 1$

第二步：分別求出 $p^6$ 對各質因數的同餘值

1. 模 $2$ 系統：
   $p > 20$ 為質數，故 $p$ 為奇數，即 $p \equiv 1 \pmod 2$。
   兩邊取 $6$ 次方得到：
   $p^6 \equiv 1^6 \equiv 1 \pmod 2$

2. 模 $7$ 系統：
   因為 $7$ 為質數且 $\gcd(p, 7) = 1$，由費馬小定理可知：
   $p^{7-1} = p^6 \equiv 1 \pmod 7$

3. 模 $13$ 系統：
   因為 $13$ 為質數且 $\gcd(p, 13) = 1$，由費馬小定理可知：
   $p^{13-1} = p^{12} \equiv 1 \pmod{13}$
   改寫為平方形式 $(p^6)^2 \equiv 1 \pmod{13}$。由於 $\mathbb{Z}_{13}$ 為一體（Field），同餘方程式 $x^2 \equiv 1 \pmod{13}$ 恰有兩個解：
   $p^6 \equiv 1 \pmod{13} \quad \text{與} \quad p^6 \equiv -1 \equiv 12 \pmod{13}$
   （亦可由歐拉判別法 $p^6 = p^{(13-1)/2} \equiv \left(\frac{p}{13}\right) \pmod{13}$ 說明，值取決於 $p$ 是否為模 $13$ 之二次剩餘）。

第三步：證明兩種模 $13$ 的情況均真實存在

為確保解答無瑕疵，需證明存在大於 $20$ 的質數 $p$ 能分別滿足上述兩個同餘值：

• 當 $p = 23$（質數且 $>20$）時，$23 \equiv 10 \pmod{13}$。因為 $10 \equiv 6^2 \pmod{13}$ 為二次剩餘，故 $23^6 \equiv 10^6 \equiv (6^2)^3 = 6^6 \equiv 1 \pmod{13}$。
• 當 $p = 31$（質數且 $>20$）時，$31 \equiv 5 \pmod{13}$。因為 $5^2 = 25 \equiv -1 \pmod{13}$，故 $31^6 \equiv 5^6 \equiv (-1)^3 = -1 \equiv 12 \pmod{13}$。

核心觀念

本題為經典的離散數學綜合考題，涵蓋命題邏輯（Propositional Logic）、量詞邏輯（Predicate Logic）、功能完整集（Functionally Complete Set）、集合論之可數性（Countability of Sets）、關係與閉包（Relations and Closures）、以及偏序關係（Partial Orderings）。重點觀念包括：

1. 邏輯等價性（Logical Equivalence）：兩命題在所有真值組合下之真假值皆相同。
2. 量詞推論與等價（Quantified Equivalence）：全稱量詞 $\forall$ 與存在量詞 $\exists$ 對條件句的分配率與非對稱等價性。
3. 功能完整集（Functionally Complete Set）：僅需單一邏輯運算子（如 NAND 或 NOR）即可表達所有邏輯函數。
4. 集合的可數性（Countability）：若存在雙射 $f: \mathbb{A} \rightarrow \mathbb{B}$ 且 $\mathbb{A}$ 為可數集，則 $\mathbb{B}$ 為可數集；有限個可數集的笛卡兒積（Cartesian Product）仍為可數集。
5. 關係的性質與閉包（Relations and Closures）：偏序關係需滿足自反性、反對稱性與遞移性；對稱閉包（Symmetric Closure）不一定能保持關係的遞移性。
6. 函數的偏序關係（Pointwise Partial Order）：點對點不等式關係在函數空間上構成偏序關係。

---

解題方法

針對每一小題，採用嚴謹的邏輯推導或反例驗證法（Counterexample Method）：

• 對於邏輯等價問題：透過真值指派（Truth Assignment）找出一組矛盾賦值，證明兩者不等價。
• 對於量詞邏輯問題：構造具體的論域（Domain）與謂詞定義（Predicate Definitions）導出反例。
• 對於功能完整集問題：引述單一運算子（Sheffer Stroke / Peirce Arrow）的反例否決敘述。
• 對於集合可數性問題：建立與已知可數集（如 $\mathbb{Q} \times \mathbb{Q}$）的雙射關係（Bijection）。
• 對於關係性質問題：檢驗自反性（Reflexivity）、對稱性（Symmetry）、反對稱性（Antisymmetry）與遞移性（Transitivity），或構造小規模集合之反例。

---

選項分析

(a) 敘述分析

• 題目原文：$(p \rightarrow q) \land r$ and $p \rightarrow (q \land r)$ are equivalent.
• 判斷：False
• 詳細推導：
  將兩命題分別化簡為與／或／非（AND-OR-NOT）形式：
  • 前者：$(p \rightarrow q) \land r \equiv (\neg p \lor q) \land r \equiv (\neg p \land r) \lor (q \land r)$
  • 後者：$p \rightarrow (q \land r) \equiv \neg p \lor (q \land r)$
    設定真值指派：令 $p = \text{False}, q = \text{False}, r = \text{False}$。
  • 前者真值：$(\text{False} \rightarrow \text{False}) \land \text{False} \equiv \text{True} \land \text{False} \equiv \text{False}$
  • 後者真值：$\text{False} \rightarrow (\text{False} \land \text{False}) \equiv \text{False} \rightarrow \text{False} \equiv \text{True}$
    因為存在真值不一致的情形，故兩命題不等價。

(b) 敘述分析

• 題目原文：$\forall x (P(x) \rightarrow Q(x)) \equiv \exists x P(x) \rightarrow \exists x Q(x)$.
• 判斷：False
• 詳細推導：
  檢驗邏輯雙向蘊涵關係。雖然 $\forall x (P(x) \rightarrow Q(x)) \implies (\exists x P(x) \rightarrow \exists x Q(x))$ 成立，但反向蘊涵並不成立。
  構造反例：
  • 設定論域 $U = \{1, 2\}$。
  • 定義謂詞：$P(1) = \text{True}, Q(1) = \text{False}$；$P(2) = \text{False}, Q(2) = \text{True}$。
  • 計算右式：$\exists x P(x)$ 為 $\text{True}$（因為 $P(1)$ 為真）；$\exists x Q(x)$ 為 $\text{True}$（因為 $Q(2)$ 為真）。因此右式 $\exists x P(x) \rightarrow \exists x Q(x) \equiv \text{True} \rightarrow \text{True} \equiv \text{True}$。
  • 計算左式：對於 $x = 1$，$P(1) \rightarrow Q(1) \equiv \text{True} \rightarrow \text{False} \equiv \text{False}$，故全稱敘述 $\forall x (P(x) \rightarrow Q(x))$ 為 $\text{False}$。
    因為右式為真而左式為假，兩者不等價。

(c) 敘述分析

• 題目原文：In propositional logic, a functionally complete set must have at least two operators.
• 判斷：False
• 詳細推導：
  根據功能完整集（Functionally Complete Set）的定義，只要一個運算子集合能夠組合出所有的真值函數，該集合即為功能完整集。
  存在僅包含單一運算子的功能完整集：
  1. 謝費爾豎線（NAND 運算子，$\uparrow$）：$\{\uparrow\}$ 為功能完整集，例如 $\neg p \equiv p \uparrow p$、$p \land q \equiv (p \uparrow q) \uparrow (p \uparrow q)$。
  2. 皮爾斯箭號（NOR 運算子，$\downarrow$）：$\{\downarrow\}$ 亦為功能完整集。
     因此，功能完整集不必包含至少兩個運算子。

(d) 敘述分析

• 題目原文：If $2^\mathbb{N}$ is uncountable, then $\mathbb{S}$ must be infinite and countable.
• 判斷：False
• 詳細推導：

核心觀念

1. 握手定理（Handshaking Lemma）：
   在任意無向圖 $G = (V, E)$ 中，所有頂點的度數（degree）總和等於邊數的兩倍：
   $\sum_{v \in V} \text{deg}(v) = 2|E|$
   若圖中每個頂點的度數皆為 $k$（即 $k$-正則圖 $k$-regular graph），則 $k|V| = 2|E|$。此式代表 $k|V|$ 必須為偶數，且頂點數 $|V| = \frac{2|E|}{k}$ 必須為正整數。

2. 平面圖的邊數上限定理（Edge Bound for Planar Graphs）：
   對於任意頂點數 $|V| \ge 3$ 的簡單平面圖 $G = (V, E)$（簡單圖指無自環與重邊的圖），其每個面至少由 3 條邊圍成（$2|E| \ge 3|F|$）。結合歐拉公式（Euler's Formula）$|V| - |E| + |F| = 2$，可推導出邊數上限定理：
   $|E| \le 3|V| - 6$
   對於不連通的簡單平面圖（設有 $k$ 個連通元件），邊數上限為 $|E| \le 3|V| - 6k \le 3|V| - 6$。若一個簡單圖的邊數超過此上限，則該圖絕對無法繪製在平面上而不發生邊相交的情況。

---

解題方法

本題基於離散數學之標準定義（預設為無自環與重邊的簡單圖），分為兩個小題進行嚴格證明：

1. 第 (a) 小題（邊數 $|E| = 24$）：
   利用握手定理，代入已知條件 $\text{deg}(v) = 5$ 與 $|E| = 24$，計算頂點數 $|V|$。若求出之頂點數非整數，即可證明此圖在圖論基本定義下根本不存在。

2. 第 (b) 小題（邊數 $|E| = 25$）：
   首先以握手定理計算 $|E| = 25$ 時對應的頂點數 $|V| = 10$。求得正整數頂點數後，進一步使用平面圖邊數上限定理（$|E| \le 3|V| - 6$）進行檢驗。將 $|V| = 10$ 代入計算平面圖所能容許的最大邊數，比較後證明其違反平面圖限制。

---

選項分析

• (a) 評估 $G$ 是否可能恰有 24 條邊：
  • 證明：
    設 $G = (V, E)$ 為符合題意之圖，每個頂點度數 $\text{deg}(v) = 5$。
    根據握手定理：
    $\sum_{v \in V} \text{deg}(v) = 5|V| = 2|E|$
    若邊數 $|E| = 24$，代入上式得：
    $5|V| = 2 \times 24 = 48 \implies |V| = \frac{48}{5} = 9.6$

核心觀念

1. 握手定理（Handshaking Lemma）：
   在任意無向圖 $G = (V, E)$ 中，所有頂點的度數（degree）總和等於邊數的兩倍：
   $\sum_{v \in V} \text{deg}(v) = 2|E|$
   若圖中每個頂點的度數皆為 $k$（即 $k$-正則圖 $k$-regular graph），則 $k|V| = 2|E|$。此式代表 $k|V|$ 必須為偶數，且頂點數 $|V| = \frac{2|E|}{k}$ 必須為正整數。

2. 平面圖的邊數上限定理（Edge Bound for Planar Graphs）：
   對於任意頂點數 $|V| \ge 3$ 的簡單平面圖 $G = (V, E)$（簡單圖指無自環與重邊的圖），其每個面至少由 3 條邊圍成（$2|E| \ge 3|F|$）。結合歐拉公式（Euler's Formula）$|V| - |E| + |F| = 2$，可推導出邊數上限定理：
   $|E| \le 3|V| - 6$
   對於不連通的簡單平面圖（設有 $k$ 個連通元件），邊數上限為 $|E| \le 3|V| - 6k \le 3|V| - 6$。若一個簡單圖的邊數超過此上限，則該圖絕對無法繪製在平面上而不發生邊相交的情況。

---

解題方法

本題基於離散數學之標準定義（預設為無自環與重邊的簡單圖），分為兩個小題進行嚴格證明：

1. 第 (a) 小題（邊數 $|E| = 24$）：
   利用握手定理，代入已知條件 $\text{deg}(v) = 5$ 與 $|E| = 24$，計算頂點數 $|V|$。若求出之頂點數非整數，即可證明此圖在圖論基本定義下根本不存在。

2. 第 (b) 小題（邊數 $|E| = 25$）：
   首先以握手定理計算 $|E| = 25$ 時對應的頂點數 $|V| = 10$。求得正整數頂點數後，進一步使用平面圖邊數上限定理（$|E| \le 3|V| - 6$）進行檢驗。將 $|V| = 10$ 代入計算平面圖所能容許的最大邊數，比較後證明其違反平面圖限制。

---

選項分析

• (a) 評估 $G$ 是否可能恰有 24 條邊：
  • 證明：
    設 $G = (V, E)$ 為符合題意之圖，每個頂點度數 $\text{deg}(v) = 5$。
    根據握手定理：
    $\sum_{v \in V} \text{deg}(v) = 5|V| = 2|E|$
    若邊數 $|E| = 24$，代入上式得：
    $5|V| = 2 \times 24 = 48 \implies |V| = \frac{48}{5} = 9.6$

要證明著色數 $\chi(G) \ge 5$ 或是找出反例，本題結論為存在反例（即該命題不成立）。

關鍵觀念與解題脈絡

1. 著色數上界（Brooks' Theorem）：若連通圖 $G$ 不是完全圖 $K_{\Delta+1}$ 且不是奇數長度的環 $C_{2k+1}$，則其著色數 $\chi(G) \le \Delta(G)$。
2. 反例構造：題目給定 $G$ 為 5-正則圖（每節點度數為 5），其最大度數 $\Delta(G) = 5$。若 $G$ 不是 $K_6$，由 Brooks 定理可知 $\chi(G) \le 5$。若進一步構造出可 2-著色、3-著色或 4-著色之 5-正則圖，即構成反例。