113 年 國立嘉義大學資訊工程學系碩士班《離散數學》

核心觀念

全稱量詞 $\forall$ 表示「每一個」都符合；存在量詞 $\exists$ 表示「至少有一個」符合。判斷時，依量詞順序檢查真值表即可：

• $\forall x\exists y\,P(x,y)$：每一列都至少有一個 $T$。
• $\forall y\exists x\,P(x,y)$：每一欄都至少有一個 $T$。
• $\exists x\forall y\,P(x,y)$：至少有一列全部是 $T$。
• $\exists y\forall x\,P(x,y)$：至少有一欄全部是 $T$。

解題方法

依原圖中的式子判斷。表格各列為：

• $x=1$：$T,F,F,F$
• $x=2$：$F,T,T,F$
• $x=3$：$T,T,T,T$
• $x=4$：$F,F,F,F$

逐列檢查「每列是否有 $T$」，逐欄檢查「每欄是否有 $T$」；若要判斷是否存在全為 $T$ 的列或欄，就檢查是否有一整列或一整欄皆為 $T$。

選項分析

(a) $\forall x\exists y\,P(x,y)$：錯誤。此式要求每一列都至少有一個 $T$，但 $x=4$ 這一列全是 $F$，不符合條件。

核心觀念

本題考查二階非齊次常係數線性遞迴關係（Second-Order Non-Homogeneous Linear Recurrence Relation with Constant Coefficients）的求解。

求解此類遞迴關係式包含以下核心步驟：

1. 齊次通解（Homogeneous Solution, $a_n^{(h)}$）：
   將等號右側非齊次項設為 $0$，得到齊次遞迴關係式。解其特徵方程式（Characteristic Equation）求出特徵根 $r_1, r_2$。若特徵根為相異實根，則齊次通解為：
   $a_n^{(h)} = c_1 r_1^n + c_2 r_2^n$

2. 特設解（Particular Solution, $a_n^{(p)}$）：
   根據非齊次項 $F(n) = 3^n$ 的形式，利用**未定係數法（Method of Undetermined Coefficients）**假設特設解。由於非齊次項中的底數 $3$ 恰好為特徵方程式的單重根（重數 $m = 1$），依據修正法則，特設解形式須乘上 $n^1$，即設為：
   $a_n^{(p)} = A \cdot n \cdot 3^n$
   將其代回原遞迴關係式求出未知係數 $A$。

3. 完全解（General Solution, $a_n$）與初始條件：
   完全解為齊次通解與特設解之和（$a_n = a_n^{(h)} + a_n^{(p)}$）。最後代入初始條件 $a_0 = 0$ 與 $a_1 = 1$，解出常數 $c_1$ 與 $c_2$。

解題方法

步驟一：求解齊次解 $a_n^{(h)}$

考慮對應的齊次遞迴關係式：
$3a_n - 10a_{n-1} + 3a_{n-2} = 0$

寫出特徵方程式：
$3r^2 - 10r + 3 = 0$

因式分解：
$(3r - 1)(r - 3) = 0$

解得特徵根：
$r_1 = 3, \quad r_2 = \frac{1}{3}$

因此，齊次解的形式為：
$a_n^{(h)} = c_1 \cdot 3^n + c_2 \cdot \left(\frac{1}{3}\right)^n = c_1 \cdot 3^n + c_2 \cdot 3^{-n}$

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

原式的非齊次項為 $F(n) = 3^n$。
因為 $3$ 已是齊次特徵方程式的單重根，故特設解應設為：
$a_n^{(p)} = A \cdot n \cdot 3^n$

將 $a_n^{(p)}$ 代回原遞迴關係式 $3a_n - 10a_{n-1} + 3a_{n-2} = 3^n$：
$3 \left( A \cdot n \cdot 3^n \right) - 10 \left( A \cdot (n-1) \cdot 3^{n-1} \right) + 3 \left( A \cdot (n-2) \cdot 3^{n-2} \right) = 3^n$

兩邊同除以 $3^{n-2}$：
$3 \cdot A n \cdot 3^2 - 10 \cdot A (n-1) \cdot 3^1 + 3 \cdot A (n-2) \cdot 3^0 = 3^2$
$27 A n - 30 A (n-1) + 3 A (n-2) = 9$

核心觀念

本題考查數論（Number Theory）中的核心基礎——除法定理（Division Algorithm）。

• 除法定理定義：
  對任意兩整數 $a$（被除數）與 $b$（除數，且 $b \neq 0$），必存在唯一的一組整數 $q$（商數，Quotient）與 $r$（餘數，Remainder），滿足：
  $a = qb + r \quad \text{其中 } 0 \le r < |b|$

• 關鍵限制條件：
  餘數 $r$ 的範圍必須符合 $0 \le r < |b|$。此條件規定餘數必須為非負整數。當被除數 $a$ 為負數時，商數 $q$ 必須向負無窮大方向取整數（即地板函數 $\lfloor a/b \rfloor$），確保算出的餘數 $r \ge 0$。

解題方法

根據除法定理的公式 $a = qb + r$（限制 $0 \le r < |b|$），分別推導兩小題：

(a) 當 $a = 387, b = 28$ 時

1. 求商數 $q$：
   將 $a$ 除以 $b$ 並取地板函數（向下取整）：
   $q = \left\lfloor \frac{387}{28} \right\rfloor = \lfloor 13.8214... \rfloor = 13$

2. 求餘數 $r$：
   依據 $r = a - qb$ 計算：
   $r = 387 - (13 \times 28) = 387 - 364 = 23$

3. 驗證區間條件：
   檢查餘數範圍是否符合 $0 \le r < |b|$：
   $0 \le 23 < 28$
   完全符合除法定理規範。

(b) 當 $a = -78, b = 15$ 時

1. 求商數 $q$：
   將 $a$ 除以 $b$ 並取地板函數（向下取整）：
   $q = \left\lfloor \frac{-78}{15} \right\rfloor = \lfloor -5.2 \rfloor = -6$

2. 求餘數 $r$：
   依據 $r = a - qb$ 計算：

二元搜尋樹（BST）滿足「左子樹鍵值 $<$ 根節點 $<$ 右子樹鍵值」。依前序序列重建：

        31
      /    \
    21      40
   /  \    /  \
 11   26  36  43
   \  /
   16 24

核心觀念

本題為離散數學中「組合計數（Combinatorics）」與「離散機率（Discrete Probability）」的典型綜合題，核心觀念包含：

1. 古典機率（Classical Probability）：在有限且等可能的樣本空間 $S$ 中，任意事件 $E$ 發生的機率定義為：
   $P(E) = \frac{|E|}{|S|}$
2. 取捨原理（Inclusion-Exclusion Principle，又稱排容原理）：對於任意兩個有限集合 $A$ 與 $B$，其聯集的元素個數為：
   $|A \cup B| = |A| + |B| - |A \cap B|$
3. 整數倍數計數與地板函數（Floor Function）：在不大於正整數 $n$ 的正整數集合中，能被正整數 $k$ 整除的數字個數為 $\lfloor \frac{n}{k} \rfloor$。若要同時被 $k_1$ 與 $k_2$ 整除，則該數字必須被其最小公倍數 $\text{lcm}(k_1, k_2)$ 整除。
4. 餘事件定理（Complementary Event Theorem）：事件 $E$ 不發生的機率等於 1 減去事件 $E$ 發生的機率：
   $P(E^c) = 1 - P(E) = \frac{|S| - |E|}{|S|}$

解題方法

• (a) 小題切入點：求不大於 100 且能被 3 或 5 整除的整數個數。直接定義事件 $A$（被 3 整除）與事件 $B$（被 5 整除），利用取捨原理計算聯集個數 $|A \cup B|$，再除以總數 $|S| = 100$ 即可。
• (b) 小題切入點：求不大於 1000 且「不能」被 7 或 9 整除的整數個數。由於正面討論「兩者皆不能整除」比較複雜，採用「餘事件法」：先求能被 7 或 9 整除的事件個數 $|C \cup D|$，再以總個數 1000 扣除該值得到餘事件個數，最後計算出機率。

子題詳細推導與分析

(a) 不大於 100 且能被 3 或 5 整除的機率

1. 定義樣本空間與事件：

   • 樣本空間 $S = \{1, 2, 3, \dots, 100\}$，總個數 $|S| = 100$。
   • 設集合 $A$ 為 $S$ 中能被 3 整除的整數集合。
   • 設集合 $B$ 為 $S$ 中能被 5 整除的整數集合。

2. 計算各集合之元素個數：

   • 能被 3 整除的個數：
     $|A| = \left\lfloor \frac{100}{3} \right\rfloor = 33$
   • 能被 5 整除的個數：
     $|B| = \left\lfloor \frac{100}{5} \right\rfloor = 20$
   • 同時能被 3 與 5 整除（即能被 $\text{lcm}(3, 5) = 15$ 整除）的個數：
     $|A \cap B| = \left\lfloor \frac{100}{15} \right\rfloor = 6$

設第 $i$ 種餅乾選取 $x_i$ 個，則