113 年 國立中山大學電機工程學系碩士班丙組《離散數學》

核心觀念

1. 等差級數求和公式：自然數 $1$ 到 $n$ 之和 $x = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$。
2. 質因數分解與數論分解：將模數分解為互質因數之乘積 $x = m_1 \cdot m_2$。
3. 威爾遜定理（Wilson's Theorem）：若 $p$ 為質數，則 $(p-1)! \equiv -1 \pmod p$。
4. 模反元素（Modular Inverse）：若 $\gcd(a, m) = 1$，則存在整數 $a^{-1}$ 使得 $a \cdot a^{-1} \equiv 1 \pmod m$。
5. 中國剩餘定理（Chinese Remainder Theorem, CRT）：若 $\gcd(m_1, m_2) = 1$，則聯立同餘方程組 $\begin{cases} N \equiv a_1 \pmod{m_1} \\ N \equiv a_2 \pmod{m_2} \end{cases}$ 在模 $m_1 m_2$ 下有唯一解。

---

解題方法

步驟一：求出模數 $x$ 並分解模數

依題意，$x$ 為自然數 $1$ 到 $100$ 之和：
$x = \sum_{k=1}^{100} k = \frac{100 \times 101}{2} = 50 \times 101 = 5050$
其中 $101$ 為質數，且 $\gcd(50, 101) = 1$。
令 $N = \frac{100!}{4!}$，求 $N \pmod{5050}$ 可化為求 $N \pmod{50}$ 與 $N \pmod{101}$ 的聯立方程組。

步驟二：計算 $N \pmod{50}$

將 $N$ 展開：
$N = \frac{100!}{4!} = 5 \times 6 \times 7 \times \dots \times 100$
分子乘積中包含 $50$ 作為其中一個乘項，且分母 $4! = 24$ 的質因數僅有 $2$ 與 $3$，不會消耗質因數 $5$。
分析 $N$ 中質因數 $5$ 的次方數：
$100!$ 中質因數 $5$ 的次數為 $\lfloor \frac{100}{5} \rfloor + \lfloor \frac{100}{25} \rfloor = 20 + 4 = 24$。
因此 $N$ 含有因子 $5^{24}$，顯然可被 $50 = 2 \times 5^2$ 整除：
$N \equiv 0 \pmod{50}$

步驟三：計算 $N \pmod{101}$

由於 $101$ 為質數，套用威爾遜定理：
$100! \equiv -1 \pmod{101}$

又由 $N = \frac{100!}{4!} \implies 4! \cdot N \equiv 100! \pmod{101}$，其中 $4! = 24$，得：
$24 N \equiv -1 \pmod{101}$

核心觀念

1. 簡單圖（Simple Graph）與完全圖（Complete Graph）：
   簡單圖指無自環（Self-loop）且無重邊（Parallel Edge）的無向圖。若一個包含 $n$ 個頂點的簡單圖為完全圖 $K_n$，其邊數達到極大值，公式為：
   $\binom{n}{2} = \frac{n(n-1)}{2}$

2. 連通部分（Connected Component）：
   極大連通子圖稱為連通部分。若圖 $G$ 恰有 $M$ 個連通部分 $C_1, C_2, \dots, C_M$，且各部分的頂點數分別為 $n_1, n_2, \dots, n_M$，則必須滿足：
   $\sum_{i=1}^M n_i = N \quad \text{且} \quad n_i \ge 1 \quad (\forall i = 1, 2, \dots, M)$

3. 邊數最大化之極值條件（Convexity Criterion）：
   邊數函數 $f(n) = \frac{n(n-1)}{2}$ 為嚴格凸函數（Convex Function）。將固定數量的頂點 $N$ 分配給 $M$ 個組別時，為使總邊數 $\sum_{i=1}^M \binom{n_i}{2}$ 最大化，分配策略必須極端化：讓 $M-1$ 個連通部分盡可能包含最少的頂點（即各 1 個孤立頂點），而將其餘頂點全部集中在同一個連通部分中，形成完全圖。

---

解題方法

1. 建立數學模型：
   設 $G$ 的 $M$ 個連通部分之頂點數分別為 $n_1, n_2, \dots, n_M$。因為 $G$ 為簡單圖，其總邊數 $E$ 之上限為各連通部分最大可能邊數之和：
   $E \le \sum_{i=1}^M \binom{n_i}{2} = \sum_{i=1}^M \frac{n_i(n_i-1)}{2}$

2. 證明極端分配產生最大邊數：
   任意取兩個連通部分之頂點數 $n_j, n_k$，假設 $n_j \ge n_k \ge 2$。若自 $n_k$ 移出 1 個頂點給 $n_j$，新構成的頂點數分別為 $n_j + 1$ 與 $n_k - 1$。比較轉移前後的邊數差：
   $\left[ \binom{n_j + 1}{2} + \binom{n_k - 1}{2} \right] - \left[ \binom{n_j}{2} + \binom{n_k}{2} \right] = n_j - (n_k - 1) = n_j - n_k + 1$
   因為 $n_j \ge n_k$，故 $n_j - n_k + 1 \ge 1 > 0$。此式證明：將頂點集中度提高，總邊數必然嚴格遞增。

3. 確定極值頂點數分配：
   為取得絕對最大邊數，必須將 $M-1$ 個連通部分各分配 $1$ 個頂點（即 $n_1 = n_2 = \dots = n_{M-1} = 1$），此時這 $M-1$ 個部分各自的邊數為 $\binom{1}{2} = 0$。
   剩餘最後一個連通部分的頂點數為：
   $n_M = N - (M - 1) = N - M + 1$

4. 計算最大邊數並展開多項式：
   最大邊數 $E_{\max}$ 即為 $K_{N-M+1}$ 的邊數：
   $E_{\max} = \binom{N - M + 1}{2} = \frac{(N - M + 1)(N - M)}{2}$
   展開分子乘積：

核心觀念

1. 白努利試驗 (Bernoulli Trial) 與二項分布 (Binomial Distribution)
   投擲正常硬幣（公正硬幣）每回合出現正面的機率為 $p = \frac{1}{2}$，反面的機率為 $q = 1 - p = \frac{1}{2}$。連續投擲 $n = 6$ 次獨立試驗，出現正面的總次數隨機變數服從二項分布 $X \sim \text{B}\left(6, \frac{1}{2}\right)$。

2. 二項機率公式
   在 $n$ 次獨立試驗中，成功（正面）恰好出現 $k$ 次的機率為：
   $P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$
   當 $p = \frac{1}{2}$ 時，公式可簡化為：
   $P(X = k) = \frac{\binom{6}{k}}{2^6} = \frac{\binom{6}{k}}{64}$

3. 互斥事件加法原理
   題目要求「出現正面次數至少三次」，代表 $X \ge 3$，即 $X$ 可以為 $3, 4, 5, 6$。各次數事件彼此互斥，其機率和為：
   $P(X \ge 3) = \sum_{k=3}^{6} P(X = k) = P(X=3) + P(X=4) + P(X=5) + P(X=6)$

---

解題方法

【方法一：正面直接累加法】

1. 計算樣本空間總數
   投擲硬幣 $6$ 次，每次皆有正面或反面 $2$ 種可能，總排列數為：
   $|\Omega| = 2^6 = 64$

2. 計算各正面次數的組合數與機率

   • 恰好 3 次正面：
     $\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20 \implies P(X = 3) = \frac{20}{64}$
   • 恰好 4 次正面：
     $\binom{6}{4} = \binom{6}{2} = \frac{6 \times 5}{2 \times 1} = 15 \implies P(X = 4) = \frac{15}{64}$
   • 恰好 5 次正面：
     $\binom{6}{5} = \binom{6}{1} = 6 \implies P(X = 5) = \frac{6}{64}$
   • 恰好 6 次正面：
     $\binom{6}{6} = 1 \implies P(X = 6) = \frac{1}{64}$

3. 加法求總和與最簡分數化簡
   $P(X \ge 3) = \frac{20 + 15 + 6 + 1}{64} = \frac{42}{64} = \frac{21}{32}$

---

【方法二：取餘事件法（補集法）】

核心觀念

• 取捨原理（Inclusion-Exclusion Principle, IEP / 排容原理）：求「相鄰兩房皆不同色」的非相鄰排列問題，正面直接討論分類極為複雜，應改用全集扣除「至少有一對同色相鄰」的集合大小。設 $A_R, A_G, A_B, A_Y$ 分別表示紅、綠、藍、黃門牌相鄰的事件，所求即為未發生任何相鄰事件的排列數 $|\bar{A}_R \cap \bar{A}_G \cap \bar{A}_B \cap \bar{A}_Y|$。
• 多重集排列（Multiset Permutation）：含有重複元素的物件進行全排列，公式為 $\frac{n!}{n_1! n_2! \cdots n_k!}$。
• 綁定法（Grouping Method）：將要求必須相鄰的相同顏色門牌綁成一個整體（視為 1 個元素）參與排列。

---

解題方法

步驟一：計算全集排列數 $N$
八間房間分配 8 塊門牌（紅 2、綠 2、藍 2、黃 2），無任何限制下的不相異物全排列數 $N$ 為：
$N = \frac{8!}{2! 2! 2! 2!} = \frac{40320}{16} = 2520$

步驟二：建立排容原理事件
設 $A_R, A_G, A_B, A_Y$ 分別表示紅、綠、藍、黃色門牌相鄰的事件。
根據取捨原理，滿足相鄰兩房皆不同色的排列總數為：
$N(\bar{A}_R \bar{A}_G \bar{A}_B \bar{A}_Y) = N - S_1 + S_2 - S_3 + S_4$

步驟三：分階計算各交集項 $S_k$

1. 計算 $S_1$（至少 1 種顏色相鄰）：
   從 4 種顏色中選 1 種將其 2 塊門牌綁成 1 個整體。此時共有 7 個元素參與排列（1 個綁定整體 + 3 對單獨門牌）：
   $S_1 = \binom{4}{1} \times \frac{7!}{1! 2! 2! 2!} = 4 \times \frac{5040}{8} = 4 \times 630 = 2520$

2. 計算 $S_2$（至少 2 種顏色相鄰）：
   從 4 種顏色中選 2 種分別綁成整體。此時共有 6 個元素參與排列（2 個綁定整體 + 2 對單獨門牌）：

核心觀念

本題考驗離散數學與演算法分析中**遞迴關係式（Recurrence Relation）**的漸近複雜度分析（Asymptotic Analysis）。

主要涵蓋以下核心知識點：

1. 代換展開法（Substitution / Expansion Method）與遞迴樹法（Recursion Tree Method）：將遞迴式逐層展開，分析每一層的工作量（Work），並加總所有層級的代價。
2. 主定理推廣型（Extended Master Theorem）：
   對於遞迴式 $F(n) = a F(n/b) + f(n)$，其中 $a \ge 1, b > 1$：
   • 計算臨界項 $n^{\log_b a}$。本題 $a = 2, b = 2 \implies n^{\log_2 2} = n^1 = n$。
   • 當 $f(n) = \Theta(n^{\log_b a} \log^k n)$（其中 $k \ge 0$）時，遞迴解為 $F(n) = \Theta(n^{\log_b a} \log^{k+1} n)$。
3. $\Theta$-符號（Tight Bound）之定義與運算：求出最高次方項並忽略常數係數與低階項。

---

解題方法

本題採用代換展開法（Expansion Method）進行精確推導，並利用主定理推廣型進行驗證。

1. 代換展開過程

設 $n = 2^k$，即 $k = \log_2 n$。原遞迴式為：
$F(n) = 2F\left(\frac{n}{2}\right) + n \log_2 n$

將 $F(n/2)$ 依據原遞迴定義式進行代換：
$F\left(\frac{n}{2}\right) = 2F\left(\frac{n}{4}\right) + \frac{n}{2} \log_2 \left(\frac{n}{2}\right)$

代回原式可得第 2 層展開：
$F(n) = 2 \left[ 2F\left(\frac{n}{4}\right) + \frac{n}{2} \log_2 \left(\frac{n}{2}\right) \right] + n \log_2 n$
$F(n) = 4F\left(\frac{n}{4}\right) + n \log_2 \left(\frac{n}{2}\right) + n \log_2 n$

同理，繼續展開至第 3 層：
$F(n) = 8F\left(\frac{n}{8}\right) + n \log_2 \left(\frac{n}{4}\right) + n \log_2 \left(\frac{n}{2}\right) + n \log_2 n$

推廣至第 $i$ 次展開之一般項：
$F(n) = 2^i F\left(\frac{n}{2^i}\right) + n \sum_{j=0}^{i-1} \log_2 \left(\frac{n}{2^j}\right)$

當展開至邊界條件 $i = k = \log_2 n$ 時（此時 $\frac{n}{2^k} = 1$）：
$F(n) = 2^k F(1) + n \sum_{j=0}^{k-1} \log_2 \left(\frac{n}{2^j}\right)$

2. 代數簡化與級數求和

利用對數性質 $\log_2 (n / 2^j) = \log_2 n - \log_2 (2^j) = k - j$：