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

核心觀念

本題為離散機率與集合計數（Combinatorics & Discrete Probability）的經典題型，評量重點如下：

1. 有限集合的冪集大小（Size of Power Set）：
   若集合 $S$ 的元素個數為 $|S| = n$，則其所有子集所構成的冪集 $\mathcal{P}(S)$ 之大小為 $|\mathcal{P}(S)| = 2^n$。
2. 古典機率模型（Classical Probability Model）：
   在樣本空間中各基本事件發生機率均等（uniformly at random）的前提下，事件 $E$ 的機率為： $$P(E) = \frac{|E|}{|\Omega|}$$
3. 元素狀態分配計數法（Element-wise Assignment / Venn Diagram Method）：
   探討兩子集的包含關係 $A \subseteq B$ 時，可透過分析母集 $S$ 中每個元素 $x \in S$ 在兩集合狀態下的合理分佈位置進行計數。
4. 互異條件（Distinct Subsets）：
   題目關鍵字為 two different subsets，代表 $A \neq B$（無放回選取或限制 $A \neq B$），因此計算樣本空間與事件數時，必須排除 $A = B$ 的情形。

---

解題方法

步驟一：確定樣本空間大小 $|\Omega|$

由題目敘述，「從 $S$ 中均勻隨機選取兩個相異子集 $A$ 與 $B$」，意即選取一個有序對 $(A, B)$，其中 $A, B \in \mathcal{P}(S)$ 且 $A \neq B$。

• 子集 $A$ 有 $2^n$ 種選法。
• 子集 $B$ 必須與 $A$ 相異（$B \neq A$），因此有 $2^n - 1$ 種選法。

樣本空間大小為：

$$|\Omega| = 2^n \times (2^n - 1) = 4^n - 2^n$$

---

步驟二：計算滿足 $A \subseteq B$ 且 $A \neq B$ 的事件數 $|E|$

1. 先求滿足 $A \subseteq B$ 的有序對 $(A, B)$ 總數（含 $A = B$）：
   對於母集 $S$ 中的任意單一元素 $x$，在集合對 $(A, B)$ 中有 4 種可能歸屬：

   • $x \in A$ 且 $x \in B$
   • $x \notin A$ 且 $x \in B$
   • $x \notin A$ 且 $x \notin B$
   • $x \in A$ 且 $x \notin B$

   欲滿足 $A \subseteq B$，則不可出現「$x \in A$ 且 $x \notin B$」的情況。因此對於 $S$ 中的每一個元素 $x$，恰有 3 種合法的放置方式。

核心觀念

本題考查二階常係數非齊次線性遞迴關係式（Second-Order Linear Non-Homogeneous Recurrence Relation with Constant Coefficients）的求解。涉及的核心概念與定理如下：

1. 通解結構定理：
   非齊次遞迴關係式 $a_n - 5a_{n-1} + 6a_{n-2} = 2^n$ 的通解可表示為齊次解與特解之和： $$a_n = a_n^{(h)} + a_n^{(p)}$$
2. 齊次解（Homogeneous Solution）：
   對應特徵方程式（Characteristic Equation）之根為 $r_1, r_2$（相異實根）時，齊次解為 $a_n^{(h)} = c_1 r_1^n + c_2 r_2^n$。
3. 特解（Particular Solution）與根重疊（Resonance）修正：
   當非齊次項為 $f(n) = A \cdot \beta^n$ 型態，且 $\beta$ 為特徵方程式之單根（重數 $m = 1$）時，特解假設須乘上 $n^1$，即設為 $a_n^{(p)} = A \cdot n \cdot \beta^n$。
4. 待定係數法與初始條件：
   將特解代回原遞迴式求出待定係數，最後再代入初始條件 $a_0, a_1$ 解出任意常數 $c_1, c_2$。

---

解題方法

將遞迴關係式移項整理為標準型態：

$$a_n - 5a_{n-1} + 6a_{n-2} = 2^n, \quad \forall n \ge 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, \quad r_2 = 3$$

故齊次解型態為：

$$a_n^{(h)} = c_1 \cdot 2^n + c_2 \cdot 3^n \quad (c_1, c_2 \text{ 為常數})$$

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

觀察非齊次項 $f(n) = 2^n$，底數 $2$ 為特徵根之一（單重根），為避免與齊次解項線性相依，設特解型式為：

$$a_n^{(p)} = A \cdot n \cdot 2^n$$

將 $a_n^{(p)}$ 代入原遞迴式 $a_n - 5a_{n-1} + 6a_{n-2} = 2^n$：

$$A \cdot n \cdot 2^n - 5A(n - 1)2^{n-1} + 6A(n - 2)2^{n-2} = 2^n$$

等號兩邊同除以 $2^{n-2}$：

$$4An - 10A(n - 1) + 6A(n - 2) = 4$$

展開並合併同類項：

核心觀念

1. 組合數定義：
   題目所求之分式即為二項式係數（組合數）： $$\binom{p+13}{13} = \frac{(p+13)!}{p!\,13!} = \frac{(p+13)(p+12)\cdots(p+1)}{13!}$$
2. 質數模同餘之組合性質：
   • 連續 $13$ 個正整數的乘積必恰有一個為 $13$ 的倍數（當區間內不包含 $13^2$ 的倍數時）。
   • 盧卡斯定理（Lucas' Theorem）：設 $q$ 為質數，非負整數 $m, n$ 在 $q$ 進位下的表示法分別為 $m = (m_k \dots m_1 m_0)_q$ 與 $n = (n_k \dots n_1 n_0)_q$，則： $$\binom{m}{n} \equiv \prod_{i=0}^{k} \binom{m_i}{n_i} \pmod{q}$$ 其中約定當 $m_i < n_i$ 時，$\binom{m_i}{n_i} = 0$。

---

解題方法

方法一：直接展開與同餘化簡（最直觀的證明）

令 $m = p + 13$，則題目要求尋找正整數 $p$ 滿足：

$$\binom{m}{13} = \frac{m(m-1)(m-2)\cdots(m-12)}{13!} \equiv 7 \pmod{13}$$

步驟 1：選取適當的 $m$
欲使分子除以分母後的結果在模 $13$ 下同餘於 $7$，最簡單的構造法是令分子中「唯一含有質因數 $13$ 的那一項」恰好為 $7 \times 13 = 91$。

取 $m = 91$，則對應的 $p$ 為：

$$p = m - 13 = 91 - 13 = 78$$

此時 $p = 78$ 確為正整數。

步驟 2：驗證與證明
將 $p = 78$ 代入分子，分子的 $13$ 個連續整數為：

$$91 \times 90 \times 89 \times \cdots \times 80 \times 79$$

分母為：

$$13! = 13 \times 12 \times 11 \times \cdots \times 2 \times 1$$

將分子中的 $91$ 寫為 $7 \times 13$，並與分母的 $13$ 約分：

$$\frac{91 \times 90 \times 89 \times \cdots \times 79}{13 \times 12!} = 7 \times \frac{90 \times 89 \times \cdots \times 79}{12!}$$

觀察分子剩餘項在模 $13$ 下的同餘類：

$$\begin{aligned} 90 &= 91 - 1 \equiv -1 \pmod{13} \\ 89 &= 91 - 2 \equiv -2 \pmod{13} \\ &\;\;\vdots \\ 79 &= 91 - 12 \equiv -12 \pmod{13} \end{aligned}$$

因此剩餘 $12$ 項的乘積滿足：

$$90 \times 89 \times \cdots \times 79 \equiv (-1)(-2)\cdots(-12) = (-1)^{12} \cdot 12! = 12! \pmod{13}$$

將此結果代回原式：

$$\binom{91}{13} = 7 \times \frac{90 \times 89 \times \cdots \times 79}{12!} \equiv 7 \times \frac{12!}{12!} = 7 \times 1 \equiv 7 \pmod{13}$$

故正整數 $p = 78$ 滿足題目要求。

---

核心觀念

本題考查一階邏輯（First-Order Logic, Predicate Logic）中存在量詞（$\exists$）對於邏輯連接詞「且（$\wedge$）」的分散性質（Distributivity）以及邏輯等價（Logical Equivalence）的定義。

1. 邏輯等價（$\equiv$）：
   兩個謂詞邏輯式 $A \equiv B$ 代表在**任何論域（Universe of Discourse / Domain）以及任何謂詞詮釋（Interpretation）**下，兩者的真值皆完全相同（即雙向蘊含 $A \to B$ 與 $B \to A$ 皆為永真式）。若能找到至少一個反例（一個論域與一組謂詞）使得兩者真值不同，則等價關係不成立。
2. 存在量詞的分散性：
   • 存在量詞對「且（$\wedge$）」不可直接分配： $$\exists x (P(x) \wedge Q(x)) \not\equiv (\exists x P(x)) \wedge (\exists x Q(x))$$
   • 兩者僅具有**單向蘊含（Implication）**關係： $$\exists x (P(x) \wedge Q(x)) \implies (\exists x P(x)) \wedge (\exists x Q(x))$$ 但逆向蘊含 $(\exists x P(x)) \wedge (\exists x Q(x)) \implies \exists x (P(x) \wedge Q(x))$ 一般不成立。

---

解題方法

要證明敘述為 False，最佳切入點為構造具體反例（Counterexample）：

1. 尋找一個論域 $\mathcal{D}$ 與兩謂詞 $P(x), Q(x)$，使得：
   • 右式 $(\exists x P(x)) \wedge (\exists x Q(x))$ 為 True（即論域中存在某個個體具備性質 $P$，且存在某個個體具備性質 $Q$；但這兩者不必是同一個個體）。
   • 左式 $\exists x (P(x) \wedge Q(x))$ 為 False（即論域中不存在任何單一個體能同時兼具性質 $P$ 與 $Q$）。
2. 當左式為 False 但右式為 True 時，兩式真值不同，即可斷定兩者不具邏輯等價性。

反例構建：

• 取論域 $\mathcal{D} = \mathbb{Z}$（所有整數）。
• 定義 $P(x)$ 為「$x$ 是偶數（Even number）」。
• 定義 $Q(x)$ 為「$x$ 是奇數（Odd number）」。

驗證真值：

• 右式評估：
  • 存在偶數（例如 $x=2$），故 $\exists x P(x)$ 為 True。
  • 存在奇數（例如 $x=3$），故 $\exists x Q(x)$ 為 True。

核心觀念

• 函式完整性 (functional completeness)：一組布林運算子若能以它們組合表示所有布林函式（等價於能產生 $\lnot$, $\land$, $\lor$ 三個基本運算子），則稱為函式完整。
• 等價運算子：
  • $\oplus$ 為「異或」 (exclusive OR)，其真值表：$p\oplus q$ 為真當且僅當 $p$ 與 $q$ 的真值不相同。
  • $\leftrightarrow$ 為「同等」 (biconditional)，其真值表：$p\leftrightarrow q$ 為真當且僅當 $p$ 與 $q$ 的真值相同。
• 判斷方法：利用Post's functional completeness theorem，只要能從給定運算子構造出否定 $\lnot$，或能構造出任一非平凡的單變元函式（如恆真、恆假）即可證明完整；反之，若所有由該集合產生的函式皆保持某種對稱性（例如奇偶性），則該集合不完整。

---

解題方法

1. 觀察 $\oplus$ 與 $\leftrightarrow$ 的性質
   • $\oplus$ 為奇偶函式：對於任意輸入，其輸出為真當且僅當真值個數為奇數。
   • $\leftrightarrow$ 為偶奇函式的補：$p\leftrightarrow q = \lnot(p\oplus q)$，即輸出為真當且僅當真值個數為偶數。
2. 檢查閉合性
   任意由 $\oplus$、$\leftrightarrow$ 組成的合式公式，其真值僅取決於變數真值個數的奇偶性。
   • 若以 $\oplus$ 連接任意子式，奇偶性會翻轉。

核心觀念

本題主要測驗集合論中關於**集合基數（Cardinality）與可數無限集合（Countably Infinite Sets）**的定義與性質：

1. 基數相等（Equicardinality）：
   對於任意兩個集合 $A$ 與 $B$，若存在一個從 $A$ 映射到 $B$ 的雙射函數（Bijection，即一對一且映成），則稱兩集合的基數相等，記作 $|A| = |B|$。
2. 可數無限集合（Countably Infinite Set）：
   集合 $A$ 被稱為可數無限集合，若且唯若 $A$ 的基數與正整數集合 $\mathbb{Z}^+$（或自然數集合 $\mathbb{N}$）相同，亦即存在雙射 $f: A \to \mathbb{Z}^+$，記作 $|A| = |\mathbb{Z}^+| = \aleph_0$（Aleph-null）。
3. 等價關係的遞移律（Transitivity）：
   集合基數的相等關係是一種等價關係（Equivalence Relation）。若 $|A| = |\mathbb{Z}^+|$ 且 $|B| = |\mathbb{Z}^+|$，則由對稱律與遞移律可得 $|A| = |B|$。

---

解題方法

本題的論證切入點為回歸可數無限集合的嚴格數學定義：

1. 根據定義，若 $A$ 是可數無限集合，則存在雙射函數：

   $$f: A \to \mathbb{Z}^+$$

   因此 $|A| = |\mathbb{Z}^+| = \aleph_0$。

2. 同理，若 $B$ 是可數無限集合，則存在雙射函數：

   $$g: B \to \mathbb{Z}^+$$

   因此 $|B| = |\mathbb{Z}^+| = \aleph_0$。

3. 由於 $g$ 是雙射，其反函數 $g^{-1}: \mathbb{Z}^+ \to B$ 亦為雙射。考慮複合函數：

核心觀念

• 集合的勢 (Power Set)： 給定集合 $S$，其勢集合記為 $2^{S}$，定義為所有 $S$ 的子集合的集合。
• 康托爾定理 (Cantor’s Theorem)： 對任意集合 $X$，都有 $\lvert X\rvert < \lvert 2^{X}\rvert$，即 $X$ 與其勢集合之基數不相等且前者較小。
• 可數與不可數的定義：
  • 可數集合：與自然數集合 $\mathbb{N}$ 同構，基數為 $\aleph_{0}$。
  • 不可數集合：基數大於 $\aleph_{0}$ 的集合。

解題方法

1. 以康托爾對角線法證明 $\lvert S\rvert < \lvert 2^{S}\rvert$。
2. 若 $S$ 為無窮集合，則 $\lvert S\rvert \ge \aleph_{0}$。根據康托爾定理，$\lvert 2^{S}\rvert$ 必嚴格大於 $\lvert S\rvert$，因此 $\lvert 2^{S}\rvert > \aleph_{0}$，即 $2^{S}$ 為不可數集合。

核心觀念

• 關係 (Relation)：在集合 $A$ 上的二元關係 $R\subseteq A\times A$。
• 傳遞性 (Transitivity)：$R$ 為傳遞的當且僅當

$\forall a,b,c\in A,\;(aRb\land bRc)\Rightarrow aRc.$

• 關係的平方 $R^{2}$：$R^{2}=R\circ R=\{(a,c)\mid\exists b\in A,\;aRb\land bRc\}$。
• 需要驗證：「若 $R$ 為傳遞，則 $R^{2}$ 必為傳遞」的真偽。

---

解題方法
直接以定義推導的方式證明 $R^{2}$ 為傳遞。

1. 假設 $R$ 為傳遞。
2. 任取 $(a,c)\in R^{2}$ 與 $(c,d)\in R^{2}$。依照 $R^{2}$ 的定義，存在中介元素 $b_{1},b_{2}\in A$ 使得

$aRb_{1},\; b_{1}c \quad\text{且}\quad cRb_{2},\; b_{2}d.$

3. 先利用傳遞性將 $b_{1}c$ 與 $cRb_{2}$ 結合：

$b_{1}c\land cRb_{2}\;\Longrightarrow\; b_{1}Rb_{2}.$

4. 再將 $aRb_{1}$ 與 $b_{1}Rb_{2}$ 結合：

核心觀念

• Big‑O 定義：對正函數 $f,g:\mathbb N\to\mathbb R^+$，寫 $f\in O(g)$ 表示存在常數 $c>0$ 與 $n_0\in\mathbb N$，使得對所有 $n\ge n_0$，都有 $f(n)\le c\cdot g(n)$。
• 偏序（partial order）：在集合 $S$ 上的二元關係 $R\subseteq S\times S$ 必須同時具備
  1. 自反性：$\forall x\in S,\;(x,x)\in R$
  2. 反對稱性：$\forall x,y\in S,\;(x,y)\in R\land(y,x)\in R\;\Rightarrow\;x=y$
  3. 傳遞性：$\forall x,y,z\in S,\;(x,y)\in R\land(y,z)\in R\;\Rightarrow\;(x,z)\in R$

解題方法
將題目所給集合視為關係
$R=\{(f_1,f_2)\mid f_1\in O(f_2)\}$
在所有正函數 $f:\mathbb N\to\mathbb R^+$ 上檢驗 $R$ 是否滿足上述三個條件。

1. 自反性：對任意 $f$，取常數 $c=1$、$n_0=1$，即有 $f(n)\le 1\cdot f(n)$，故 $f\in O(f)$，$(f,f)\in R$。自反性成立。

核心觀念

• 關係 (Relation)：在集合 $A$ 上的二元關係 $R\subseteq A\times A$ 可視為有向圖 (digraph)，其頂點為集合 $A$，若 $(a,b)\in R$ 則在圖中加入一條從 $a$ 指向 $b$ 的有向邊。
• 圖同構 (Isomorphism)：兩個有向圖 $G_1=(V_1,E_1)$、$G_2=(V_2,E_2)$ 若存在一個雙射 $\varphi:V_1\to V_2$ 使得對所有有向邊 $(u,v)\in E_1$，恰有 $(\varphi(u),\varphi(v))\in E_2$，則稱 $G_1$ 與 $G_2$ 同構。圖同構僅比較結構，不關心頂點名稱。
• 關係的等價與不同：兩個關係 $R_1,R_2$ 若 $R_1\neq R_2$，表示它們在集合 $A\times A$ 的元素（即有向邊）上至少有一處不同。然而，若僅重新排列頂點名稱，就可能得到同樣的邊結構。

解題方法

1. 驗證命題的必要條件：若 $R_1\neq R_2$ 必然導致其圖不可同構，則必須證明不存在任何頂點重新標號能把 $R_1$ 的圖變成 $R_2$ 的圖。
2. 舉反例：若能找到一組集合 $A$、兩個不同關係 $R_1,R_2$，使得它們的有向圖結構相同（僅頂點名稱不同），則命題為偽。

核心觀念

• 平面圖 (planar graph)：可在平面上畫而不產生交叉邊的無向圖。
• Euler 公式：對於連通的平面圖 $G=(V,E)$，有
  $|V|-|E|+|F|=2$
  其中 $|F|$ 為面數（包括外圍面）。
• 握手引理 (handshaking lemma)：
  $\sum_{v\in V}\deg(v)=2|E|.$
• 簡單平面圖的面度下界：每個面至少被三條邊圍繞，故
  $3|F|\le 2|E|.$

---

解題方法

1. 令 $|V|=n$，題設每個頂點的度皆為 $5$，使用握手引理得到
   $5n = \sum_{v\in V}\deg(v)=2|E|\;\Longrightarrow\;|E|=\frac{5n}{2}.$
2. 由簡單平面圖的面度下界 $3|F|\le 2|E|$，代入 $|E|$：
   $3|F|\le 2\cdot\frac{5n}{2}=5n\;\Longrightarrow\;|F|\le\frac{5n}{3}.$
3. 將 $|E|=\frac{5n}{2}$ 代入 Euler 公式
   $n-\frac{5n}{2}+|F|=2 \;\Longrightarrow\;|F|=2+\frac{5n}{2}-n=2+\frac{3n}{2}= \frac{3n+4}{2}.$
4. 結合第 2 步與第 3 步的兩個 $|F|$ 表式：
   $\frac{3n+4}{2}\le\frac{5n}{3}.$
   兩邊同乘 $6$ 後得到

核心觀念

• 色彩數 (chromatic number) $\chi(G)$：將圖 $G$ 的頂點著色，使相鄰頂點不同色所需的最少顏色數。
• 邊刪除後的色彩數：若對任意邊 $e\in E(G)$，圖 $G-e$ 的色彩數 $\chi(G-e)\le k-1$，說明 $G$ 在刪除任一邊後就不需要 $k$ 種顏色。
• $k$‑臨界圖 (k‑critical graph)：滿足 $\chi(G)=k$，且對所有邊 $e$， $\chi(G-e)=k-1$。本題的假設即是 $G$ 為 $k$‑臨界圖的弱化形式。
• 度 (degree) 的下界：在 $k$‑臨界圖中，有一個著名的性質：$\displaystyle \delta(G)\ge k-1$，其中 $\delta(G)$ 為圖的最小度。此題要求證明這一性質。

---

解題方法

1. 反證：假設存在頂點 $v$ 的度 $d(v)\le k-2$。
2. 選取相鄰邊：若 $d(v)=0$，則 $G$ 本身已可用 1 色著色，與 $\chi(G)=k\ge2$ 矛盾；故必有至少一條相鄰邊 $uv\in E(G)$。
3. 考慮刪除該邊：根據題目條件，$G' = G-uv$ 的色彩數 $\chi(G')\le k-1$。因此存在一個恰好使用 $k-1$ 種顏色的合法著色 $c:V(G')\to\{1,\dots,k-1\}$。
4. 分析 $v$ 的可用顏色：在 $G'$ 中，$v$ 的鄰居至多 $d(v)\le k-2$ 個。