109 年 國立中山大學資訊工程學系碩士班甲組《離散數學》

設第 $i$ 個容器中的球數為 $x_i$，則

$$x_1+x_2+x_3+x_4+x_5=10.$$

(a) 每個容器至少一球，即 $x_i\ge 1$。由隔板法，方法數為

$$\binom{10-1}{5-1}=\binom94=126.$$

【答案】$126$ 種。

核心觀念

1. 奇數的代數定義（Definition of Odd Integers）：
   若 $n \in \mathbb{Z}^+$ 為奇數，則存在非負整數 $k \in \mathbb{Z}_{\ge 0}$，使得 $n = 2k + 1$。
2. 整除性定義（Divisibility）：
   設 $d, n \in \mathbb{Z}$，若存在整數 $q$ 使得 $n = dq$，則稱 $d$ 整除 $n$，記作 $d \mid n$；若不存在此整數 $q$，則記作 $d \nmid n$。
3. 除法原理與同餘性質（Division Algorithm & Modular Arithmetic）：
   對任意奇數 $n$，其模 4 之結果必為 $1$ 或 $3$（即 $n \equiv 1$ 或 $3 \pmod 4$），故其平方模 4 之餘數必為 1（即 $n^2 \equiv 1 \pmod 4$）。

---

解題方法

本題為數論經典證明題。解法可採直接代數推導法（適合標準作答）或同餘算術法（適合速解驗算）。

解法一：直接代數推導法（標準考場作答）

1. 設定變數：
   因為 $a, b \in \mathbb{Z}^+$ 皆為奇數，故可分別設為：
   $a = 2k + 1 \quad (k \in \mathbb{Z}_{\ge 0})$
   $b = 2m + 1 \quad (m \in \mathbb{Z}_{\ge 0})$
   （注意：$a$ 與 $b$ 不一定相等，變數必須獨立設為 $k$ 與 $m$。）

2. 展開平方和 $a^2 + b^2$：
   $a^2 + b^2 = (2k + 1)^2 + (2m + 1)^2$
   $a^2 + b^2 = (4k^2 + 4k + 1) + (4m^2 + 4m + 1)$
   $a^2 + b^2 = 4k^2 + 4k + 4m^2 + 4m + 2$

3. 第一部分：證明 $2 \mid (a^2 + b^2)$：
   將式子提出公因數 $2$：
   $a^2 + b^2 = 2 \left( 2k^2 + 2k + 2m^2 + 2m + 1 \right)$
   因為 $k, m \in \mathbb{Z}_{\ge 0}$，所以 $q_1 = 2k^2 + 2k + 2m^2 + 2m + 1$ 必為整數。
   由整除定義，得證 $2 \mid (a^2 + b^2)$。

4. 第二部分：證明 $4 \nmid (a^2 + b^2)$：
   將式子改寫為被 $4$ 除的形式：
   $a^2 + b^2 = 4 \left( k^2 + k + m^2 + m \right) + 2$
   令 $q_2 = k^2 + k + m^2 + m$，因為 $k, m \in \mathbb{Z}_{\ge 0}$，故 $q_2 \in \mathbb{Z}$。
   因此 $a^2 + b^2 = 4q_2 + 2$。

核心觀念

1. 封閉二元運算（Closed Binary Operation）：
   定義在集合 $A$ 上的封閉二元運算，本質上為一個從直積 $A \times A$ 對應至 $A$ 的函數 $f: A \times A \to A$。若集合有限且 $|A| = n$，則定義域 $A \times A$ 的元素個數為 $|A \times A| = n^2$，對應域 $A$ 的元素個數為 $|A| = n$。
2. 函數計數原理（Function Counting Principle）：
   設有限集合 $X$ 與 $Y$ 的基數分別為 $|X| = m$ 與 $|Y| = n$，則從 $X$ 到 $Y$ 的所有可能函數總數為 $n^m$。
3. 交換律（Commutative Property）：
   二元運算 $f$ 若滿足交換律，代表對任意 $x, y \in A$，均有 $f(x, y) = f(y, x)$。若將二元運算表達成 $n \times n$ 的運算表（Cayley Table），交換律意味著該矩陣關於主對角線呈對稱（Symmetric Matrix）。

---

解題方法

(a) 封閉二元運算函數總數

1. 定義域 $A \times A$ 共有 $|A| \times |A| = 7 \times 7 = 49$ 個有序對 $(x, y)$。
2. 對於定義域中的每一個有序對 $(x, y)$，其經由函數 $f$ 映射後的結果 $f(x, y)$ 都可以獨立且自由地從對應域 $A$ 中選擇一個元素，共有 $|A| = 7$ 種選擇。
3. 根據乘法原理，所有可能的封閉二元運算函數總數為：
   $|A|^{|A \times A|} = |A|^{|A|^2} = 7^{49}$

(b) 具交換律之封閉二元運算總數

1. 考慮二元運算 $f$ 在 $A \times A$ 上的運算表（大小為 $7 \times 7$ 的方陣）。
2. 當運算滿足交換律 $f(x, y) = f(y, x)$ 時，運算表中位於對稱位置的元素 $(x, y)$ 與 $(y, x)$ 其值必須完全相同。
3. 因此，只需獨立決定主對角線上的元素以及主對角線右上方的元素：

核心觀念

本題考驗離散數學中的**組合計數（Combinational Counting）與鴿籠原理（Pigeonhole Principle）**之應用。

1. 乘法法則（Rule of Product）：若完成某件事需經兩個獨立步驟，第一步驟有 $m$ 種可能，第二步驟有 $n$ 種可能，則總組合數為 $m \times n$ 種。
2. 鴿籠原理（Pigeonhole Principle）：若將 $n$ 個物件（鴿子）放入 $k$ 個容器（鴿籠）中，且 $n > k$，則至少有一個容器包含至少 $2$ 個物件。要「保證（Guarantee）」發生重複，物件數量 $n$ 最少必須達到 $k + 1$。

---

解題方法

步驟一：計算「名與姓首字母組合」的總可能性（鴿籠數 $k$）

英文字母共有 $26$ 個（A 至 Z）。

• 名字（First Name）的首字母有 $26$ 種可能。
• 姓氏（Last Name）的首字母有 $26$ 種可能。

根據乘法法則，名與姓首字母組成的有序對組合 $(F, L)$ 總數量為：
$k = 26 \times 26 = 676$
這 $676$ 種組合即為本題對應的「鴿籠數」。

步驟二：套用鴿籠原理求出保證重複的最小人數（鴿子數 $n$）

目標為「保證至少有兩個人擁有相同的名字與姓氏首字母」。

• 考慮最壞情況（Worst-Case Scenario）：前 $676$ 位就座的人，每個人的首字母組合皆不相同（恰好填滿所有 $676$ 種組合，每種組合各 $1$ 人），此時仍未能保證有兩人重複。
• 當第 $677$ 個人就座時，不論其首字母組合為何，必定會落在已被佔用的 $676$ 種組合之一。

核心觀念

本題屬於離散數學中**生成函數（Generating Functions）與排容原理（Inclusion-Exclusion Principle）**在「受限非負整數解（Restricted Integer Solutions）」問題上的典型應用。

1. 單位轉換（Unit Conversion）：
   題目規定信封是以「每包 25 封（in package of 25）」為發放單位，因此必須先將信封總數以及各群組的配額上下限統一轉換為「包數（packages）」進行計算：

   • 總包數 $N = \frac{3600}{25} = 144$ 包。
   • 每組下限：至少 150 封 $\implies \frac{150}{25} = 6$ 包。
   • 每組上限：至多 1000 封 $\implies \frac{1000}{25} = 40$ 包。

2. 重複組合與不定方程式：
   設 5 個學生群組獲得的信封包數分別為 $x_1, x_2, x_3, x_4, x_5$，則問題轉化為求解不定方程式：
   $x_1 + x_2 + x_3 + x_4 + x_5 = 144, \quad \text{其中 } 6 \le x_i \le 40 \ \forall i \in \{1, 2, 3, 4, 5\}$

3. 變數平移（Variable Shift）：
   令 $y_i = x_i - 6$，代表扣除基本配額後額外獲得的包數，則 $0 \le y_i \le 34$。方程式簡化為標準非負整數解問題：
   $y_1 + y_2 + y_3 + y_4 + y_5 = 114 \quad (144 - 5 \times 6 = 114)$

4. 排容原理（Inclusion-Exclusion Principle）：
   求受限於 $0 \le y_i \le 34$ 的整數解個數時，先計算無上限限制（$y_i \ge 0$）的重複組合數 $H(5, 114)$，再利用排容原理扣除至少有一個變數違反上限（即 $y_i \ge 35$）的情形。

---

解題方法

步驟一：建立簡化後的不定方程式

設 5 個群組分配到的信封包數分別為 $x_1, x_2, x_3, x_4, x_5$。
已知 $x_1 + x_2 + x_3 + x_4 + x_5 = 144$ 且 $6 \le x_i \le 40$。
做變數代換 $y_i = x_i - 6$，得：
$y_1 + y_2 + y_3 + y_4 + y_5 = 114, \quad 0 \le y_i \le 34 \ \forall i \in \{1, 2, 3, 4, 5\}$

步驟二：應用排容原理展開

設全集 $U$ 為方程式 $y_1 + y_2 + y_3 + y_4 + y_5 = 114$ 的非負整數解集合。
設條件 $A_i$ 為「$y_i \ge 35$」（即第 $i$ 個群組違反上限）。我們求的是未違反任何條件的解個數 $N(\overline{A_1}\overline{A_2}\overline{A_3}\overline{A_4}\overline{A_5}) = S_0 - S_1 + S_2 - S_3 + S_4 - S_5$。

1. 無上限限制解總數 $S_0$：
   $S_0 = H(5, 114) = \binom{5 + 114 - 1}{114} = \binom{118}{4} = 7,673,835$

2. 至少 1 個變數違反上限（$y_i \ge 35$）的情形 $S_1$：
   選擇 1 個違規變數有 $\binom{5}{1}$ 種方式。令 $z_i = y_i - 35 \ge 0$，方程式變為 $z_i + \sum_{j \neq i} y_j = 114 - 35 = 79$。
   $S_1 = \binom{5}{1} H(5, 79) = 5 \times \binom{5 + 79 - 1}{79} = 5 \times \binom{83}{4} = 5 \times 1,837,620 = 9,188,100$

核心觀念

本題考查**整數拆分（Integer Partition）與生成函數（Generating Function）**的建構原理。

1. 整數拆分生成函數基本原理：
   若非負整數 $n$ 被拆分成若干個正整數加數（summand），且加數 $k$ 可選擇的出現次數集合為 $S_k \subseteq \{0, 1, 2, \dots\}$，則該加數 $k$ 所對應的生成函數因子為：
   $f_k(x) = \sum_{m \in S_k} x^{k \cdot m}$
   將所有允許的加數 $k$ 之生成函數因子相乘，即得整體拆分數的生成函數：
   $P(x) = \prod_{k} f_k(x)$

2. 無窮等比級數求和公式：
   當 $|x| < 1$ 時，無窮等比級數可收斂表示為：
   $\sum_{j=0}^{\infty} y^j = \frac{1}{1 - y}$

---

解題方法

(a) 每個加數必須出現偶數次（each summand must appear an even number of times）

1. 確定加數範圍與出現次數：
   • 加數可為任意正整數 $k \in \{1, 2, 3, \dots\}$。
   • 對於固定的加數 $k$，其出現次數限制為偶數，即 $m \in \{0, 2, 4, 6, \dots\}$。
2. 建構各加數的生成函數因子：
   加數 $k$ 所貢獻的因子為：
   $f_k(x) = 1 + x^{2k} + x^{4k} + x^{6k} + \dots = \sum_{j=0}^{\infty} (x^{2k})^j$
   利用無窮等比級數求和公式化簡得：
   $f_k(x) = \frac{1}{1 - x^{2k}}$
3. 求取整體生成函數：
   將所有正整數 $k = 1, 2, 3, \dots$ 的因子相乘：
   $P_a(x) = \prod_{k=1}^{\infty} f_k(x) = \prod_{k=1}^{\infty} \frac{1}{1 - x^{2k}} = \frac{1}{(1-x^2)(1-x^4)(1-x^6)\cdots}$

(b) 每個加數必須為偶數（each summand must be even）

1. 確定加數範圍與出現次數：
   • 加數僅能取正偶數，即 $2k \in \{2, 4, 6, 8, \dots\}$（其中 $k \in \{1, 2, 3, \dots\}$）。
   • 對於每個偶數加數 $2k$，其出現次數無限制，可為任意非負整數 $m \in \{0, 1, 2, 3, \dots\}$。
2. 建構各加數的生成函數因子：
   偶數加數 $2k$ 所貢獻的因子為：
   $g_k(x) = 1 + x^{2k \cdot 1} + x^{2k \cdot 2} + x^{2k \cdot 3} + \dots = \sum_{m=0}^{\infty} (x^{2k})^m$

由遞迴關係 $a_{n+1}=da_n$，得

$a_5=d^2a_3.$

因此

$$d^2=\frac{a_5}{a_3} =\frac{1628}{6336}\cdot\frac{77}{156} =\frac{2849}{22464},$$

故

$d=\pm\sqrt{\frac{2849}{22464}}.$

核心觀念

1. 完全雙分圖（Complete Bipartite Graph）之定義：
   若圖 $G = (V, E)$ 的頂點集 $V$ 可分割為兩個互斥的非空子集 $V_1$ 與 $V_2$（即 $V = V_1 \cup V_2$ 且 $V_1 \cap V_2 = \emptyset$），且滿足：

   • $V_1$ 內部的任意兩頂點間均無邊相連；$V_2$ 內部的任意兩頂點間亦均無邊相連（兩者皆為獨立集）。
   • $V_1$ 中的每一個頂點與 $V_2$ 中的每一個頂點之間，恰好都有一條邊相連。
     則稱 $G$ 為完全雙分圖，記作 $K_{m,n}$，其中 $m = |V_1|$ 且 $n = |V_2|$。

2. 基本計數原理：

   • 頂點總數：兩獨立頂點集的基數之和，即 $|V| = |V_1| + |V_2| = m + n$。
   • 邊總數：由乘法原理（Rule of Product），從 $V_1$ 任取一頂點與從 $V_2$ 任取一頂點可唯一確定一條邊，故總邊數為 $|E| = |V_1| \times |V_2| = m \cdot n$。

3. 握手定理（Handshaking Lemma）：
   對任意無向圖 $G=(V,E)$，所有頂點的度數（degree）總和等於邊數的兩倍，即 $\sum_{v \in V} \deg(v) = 2|E|$。

---

解題方法

(a) 推導 $K_{m,n}$ 的頂點數與邊數

1. 頂點數（Number of Vertices）計算：
   設完全雙分圖 $K_{m,n} = (V, E)$ 的頂點集分割為 $V_1$ 與 $V_2$，滿足 $|V_1| = m$ 且 $|V_2| = n$。
   因為 $V_1 \cap V_2 = \emptyset$，依據集合聯集的基數公式：
   $|V| = |V_1 \cup V_2| = |V_1| + |V_2| = m + n$
   故 $K_{m,n}$ 共有 $m + n$ 個頂點。

2. 邊數（Number of Edges）計算：

   • 推導法一（乘法原理）：
     $K_{m,n}$ 的每一條邊恰由 $V_1$ 中的一個頂點與 $V_2$ 中的一個頂點連接而成。
     選擇 $V_1$ 端點有 $m$ 種方法，選擇 $V_2$ 端點有 $n$ 種方法。
     根據乘法原理，邊的總數為：
     $|E| = m \times n = mn$
   • 推導法二（握手定理驗證）：
     在 $K_{m,n}$ 中，$V_1$ 中的每個頂點皆連接至 $V_2$ 的 $n$ 個頂點，故度數皆為 $n$；$V_2$ 中的每個頂點皆連接至 $V_1$ 的 $m$ 個頂點，故度數皆為 $m$。
     頂點度數總和為：

核心觀念

本題為數論（Number Theory）中關於**同餘（Congruence）與最大公因數（Greatest Common Divisor, $\gcd$）**基本性質的證明題。考查重點在於能否精準運用定義並進行嚴謹的邏輯推導。

1. 同餘的定義（Definition of Congruence）：
   對於 $a, b, n \in \mathbb{Z}^+$ 且 $n > 1$，若 $a \equiv b \pmod n$，表示 $n$ 整除 $(a - b)$，記作 $n \mid (a - b)$。
   依定義，存在一整數 $k \in \mathbb{Z}$，使得：
   $a - b = k n \quad \implies \quad a = b + k n$

2. 最大公因數的性質（Properties of $\gcd$）：

   • 公因數集合相同：若兩組正整數對的「公因數集合」完全相同，則其集合內的最大元素（即最大公因數）必相等。
   • 整除的線性組合性質：若 $d \mid x$ 且 $d \mid y$，則對任意整數 $s, t \in \mathbb{Z}$，皆有 $d \mid (s x + t y)$。
   • 相互整除：若 $d_1, d_2 \in \mathbb{Z}^+$ 滿足 $d_1 \mid d_2$ 且 $d_2 \mid d_1$，則 $d_1 = d_2$。

---

解題方法

本題可採用「公因數集合相等法」或「雙向相互整除法」進行證明。以下提供最為直觀且無懈可擊的兩種標準推導過程：

方法一：公因數集合相等法（推薦，邏輯最清晰）

步驟一：定義公因數集合
定義 $S_1$ 為 $a$ 與 $n$ 的所有正公因數集合，$S_2$ 為 $b$ 與 $n$ 的所有正公因數集合：
$S_1 = \{ d \in \mathbb{Z}^+ : d \mid a \text{ 且 } d \mid n \}$
$S_2 = \{ d \in \mathbb{Z}^+ : d \mid b \text{ 且 } d \mid n \}$

步驟二：證明 $S_1 \subseteq S_2$
已知 $a \equiv b \pmod n$，故存在整數 $k \in \mathbb{Z}$ 使得 $b = a - kn$。
任取 $d \in S_1$，依定義有 $d \mid a$ 且 $d \mid n$。
根據整除的線性組合性質：
$d \mid a \text{ 且 } d \mid n \implies d \mid (a - kn) \implies d \mid b$
因為 $d \mid b$ 且 $d \mid n$，所以 $d \in S_2$。由此證得 $S_1 \subseteq S_2$。

步驟三：證明 $S_2 \subseteq S_1$
同理，由 $a = b + kn$，任取 $d \in S_2$，依定義有 $d \mid b$ 且 $d \mid n$。
根據整除的線性組合性質：
$d \mid b \text{ 且 } d \mid n \implies d \mid (b + kn) \implies d \mid a$
因為 $d \mid a$ 且 $d \mid n$，所以 $d \in S_1$。由此證得 $S_2 \subseteq S_1$。

步驟四：得出結論
由 $S_1 \subseteq S_2$ 且 $S_2 \subseteq S_1$，可得 $S_1 = S_2$。
由於兩集合完全相同，其最大元素必相等：