108 年 國立臺灣大學工程科學及海洋工程學系碩士班丁組《離散數學（A）》

核心觀念

本題旨在考察數論（Number Theory）中的基本基礎定理與經典證明手法，核心觀念包含：

1. 質數（Prime Number）定義：大於 $1$ 的整數 $p$，若其正因數僅有 $1$ 與 $p$ 本身，則稱 $p$ 為質數。
2. 算術基本定理（Fundamental Theorem of Arithmetic）之推論：任何大於 $1$ 的正整數 $n$，皆可唯一分解為質數的乘積。意即：任何大於 $1$ 的整數至少存在一個質因數。
3. 整除之運算性質：若整數 $d$ 同時整除 $a$ 與 $b$（記做 $d \mid a$ 且 $d \mid b$），則對於任意整數 $x, y$，皆有 $d \mid (ax + by)$。
4. 反證法（Proof by Contradiction）：先假設欲證命題之否定成立，透過嚴謹的邏輯推導得出矛盾（如 $d \mid 1$ 但 $d > 1$），進而證實原命題必然成立。

---

解題方法

採用經典的歐幾里得（Euclid）反證法進行證明：

步驟一：設定反證假設
假設質數的數量是有限的，將世界上所有的質數由小到大排列並窮舉登記為有限集合：
$P = \{p_1, p_2, p_3, \dots, p_k\}$
其中 $k$ 為質數的總個數，$p_1 = 2, p_2 = 3, p_3 = 5, \dots$。

步驟二：構造輔助整數
構造一個新的正整數 $N$，定義為所有已知質數的乘積再加上 $1$：
$N = (p_1 \cdot p_2 \cdot p_3 \cdots p_k) + 1$

步驟三：分析 $N$ 的質因數
由於 $p_1 \ge 2$，明顯可知 $N > 1$。
根據算術基本定理，整數 $N$ 必須至少有一個質因數，設此質因數為 $q$（即 $q$ 為質數，且 $q \mid N$）。

步驟四：導出邏輯矛盾
由於集合 $P = \{p_1, p_2, \dots, p_k\}$ 已包含世界上「所有」的質數，故質數 $q$ 必須屬於集合 $P$，意即存在某個 $i \in \{1, 2, \dots, k\}$ 使得 $q = p_i$。
由此可得：
$q \mid (p_1 \cdot p_2 \cdot p_3 \cdots p_k)$

已知 $q \mid N$，利用整除的線性組合性質，可知 $q$ 亦能整除兩者之差：
$q \mid \left[ N - (p_1 \cdot p_2 \cdot p_3 \cdots p_k) \right]$
將 $N$ 的定義代入上式：

核心觀念

本題考查機率論中的基礎定義與核心定理，重點包含以下觀念：

1. 條件機率定義（Definition of Conditional Probability）：
   對任意兩事件 $E_1, E_2$，在 $\Pr(E_2) > 0$ 的前提下，定義在 $E_2$ 發生的條件下 $E_1$ 發生的條件機率為：
   $\Pr(E_1|E_2) = \frac{\Pr(E_1 \cap E_2)}{\Pr(E_2)}$
2. 機率乘法公式（Multiplication Rule）：
   由條件機率定義改寫可得聯合機率（Joint Probability）：
   $\Pr(E_1 \cap E_2) = \Pr(E_1)\Pr(E_2|E_1) = \Pr(E_2)\Pr(E_1|E_2)$
3. 全機率定理（Law of Total Probability）：
   若事件 $A$ 與其對立事件 $\bar{A}$ 構成樣本空間 $S$ 的一組分割（Partition），即 $A \cap \bar{A} = \emptyset$ 且 $A \cup \bar{A} = S$，則對任意事件 $B$，其發生的總機率可分解為：
   $\Pr(B) = \Pr(A \cap B) + \Pr(\bar{A} \cap B) = \Pr(A)\Pr(B|A) + \Pr(\bar{A})\Pr(B|\bar{A})$
4. 貝氏定理（Bayes' Theorem）：
   結合條件機率定義與全機率定理，用以由事前機率（Prior Probability）與似然值（Likelihood）推導出事後機率（Posterior Probability）。

---

解題方法

本題為證明題，採取由右式（RHS）經由定理化簡推導至左式（LHS）的直接證明法。

前提假設：
假設 $\Pr(A) > 0$、$\Pr(\bar{A}) > 0$ 且 $\Pr(B) > 0$。

詳細推導步驟：

1. 分子化簡（套用機率乘法公式）：
   根據條件機率定義，$\Pr(B|A) = \frac{\Pr(A \cap B)}{\Pr(A)}$，等式兩邊同乘以 $\Pr(A)$ 得：
   $\Pr(A)\Pr(B|A) = \Pr(A \cap B)$

2. 分母化簡（套用全機率定理）：
   因為 $A$ 與 $\bar{A}$ 互斥且聯集為全域 $S$，故事件 $B$ 可表為：
   $B = B \cap S = B \cap (A \cup \bar{A}) = (A \cap B) \cup (\bar{A} \cap B)$
   由於 $(A \cap B)$ 與 $(\bar{A} \cap B)$ 為互斥事件，由機率可加性公理：
   $\Pr(B) = \Pr(A \cap B) + \Pr(\bar{A} \cap B)$
   分別對兩項套用機率乘法公式：

   • $\Pr(A \cap B) = \Pr(A)\Pr(B|A)$

核心觀念

本題考查整數的奇偶性（Parity）、反證法（Proof by Contradiction）以及排列（Permutation）總和的不變性。

主要運用的定義與定理如下：

1. 整數乘積的奇偶性：若干個整數的乘積若為奇數，當且僅當每一個整數因子皆為奇數。若乘積中存在至少一個偶數因子，則整體乘積必為偶數。
2. 奇偶數連加規律：$n$ 個奇數相加，若 $n$ 為奇數，則其總和必為奇數；若 $n$ 為偶數，則其總和必為偶數。
3. 排列求和不變性：若 $a_1, a_2, \dots, a_n$ 是 $1, 2, \dots, n$ 的一個排列，則 $\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} i$。

---

解題方法

採用**反證法（Proof by Contradiction）**切入推導。

完整證明步驟：

1. 提出反面假設：
   假設乘積 $P = (1-a_1)(2-a_2)\dots(n-a_n)$ 為奇數。

2. 分析各項因子的奇偶性：
   根據整數乘積奇偶性定理，若 $P$ 為奇數，則每一個因子 $(i - a_i)$ 都必須是奇數（對所有 $i = 1, 2, \dots, n$）。

3. 計算所有因子的總和：
   將這 $n$ 個因子全部相加，設總和為 $S$：
   $S = \sum_{i=1}^{n} (i - a_i)$
   拆開求和號並利用加法交換律與結合律：
   $S = \sum_{i=1}^{n} i - \sum_{i=1}^{n} a_i$
   因為 $a_1, a_2, \dots, a_n$ 為 $1, 2, \dots, n$ 的一個排列，其元素的集合與 $\{1, 2, \dots, n\}$ 完全相等，故：
   $\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} i$
   代入可得：
   $S = 0$

核心觀念

本題考查離散數學組合學中的鴿籠原理（Pigeonhole Principle）、數論的同餘與奇偶性（Parity），以及解析幾何中的中點公式。

1. 中點公式：在三維空間中，設兩點 $P_1 = (x_1, y_1, z_1)$ 與 $P_2 = (x_2, y_2, z_2)$，其連線中點座標為：
   $M = \left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}, \frac{z_1 + z_2}{2}\right)$
2. 整數座標條件：中點 $M$ 為整數座標點（$M \in \mathbb{Z}^3$）的充要條件為：$x_1 + x_2$、$y_1 + y_2$ 與 $z_1 + z_2$ 皆為偶數。
3. 同餘與奇偶性：兩整數之和為偶數，若且唯若這兩數具有相同的奇偶性，即：
   $a + b \equiv 0 \pmod 2 \iff a \equiv b \pmod 2$
4. 鴿籠原理：若將 $n$ 個物品放進 $k$ 個盒子中，且 $n > k$，則必定至少有一個盒子包含 2 個或 2 個以上的物品。

---

解題方法

步驟一：分析中點為整數點的充要條件

設空間中任意兩整數點 $P_i = (x_i, y_i, z_i)$ 與 $P_j = (x_j, y_j, z_j)$（其中 $x_i, y_i, z_i \in \mathbb{Z}$）。
其連線中點座標為：
$M_{ij} = \left(\frac{x_i + x_j}{2}, \frac{y_i + y_j}{2}, \frac{z_i + z_j}{2}\right)$
要使 $M_{ij}$ 為整數座標點，其三個分量必須皆為整數，即：
$x_i + x_j \equiv 0 \pmod 2, \quad y_i + y_j \equiv 0 \pmod 2, \quad z_i + z_j \equiv 0 \pmod 2$
依據奇偶性同餘性質，上式可等價轉化為：
$x_i \equiv x_j \pmod 2, \quad y_i \equiv y_j \pmod 2, \quad z_i \equiv z_j \pmod 2$
亦即，$P_i$ 與 $P_j$ 的對應座標分量必須擁有完全相同的奇偶性。

設各面額紙鈔張數依序為 $a,b,c,d\ge 0$，則

$200a+500b+1000c+2000d=8000.$

除以 $100$：

$2a+5b+10c+20d=80.$

等式右側及其餘各項皆為偶數，故 $b$ 必為偶數。令 $b=2k$，得

$a+5k+5c+10d=40,$

因此只需計算

$k+c+2d\le 8$

核心觀念

1. 有限狀態機（Finite State Machine, FSM）與米利機（Mealy Machine）：
   有限狀態機為由有限個狀態、輸入符號、轉移函數及輸出構成的計算模型。本題輸出序列與輸入序列長度相同，且在接收每一個輸入字元時即刻產生相應的輸出（$Y$ 或 $N$），故採用**米利機（Mealy Machine）**模型最為直接且狀態數最少。
   米利機的數學定義為五元組 $M = (Q, \Sigma, \Gamma, \delta, \lambda)$：

   • $Q$：有限狀態集合。
   • $\Sigma = \{0, 1\}$：輸入字母集。
   • $\Gamma = \{N, Y\}$：輸出字母集。
   • $\delta: Q \times \Sigma \to Q$：狀態轉移函數。
   • $\lambda: Q \times \Sigma \to \Gamma$：輸出函數。

2. 序列模式辨識與重疊處理（Overlapping Pattern Recognition）：
   辨識目標字串 $1010$ 時，狀態設計的核心為記錄「目前已匹配到目標字串的最長字首（Prefix）長度」。若遇到不匹配的字元，需根據已輸入字串的末尾部分，尋找能與目標字串字首匹配的最長字尾（Suffix），進行正確的狀態回退（此概念同 KMP 演算法）。當成功匹配 $1010$ 時，由於結尾的 $10$ 同時可作為下一次匹配 $1010$ 的前兩字元（如輸入 $101010$ 會產生兩次 $Y$），故狀態需回退至「已匹配 $10$」的狀態，而非回到初始狀態。

---

解題方法

1. 狀態定義
根據目標字串 $1010$ 的長度（$4$），定義 $4$ 個狀態，分別代表目前已連續匹配到的字首長度：

• $S_0$：初始狀態，表示目前匹配長度為 $0$（無任何有效字首）。
• $S_1$：表示目前已匹配字首為 $1$（長度為 $1$）。
• $S_2$：表示目前已匹配字首為 $10$（長度為 $2$）。
• $S_3$：表示目前已匹配字首為 $101$（長度為 $3$）。

2. 狀態轉移與輸出推導

• 在 $S_0$ 狀態（匹配 ""）：

  • 輸入 $1$：成功推進至字首 $1$，轉移至 $S_1$，輸出 $N$。
  • 輸入 $0$：無法匹配，維持在 $S_0$，輸出 $N$。

• 在 $S_1$ 狀態（匹配 "1"）：

  • 輸入 $1$：字串變為 $11$，末尾最長可匹配字首仍為 $1$，故維持在 $S_1$，輸出 $N$。
  • 輸入 $0$：成功推進至字首 $10$，轉移至 $S_2$，輸出 $N$。

• 在 $S_2$ 狀態（匹配 "10"）：

  • 輸入 $1$：成功推進至字首 $101$，轉移至 $S_3$，輸出 $N$。
  • 輸入 $0$：字串變為 $100$，無任何有效字首匹配，回退至 $S_0$，輸出 $N$。

• 在 $S_3$ 狀態（匹配 "101"）：

  • 輸入 $1$：字串變為 $1011$，末尾最長可匹配字首為 $1$，回退至 $S_1$，輸出 $N$。
  • 輸入 $0$：字串變為 $1010$，成功完成匹配！輸出 $Y$。由於末尾 $10$ 為下一輪匹配的字首，故轉移至 $S_2$。

3. 狀態轉移表（State Transition Table）

當前狀態 $q \in Q$	輸入 $0$（次態 / 輸出）	輸入 $1$（次態 / 輸出）
$S_0$（初始）	$S_0 / N$	$S_1 / N$
$S_1$	$S_2 / N$	$S_1 / N$
$S_2$	$S_0 / N$	$S_3 / N$
$S_3$	$S_2 / Y$	$S_1 / N$

---

狀態與轉移分析

由於本題為設計與圖示題，下表對各狀態在不同輸入下的轉移邏輯進行逐一檢驗與說明：

• $S_0$ 轉移分析：

  • 輸入 $0$ $\to$ 歷史序列末尾為 $0$，無法形成 $1010$ 的任何前綴 $\to$ 保持 $S_0 / N$。
  • 輸入 $1$ $\to$ 歷史序列末尾為 $1$，匹配 $1010$ 的第一個字元 $\to$ 轉移至 $S_1 / N$。

• $S_1$ 轉移分析：

  • 輸入 $0$ $\to$ 歷史序列末尾為 $10$，匹配前兩個字元 $\to$ 轉移至 $S_2 / N$。
  • 輸入 $1$ $\to$ 歷史序列末尾為 $11$，最後一個 $1$ 可作為新匹配的開始 $\to$ 保持 $S_1 / N$。

• $S_2$ 轉移分析：

  • 輸入 $0$ $\to$ 歷史序列末尾為 $100$，中斷匹配且無可利用後綴 $\to$ 回退至 $S_0 / N$。
  • 輸入 $1$ $\to$ 歷史序列末尾為 $101$，匹配前三個字元 $\to$ 轉移至 $S_3 / N$。

• $S_3$ 轉移分析：

  • 輸入 $0$ $\to$ 歷史序列末尾為 $1010$，達到完整匹配，輸出 $Y$；保留末尾 $10$ 作為下一次匹配前綴 $\to$ 轉移至 $S_2 / Y$。
  • 輸入 $1$ $\to$ 歷史序列末尾為 $1011$，最後一個 $1$ 可作為新匹配的開始 $\to$ 回退至 $S_1 / N$。

範例追蹤驗證（題目提示：1110101001）：

核心觀念

本題考查有限狀態機（Finite State Machine, FSM）與字串樣式辨識。

將輸入視為只含 0、1 的位元字串，目標是判斷其中是否出現連續子字串 1010。有限狀態機的每個狀態，代表目前已經比對成功的樣式前綴長度：

• $q_0$：尚未比對到有效前綴
• $q_1$：目前結尾為 1
• $q_2$：目前結尾為 10
• $q_3$：目前結尾為 101
• $q_4$：已經辨識出 1010，為接受狀態

一旦進入 $q_4$，即代表輸入中曾出現 1010，後續字元不影響辨識結果，因此維持在 $q_4$。

解題方法

依照目前已匹配的字串，建立狀態轉移：

目前狀態	讀入 0	讀入 1	意義
$q_0$	$q_0$	$q_1$	尚未開始或無有效前綴
$q_1$	$q_2$	$q_1$	已匹配 1
$q_2$	$q_0$	$q_3$	已匹配 10
$q_3$	$q_4$	$q_1$	已匹配 101
$q_4$	$q_4$	$q_4$	已找到 1010

關鍵轉移說明如下：

1. $q_0$ 讀入 1 後，開始匹配樣式，因此進入 $q_1$。
2. $q_1$ 讀入 0 後得到 10，進入 $q_2$。
3. $q_2$ 讀入 1 後得到 101，進入 $q_3$。
4. $q_3$ 讀入 0 後得到 1010，進入接受狀態 $q_4$。
5. $q_1$ 讀入 1 時，最新結尾仍可視為一個新的 1，因此留在 $q_1$。
6. $q_3$ 讀入 1 時，字串結尾為 1011，其中最後一個字元 1 可作為新比對起點，因此回到 $q_1$。

C++ 程式