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

核心觀念
本題屬於離散數學中組合學（Combinatorics）的基本計數問題，主要考驗以下觀念與原則：

1. 組合公式（Combination Formula）：從 $n$ 個相異物中無順序取出 $k$ 個的組合數，記作 $C(n, k)$ 或 $\binom{n}{k}$，公式為：
   $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
   且具備對稱性質：$\binom{n}{k} = \binom{n}{n-k}$。
2. 乘法原理（Product Rule）：若完成一項任務需分為若干個步驟，且各步驟間互相獨立，則總方法數為各步驟方法數之相乘。
3. 加法原理（Sum Rule）：若完成一項任務可分為若干個互斥（Disjoint）的可能情況，則總方法數為各情況方法數之相加。

---

解題方法

(a) 要求恰好 7 名男性與 7 名女性

組成 14 人的委員會，且必須包含 7 男 7 女，可分為兩個獨立步驟：

1. 從 10 名男性中選出 7 名：
   $\binom{10}{7} = \binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$
2. 從 10 名女性中選出 7 名：
   $\binom{10}{7} = \binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

根據乘法原理，總選法數為：
$\binom{10}{7} \times \binom{10}{7} = 120 \times 120 = 14400$

(b) 要求至少 8 名男性

委員會總人數為 14 人，且男性總數僅有 10 人。條件限制「至少 8 名男性」（$m \ge 8$），故選取的男性人數 $m$ 可能為 8、9 或 10 人。按男性人數進行互斥分類推導：

• 情況一：選取 8 男 6 女

核心觀念

本題考查：

1. 雙條件命題 $a \leftrightarrow b$ 的定義：

   $a \leftrightarrow b \equiv (a \rightarrow b)\wedge(b\rightarrow a)$

2. 命題蘊涵的傳遞性：

   $a\rightarrow b,\quad b\rightarrow c \;\Longrightarrow\; a\rightarrow c$

令

$L=(r\leftrightarrow p)\wedge(p\leftrightarrow q)\wedge(q\leftrightarrow r)$

$R=(r\rightarrow p)\wedge(p\rightarrow q)\wedge(q\rightarrow r)$

欲證明 $L\leftrightarrow R$，只須證明 $L\rightarrow R$ 與 $R\rightarrow L$。

解題方法與推導

一、證明 $L\rightarrow R$

由 $L$ 可知：

$r\leftrightarrow p,\qquad p\leftrightarrow q,\qquad q\leftrightarrow r$

依雙條件命題的定義，每一個雙條件命題都包含兩個方向：

$r\leftrightarrow p \Longrightarrow r\rightarrow p$

$p\leftrightarrow q \Longrightarrow p\rightarrow q$

$q\leftrightarrow r \Longrightarrow q\rightarrow r$

因此可得：

$(r\rightarrow p)\wedge(p\rightarrow q)\wedge(q\rightarrow r)$

也就是：

$L\rightarrow R$

二、證明 $R\rightarrow L$

由 $R$ 可知：

$r\rightarrow p,\qquad p\rightarrow q,\qquad q\rightarrow r$

接著分別證明三個雙條件命題。

證明 $r\leftrightarrow p$

已知：

$r\rightarrow p$

又因為：

$p\rightarrow q,\qquad q\rightarrow r$

由蘊涵的傳遞性：

$p\rightarrow q\rightarrow r$

所以：

$p\rightarrow r$

因此：

$(r\rightarrow p)\wedge(p\rightarrow r)$

即：

$r\leftrightarrow p$

證明 $p\leftrightarrow q$

已知：

$p\rightarrow q$

又因為：

$q\rightarrow r,\qquad r\rightarrow p$

由蘊涵的傳遞性：

$q\rightarrow r\rightarrow p$

所以：

$q\rightarrow p$

因此：

核心觀念

1. 真子集（Proper Subset）定義：
   對於宇集 $U$ 中的兩集合 $A$ 與 $B$，$A$ 為 $B$ 的真子集（記作 $A \subset B$ 或 $A \subsetneq B$），當且僅當 $A$ 為 $B$ 的子集（$A \subseteq B$）且 $A$ 不等於 $B$（$A \neq B$）。
2. 量化語句（Quantified Statement）表示法：
   • 全稱量詞（Universal Quantifier, $\forall$）：用以表達「對宇集中所有的 $x$」。
   • 存在量詞（Existential Quantifier, $\exists$）：用以表達「宇集中存在至少一個 $x$」。
   • 條件句（Implication, $\rightarrow$）：$P \rightarrow Q \equiv \neg P \lor Q$。
3. 邏輯否定律與量詞變號律：
   • 量詞否定律：$\neg (\forall x, P(x)) \equiv \exists x, \neg P(x)$；$\neg (\exists x, P(x)) \equiv \forall x, \neg P(x)$。
   • 笛摩根定律（De Morgan's Laws）：$\neg (P \land Q) \equiv \neg P \lor \neg Q$。
   • 條件句否定律：$\neg (P \rightarrow Q) \equiv P \land \neg Q$。

---

解題方法與詳細推導

(a) 撰寫表示真子集關係 $A \subset B$ 的量化語句

依據集合論中真子集的定義，$A \subset B$ 等價於「$A \subseteq B$ 且 $A \neq B$」。將此定義轉譯為量化語句可拆解為兩個邏輯分量：

1. 表達 $A$ 是 $B$ 的子集 ($A \subseteq B$)：
   意即「宇集中任何屬於 $A$ 的元素，必定也屬於 $B$」。
   寫成量化語句為：
   $\forall x \in U, (x \in A \rightarrow x \in B)$

2. 表達 $A$ 不等於 $B$ ($A \neq B$)：
   在已知 $A \subseteq B$ 的前提下，$A \neq B$ 代表 $B$ 中至少存在一個元素不屬於 $A$（即 $B \not\subseteq A$）。
   寫成量化語句為：
   $\exists x \in U, (x \in B \land x \notin A)$

將上述兩條件以邏輯「與」（$\land$）連接，即得到表示 $A \subset B$ 的定案量化語句：
$(\forall x \in U, (x \in A \rightarrow x \in B)) \land (\exists x \in U, (x \in B \land x \notin A))$

---

(b) 否定 (a) 之結果以確定 $A \not\subset B$ 的條件

欲確定 $A$ 不是 $B$ 的真子集（$A \not\subset B$），對 (a) 小題的量化語句進行整體否定：

$\neg \left[ (\forall x \in U, (x \in A \rightarrow x \in B)) \land (\exists x \in U, (x \in B \land x \notin A)) \right]$

詳細推導步驟如下：

1. 套用笛摩根定律（De Morgan's Law）展開否定符號：
   $\neg (\forall x \in U, (x \in A \rightarrow x \in B)) \lor \neg (\exists x \in U, (x \in B \land x \notin A))$

2. 對各項分別進行量詞否定與邏輯化簡：

   • 前項否定：
     $\neg (\forall x \in U, (x \in A \rightarrow x \in B)) \equiv \exists x \in U, \neg(x \in A \rightarrow x \in B)$
     套用條件句否定律 $\neg(P \rightarrow Q) \equiv P \land \neg Q$，得：
     $\exists x \in U, (x \in A \land x \notin B)$
     （此項語意：存在元素屬於 $A$ 但不屬於 $B$，即 $A \not\subseteq B$）

核心觀念

本題屬於離散數學中的**組合計數（Combinatorial Counting）**問題，核心觀念包含：

1. 乘法原理（Rule of Product）：若一項作業可分解為兩個相互獨立的步驟，第一步驟有 $A$ 種選法，第二步驟有 $B$ 種選法，則完成該作業共有 $A \times B$ 種方法。
2. 一維連續區間選擇（Subsegment Selection）：在由 $n$ 個連續小單位組成的直線區間中，選擇長度為 $k$ 的連續區間，其起始位置共有 $n - k + 1$ 種選法。
3. 二維點陣／格子定位：確定棋盤上一個 $k \times k$ 的正方形，等價於分別在「水平方向（行）」與「垂直方向（列）」獨立選定長度為 $k$ 的連續區間。

---

解題方法

(a) 求 $9 \times 9$ 棋盤中 $3 \times 3$ 正方形的個數

1. 垂直方向（列選法）：
   棋盤共有 $9$ 列。若要放置邊長為 $3$ 的正方形，其頂端可佔據第 $1$ 至第 $7$ 列中的任意起始位置（例如第 $1$$3$ 列、第 $2$$4$ 列、……、第 $7$~$9$ 列）。
   起始位置選法數為：
   $9 - 3 + 1 = 7 \text{ 種}$

2. 水平方向（行選法）：
   棋盤共有 $9$ 行。同理，邊長為 $3$ 的正方形最左側可佔據第 $1$ 至第 $7$ 行中的任意起始位置。
   起始位置選法數為：
   $9 - 3 + 1 = 7 \text{ 種}$

3. 結合乘法原理：
   由於水平方向與垂直方向的選擇相互獨立，正方形的總數為水平選法數與垂直選法數之積：
   $7 \times 7 = 7^2 = 49$

---

(b) 求任意 $n \times n$ 棋盤中 $k \times k$ 正方形的個數（$1 \le k \le n$）

1. 一般化推導：
   對於固定尺寸為 $n \times n$ 的棋盤，欲選取邊長為 $k$ 的小正方形（其中 $1 \le k \le n$）：

   • 在垂直方向上，長度為 $n$ 的邊上挑選連續長度為 $k$ 的片段，其可能的起始位置有 $n - k + 1$ 個。
   • 在水平方向上，長度為 $n$ 的邊上挑選連續長度為 $k$ 的片段，其可能的起始位置亦有 $n - k + 1$ 個。

2. 計算總數：
   每一個 $k \times k$ 正方形唯一對應一組（垂直起始位置，水平起始位置）。由乘法原理可知，邊長為 $k$ 的正方形個數 $N(k)$ 為：

核心觀念

1. 鴿籠原理（Pigeonhole Principle）：若有 $n$ 個物件（鴿子）放入 $m$ 個容器（鴿籠），且 $n > m$，則至少有一個容器裝有 2 個或以上的物件。推廣至函數映射 $f: A \to B$，當集額 $|A| > |B|$ 時，$f$ 必不為單射（Injective），即存在 $x_1 \neq x_2 \in A$ 使得 $f(x_1) = f(x_2)$。
2. 集合子集計數與總和範圍：
   • 若集合 $S$ 之基數 $|S| = n$，則 $S$ 的非空子集個數為 $2^n - 1$。
   • 在元素大小受限制的情況下，精確估計所有非空子集元素總和可能產生的可能值區間（鴿籠數量）。

---

解題方法

證明目標：設 $S = \{a_1, a_2, a_3, a_4, a_5\}$ 為 5 個正整數所組成的集合，且滿足 $1 \le a_1 < a_2 < a_3 < a_4 < a_5 \le 9$。證明 $S$ 的所有非空子集之元素總和不可能全不相同。

證明步驟：

1. 計算鴿子數量（非空子集的個數）：
   集合 $S$ 共有 5 個元素，其非空子集的總數量為：
   $|P(S) \setminus \{\emptyset\}| = 2^5 - 1 = 31$
   即共有 31 個非空子集。

2. 估計鴿籠數量（子集總和的可能值數量）：
   設任意非空子集為 $A \subseteq S$，其元素總和記為 $S(A)$。

   • 最小值下界：單元素子集 $\{a_1\}$ 的總和最小，故 $S(A) \ge a_1$。
   • 最大值上界：全集 $S$ 本身的總和最大，故 $S(A) \le a_1 + a_2 + a_3 + a_4 + a_5$。

   所有非空子集的總和 $S(A)$ 皆為整數，且必落在閉區間 $[a_1, a_1 + a_2 + a_3 + a_4 + a_5]$ 內。
   該區間內可能出現的整數總數（即鴿籠數）最多為：
   $(a_1 + a_2 + a_3 + a_4 + a_5) - a_1 + 1 = a_2 + a_3 + a_4 + a_5 + 1$

3. 分項討論與邊界評估：
   已知 $1 \le a_1 < a_2 < a_3 < a_4 < a_5 \le 9$，故元素的上限分別為 $a_5 \le 9, a_4 \le 8, a_3 \le 7, a_2 \le 6$。
   因此，$a_2 + a_3 + a_4 + a_5$ 的最大可能值為 $6 + 7 + 8 + 9 = 30$。
   按此分成以下兩種情況討論：

由於 $A\neq\varnothing$，取 $A$ 中長度最短的字串 $w$。由 $A=A^2$，存在 $x,y\in A$ 使得

$$w=xy.$$

核心觀念

1. 無窮等比級數與母函數（Generating Functions）：
   在 $|x| < 1$ 的收斂區域內，無窮等比級數可表示為封閉形式（Closed Form）：
   $1 + x + x^2 + x^3 + \dots = \frac{1}{1-x} = (1-x)^{-1}$
   多項式連乘積 $(1 + x + x^2 + x^3 + \dots)^n$ 可轉化為負指數冪次 $(1-x)^{-n}$。

2. 負二項式定理（Negative Binomial Theorem）：
   對任意正整數 $n$ 與非負整數 $k$，展開式 $(1-x)^{-n}$ 中 $x^k$ 的係數符合負二項式展開：
   $(1-x)^{-n} = \sum_{k=0}^{\infty} \binom{-n}{k} (-x)^k = \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k$

3. 重複組合（Combinations with Repetition / Stars and Bars）：
   展開式中 $x^k$ 的係數，在組合計數上等價於求非負整數解 $e_1 + e_2 + \dots + e_n = k$（其中 $e_i \in \mathbb{N} \cup \{0\}$）的解個數，其重複組合數表示為：
   $H^n_k = \binom{n+k-1}{k} = \binom{n+k-1}{n-1}$

---

解題方法

(b) 子題：一般式推導

方法一：母函數代數推導法

1. 將級數化為封閉形式：
   $1 + x + x^2 + x^3 + \dots = \frac{1}{1-x}$
2. 將原式以負指數表示：
   $(1 + x + x^2 + x^3 + \dots)^n = \left(\frac{1}{1-x}\right)^n = (1-x)^{-n}$
3. 根據廣義二項式定理展開：
   $(1-x)^{-n} = \sum_{k=0}^{\infty} \binom{-n}{k} (-1)^k x^k$
4. 展開廣義組合數 $\binom{-n}{k}$：
   $\binom{-n}{k} = \frac{(-n)(-n-1)(-n-2)\dots(-n-k+1)}{k!} = \frac{(-1)^k \cdot n(n+1)(n+2)\dots(n+k-1)}{k!}$
5. 將 $\binom{-n}{k}$ 代回展開式，負號相消得 $(-1)^k \cdot (-1)^k = (-1)^{2k} = 1$：
   $\binom{-n}{k} (-1)^k = \frac{n(n+1)\dots(n+k-1)}{k!} = \binom{n+k-1}{k}$
6. 故 $(1 + x + x^2 + x^3 + \dots)^n$ 中 $x^k$ 的係數為：
   $\binom{n+k-1}{k} \quad \text{或} \quad \binom{n+k-1}{n-1} \quad \text{或} \quad H^n_k$

方法二：重複組合模型法

1. 將多項式連乘積寫開：
   $(1 + x + x^2 + x^3 + \dots)^n = \underbrace{(1 + x + x^2 + \dots)(1 + x + x^2 + \dots) \dots (1 + x + x^2 + \dots)}_{n \text{ 個括號}}$
2. 從第 $i$ 個括號中選出 $x^{e_i}$（$e_i \ge 0$），欲湊出 $x^k$，變數必須滿足：

核心觀念

本題為數論（Number Theory）中關於**模同餘（Modular Congruence）與整除性（Divisibility）**的基礎證明題，主要考查以下定義與性質：

1. 模同餘的定義：對於整數 $c, d$ 與正整數 $q$，若 $c \equiv d \pmod q$，定義為 $q$ 能整除 $(c - d)$，記作 $q \mid (c - d)$。
2. 整除的定義：對於整數 $x, y$（其中 $x \neq 0$），若 $x \mid y$，代表存在一個整數 $k \in \mathbb{Z}$，使得 $y = k \cdot x$。
3. 整數乘法的封閉性（Closure Property）：若 $k, m \in \mathbb{Z}$，則其積 $k \cdot m \in \mathbb{Z}$。

---

解題方法

本題採用直接證明法（Direct Proof）。解題切入點是將抽象的「同餘關係」與「整除關係」依定義還原為具體的「整數代數式」，再進行代換與合併。

詳細推導步驟：

1. 展開同餘條件：
   根據模同餘的定義，由 $c \equiv d \pmod q$ 可得：
   $q \mid (c - d)$
   再根據整除的定義，存在一個整數 $k \in \mathbb{Z}$ 使得：
   $c - d = k \cdot q \quad \text{--- (式 1)}$

2. 展開整除條件：
   根據整除的定義，由 $p \mid q$ 表示存在一個整數 $m \in \mathbb{Z}$ 使得：
   $q = m \cdot p \quad \text{--- (式 2)}$

3. 代換與邏輯推導：
   將 (式 2) 代入 (式 1) 中，可得：
   $c - d = k \cdot (m \cdot p) = (k \cdot m) \cdot p$
   因為 $k, m \in \mathbb{Z}$，根據整數乘法的封閉性，整數相乘結果仍為整數，故令 $n = k \cdot m \in \mathbb{Z}$。
   上式可改寫為：
   $c - d = n \cdot p \quad (n \in \mathbb{Z})$