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

核心觀念

本題考查數論（Number Theory）中的**二元一次丟番圖方程式（Linear Diophantine Equation）**求正整數解的個數。

用到之核心定義與定理如下：

1. 丟番圖方程式可解性定理：對於二元一次方程式 $ax + by = c$（其中 $a, b, c \in \mathbb{Z}$ 且 $a, b$ 不全為 0），若且唯若 $\gcd(a, b) \mid c$ 時，該方程式存在整數解。
2. 通解結構定理：若已求得一組特解 $(x_0, y_0)$，則其所有整數解（通解）可表示為：
   $x = x_0 + \frac{b}{\gcd(a, b)} \cdot k$
   $y = y_0 - \frac{a}{\gcd(a, b)} \cdot k \quad (k \in \mathbb{Z})$
3. 正整數解約束條件：題目要求「正整數解」（Positive Integer Solutions），意即 $x > 0$ 且 $y > 0$（亦即 $x, y \ge 1$ 且 $x, y \in \mathbb{Z}$）。

---

解題方法

步驟一：確認解的存在性

給定方程式：
$4x + 7y = 117$
計算係數的最大公因數：$\gcd(4, 7) = 1$。
因為 $1 \mid 117$，故此方程式必存在整數解。

步驟二：尋求特解 $(x_0, y_0)$

利用同餘（Congruence）的觀念求解 $x$ 的特解：
$4x + 7y = 117 \implies 4x \equiv 117 \pmod 7$
將 $117$ 對 $7$ 取模：$117 = 7 \times 16 + 5 \equiv 5 \pmod 7$。
同餘式可寫為：
$4x \equiv 5 \equiv 12 \pmod 7$
兩邊同除以 $4$（因為 $\gcd(4, 7) = 1$）：
$x \equiv 3 \pmod 7$
取最小正整數特解 $x_0 = 3$，代回原方程式求出對應的 $y_0$：
$4(3) + 7y_0 = 117 \implies 12 + 7y_0 = 117 \implies 7y_0 = 105 \implies y_0 = 15$
得到特解為 $(x_0, y_0) = (3, 15)$。

步驟三：建立通解公式

將特解與係數帶入二元一次方程式的通解結構：
$x = 3 + 7k$
$y = 15 - 4k \quad (k \in \mathbb{Z})$

步驟四：求解參數 $k$ 的正整數範圍

根據正整數解條件（$x \ge 1$ 且 $y \ge 1$）：

1. 由 $x \ge 1$：
   $3 + 7k \ge 1 \implies 7k \ge -2 \implies k \ge -\frac{2}{7}$
   因為 $k \in \mathbb{Z}$，故 $k \ge 0$。
2. 由 $y \ge 1$：

核心觀念

本題考查組合數學中的集合子集個數與乘法原理（Product Rule）。

1. 子集總數定理：若有限集合 $A$ 包含 $m$ 個元素，則 $A$ 的子集總數為 $2^m$。這是因為對於集合中的每一個元素，在構成子集時都恰有「包含」與「不包含」 $2$ 種選擇。
2. 受限子集計數：當指定某 $k$ 個元素「必須包含」在子集中時，這 $k$ 個元素的選取狀態已被完全固定（各有 $1$ 種選擇）。因此，滿足條件的子集數量，完全取決於其餘未被限制的 $(m - k)$ 個元素，數量即為 $2^{m - k}$。

---

解題方法

步驟一：計算全集元素個數

給定集合為 $S = \{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13\}$。
計算連續整數集合的元素總數 $n(S)$：
$n(S) = 13 - 3 + 1 = 11$

步驟二：分析約束條件與可自由選擇的元素

題目規定子集必須包含 $3, 9, 13$ 這 $3$ 個特定元素。
將這 $3$ 個固定元素自原集合中扣除，剩餘可自由選擇「選入或不選入」子集的元素集合為：
$S' = S \setminus \{3, 9, 13\} = \{4, 5, 6, 7, 8, 10, 11, 12\}$
剩餘自由元素個數為：
$n(S') = 11 - 3 = 8$

步驟三：運用乘法原理推導結果

對於 $S'$ 中的這 $8$ 個元素，每一個元素皆有 $2$ 種可能性（選或不選），根據乘法原理，包含 $3, 9, 13$ 的子集總數為：
$2^8 = 256$

---

選項分析

核心觀念

本題考查**合成函數（Composite Function）**的基本定義與映射運算。

設 $A, B, C$ 為集合，若有兩個函數 $f: A \to B$ 與 $g: B \to C$，則其合成函數記做 $g \circ f: A \to C$，定義為：
$(g \circ f)(x) = g(f(x)), \quad \forall x \in A$

在此運算中，作用順序是由右至左：輸入值 $x$ 先經過函數 $f$ 映射得到中間值 $f(x)$，再將該中間值作為函數 $g$ 的輸入，經由 $g$ 映射出最終結果 $g(f(x))$。

---

解題方法

已知函數 $f$ 的定義域為 $\{1, 2, 3, 4\}$，欲求合成函數 $g \circ f$ 的所有映射值，依定義分別帶入各元素進行兩階段映射計算：

1. 計算 $(g \circ f)(1)$：
   代入 $x = 1$，先求 $f(1) = 3$，再求 $g(3) = 4$。
   $(g \circ f)(1) = g(f(1)) = g(3) = 4$

2. 計算 $(g \circ f)(2)$：
   代入 $x = 2$，先求 $f(2) = 1$，再求 $g(1) = 5$。
   $(g \circ f)(2) = g(f(2)) = g(1) = 5$

3. 計算 $(g \circ f)(3)$：
   代入 $x = 3$，先求 $f(3) = 4$，再求 $g(4) = 1$。
   $(g \circ f)(3) = g(f(3)) = g(4) = 1$

4. 計算 $(g \circ f)(4)$：
   代入 $x = 4$，先求 $f(4) = 6$，再求 $g(6) = 2$。

核心觀念

本題屬於離散數學中組合計數（Combinatorics）的**不全相異物排列（Multiset Permutations）與受限制排列（Restricted Permutations）**問題。

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

1. 不全相異物排列公式（Multiset Permutation Formula）：
   若有 $n$ 個元素，其中包含 $k$ 種重複元素，個數分別為 $n_1, n_2, \dots, n_k$，且 $\sum_{i=1}^k n_i = n$，則其所有相異排列數為：
   $\frac{n!}{n_1! \, n_2! \cdots n_k!}$

2. 不相鄰排列的計數策略：
   處理「指定元素互不相鄰」問題，主要有兩種切入角度：

   • 插空法（Insertion Method）：先將沒有限制的元素排好，再將受限元素插入相鄰元素間形成的空隙中。
   • 反面扣除法（Complementary Counting）：利用排容原理，用「全部任意排列數」減去「受限元素相鄰的排列數」。

---

解題方法

步驟一：分析字串的字元組成
字串 LOVENSYSU 共有 9 個字元，統計各字母出現頻率：

• 字母 L, O, V, E, N, Y, U 各出現 1 次（共 7 個相異字元）。
• 字母 S 出現 2 次（重複字元）。

步驟二：選擇解法推導與計算

方法一：插空法（建議解法）

1. 排列 7 個非 S 的相異字元：
   將 L, O, V, E, N, Y, U 進行全排列，方法數為：
   $7! = 5040$

2. 插入 2 個相同的 S：
   7 個字元排定後，包含前後兩端共會產生 8 個可供插入的空隙：
   $\text{\_ C}_1\text{ \_ C}_2\text{ \_ C}_3\text{ \_ C}_4\text{ \_ C}_5\text{ \_ C}_6\text{ \_ C}_7\text{ \_}$
   由於 2 個 S 為相同字元，只需從這 8 個空隙中選出 2 個空隙各放入 1 個 S 即可，方法數為：
   $\binom{8}{2} = \frac{8 \times 7}{2 \times 1} = 28$

3. 計算總排列數：
   由乘法原理，兩 S 不相鄰的排列總數為：
   $\text{排列數} = 7! \times \binom{8}{2} = 5040 \times 28 = 141120$

方法二：反面扣除法

1. 計算 9 個字元的所有任意排列數（全集）：
   不考慮任何限制，9 個字元中包含 2 個相同的 S，排列數為：

核心觀念

本題考驗集合論中**差集（Difference Set / Relative Complement）**的化簡技巧，以及差集與交集、聯集、補集之間的代數等式與運算性質。解題所需的基礎定理與定義如下：

1. 差集之補集定義：
   $A - B = A \cap B^c$
2. 笛摩根定律（De Morgan's Laws）：
   $(B \cup C)^c = B^c \cap C^c$
   $(B \cap C)^c = B^c \cup C^c$
3. 集合交集的結合律與交換律：
   $(A \cap B^c) \cap C^c = A \cap (B^c \cap C^c) = (A \cap C^c) \cap B^c$
4. 集合交集對聯集的分配律：
   $X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)$

---

解題方法

驗證集合等式主要採用兩種策略：

1. 集合代數法（Set Algebra）：將所有差集符號「$-$」透過定義轉換為交集「$\cap$」與補集「$^c$」，再運用集合代數律（結合律、分配律、笛摩根定律等）進行邏輯化簡與推導。
2. 反例法（Counterexample Method）：若要否定一個集合等式，只需找出一個具體的反例集合，證明左式（LHS）與右式（RHS）所包含的元素不相等即可。

本題將對各選項進行代數推導與化簡，找出不成立的選項。

---

選項分析

• 選項 (a) $(A-B)-C = A-(B \cup C)$：正確（不選）

  • 左式代數推導：
    $(A-B)-C = (A \cap B^c) \cap C^c$
  • 根據交集結合律與笛摩根定律：
    $(A \cap B^c) \cap C^c = A \cap (B^c \cap C^c) = A \cap (B \cup C)^c = A - (B \cup C)$
  • 左右兩式恆等，此敘述正確。

• 選項 (b) $(A-B)-C = (A-C)-B$：正確（不選）

  • 左式代數推導：
    $(A-B)-C = (A \cap B^c) \cap C^c$
  • 根據交集的結合律與交換律：
    $(A \cap B^c) \cap C^c = (A \cap C^c) \cap B^c = (A - C) - B$
  • 左右兩式恆等，此敘述正確。

• 選項 (c) $(A-B)-C = A-(B \cap C)$：錯誤（應選此項）

  • 右式代數推導：

核心觀念

本題考查組合學（Combinatorics）中「二項式係數對稱性（Symmetric Property of Binomial Coefficients）」與「子集總數公式（Power Set Cardinality）」。

1. 子集數量與二項式係數：
   設 $A$ 為包含 $n$ 個元素的有限集合，則大小為 $k$ 的子集數量為 $\binom{n}{k}$。
2. 所有子集總數：
   根據二項式定理，集合 $A$ 的所有子集個數為：
   $\sum_{k=0}^{n} \binom{n}{k} = 2^n$
3. 二項式係數對稱恆等式：
   對於任意 $0 \le k \le n$，恆滿足：
   $\binom{n}{k} = \binom{n}{n-k}$

---

解題方法

已知集合 $A$ 的元素個數 $n = 21$。題目要求計算元素個數不少於 11 個（即 $|S| \ge 11$）的子集數量，亦即求取下列和式：
$S_{\text{target}} = \sum_{k=11}^{21} \binom{21}{k}$

1. 列出所有子集的求和關係：
   集合 $A$ 的所有子集總數可分成 22 個二項式係數相加：
   $\sum_{k=0}^{21} \binom{21}{k} = \binom{21}{0} + \binom{21}{1} + \dots + \binom{21}{10} + \binom{21}{11} + \dots + \binom{21}{21} = 2^{21}$

2. 利用對稱性分段：
   根據對稱公式 $\binom{21}{k} = \binom{21}{21-k}$，可得前半段 11 項與後半段 11 項兩兩相等：
   $\binom{21}{0} = \binom{21}{21}$
   $\binom{21}{1} = \binom{21}{20}$
   $\vdots$
   $\binom{21}{10} = \binom{21}{11}$

   因此，前半段子集數與後半段子集數完全相同：
   $\sum_{k=0}^{10} \binom{21}{k} = \sum_{k=11}^{21} \binom{21}{k}$

3. 計算目標數值：
   將對稱關係代回子集總數式：
   $2 \times \sum_{k=11}^{21} \binom{21}{k} = 2^{21}$

核心觀念

本題旨在考驗離散數學中**複合函數（Composite Function）**的定義與數值計算。

1. 複合函數定義：設 $f$ 與 $g$ 為兩個函數，其複合函數記作 $g \circ f$，定義為：
   $(g \circ f)(x) = g(f(x))$
2. 多重複合函數求值：對於三層複合函數 $(g \circ f \circ g)(x) = g(f(g(x)))$，必須遵循「由內而外（即由右至左）」的代入順序：
   • 先計算最內層的值 $u = g(x)$。
   • 再將 $u$ 代入中間層計算 $v = f(u)$。
   • 最後將 $v$ 代入最外層計算 $g(v)$。

---

解題方法

題目要求計算 $g \circ f \circ g(4)$ 的值，即求解 $g(f(g(4)))$。我們按照「由右至左（由內而外）」的三個關鍵步驟逐步推導：

1. 第一步：計算最內層 $g(4)$
   已知 $g(x) = 3x^2 - 10x - 2$，將 $x = 4$ 代入：
   $g(4) = 3(4)^2 - 10(4) - 2 = 3(16) - 40 - 2 = 48 - 40 - 2 = 6$

2. 第二步：計算中間層 $f(g(4)) = f(6)$
   已知 $f(x) = 2x^3 - 70x - 9$，將 $x = 6$ 代入：
   $f(6) = 2(6)^3 - 70(6) - 9 = 2(216) - 420 - 9 = 432 - 420 - 9 = 3$

核心觀念

1. 不相選/不相鄰排列（Non-adjacent Permutation）：處理指定元素「不得相鄰」的直線排列問題，常見解法有：
   • 扣除法（補集法）：全域任意排列數 $-$ 指定元素相鄰的排列數。
   • 插空法（間隙法）：先將無限制的元素排好，再將不得相鄰的元素插入其形成的空隙中。
2. 相同物重複排列（Multiset Permutation）：設有 $n$ 個物件，其中有 $n_1$ 個相同物類別 1、$n_2$ 個相同物類別 2、…、$n_k$ 個相同物類別 $k$（滿足 $\sum_{i=1}^k n_i = n$），其直線排列的相異排法總數為：
   $\frac{n!}{n_1! \, n_2! \, \cdots \, n_k!}$

---

解題方法

首先對字串 ANSYSUAA 進行字元數量盤點：

• 字母 A：3 個
• 字母 N：1 個
• 字母 S：2 個
• 字母 Y：1 個
• 字母 U：1 個

總字母數 $n = 3 + 1 + 2 + 1 + 1 = 8$。題目要求 Y 與 U 不得相鄰。以下提供兩種標準解法導出解答：

方法一：扣除法（反面扣除法）

1. 計算全域任意排列數：
   將 8 個字母（含 3 個 A、2 個 S、1 個 N、1 個 Y、1 個 U）任意直線排列：
   $\text{Total} = \frac{8!}{3! \times 2! \times 1! \times 1! \times 1!} = \frac{40320}{6 \times 2} = 3360$

2. 計算 Y 與 U 相鄰的排列數：
   將 Y 與 U 綑綁視為一個複合元素 $\text{(YU)}$。此時相當於排列以下 7 個元素：$\text{(YU)}, \text{A}, \text{A}, \text{A}, \text{N}, \text{S}, \text{S}$。

   • 7 個元素的相異物與相同物直線排列數為：
     $\frac{7!}{3! \times 2!} = \frac{5040}{12} = 420$
   • 綑綁內部 Y 與 U 可互換順序（$\text{YU}$ 或 $\text{UY}$），有 $2! = 2$ 種排法。
   • 故相鄰排列數為：
     $\text{Adjacent} = 420 \times 2! = 840$

3. 計算 Y 與 U 不相鄰的排列數：
   $\text{Valid} = \text{Total} - \text{Adjacent} = 3360 - 840 = 2520$

---

方法二：插空法（間隙法）

核心觀念

本題考查命題邏輯（Propositional Logic）中**條件句（Conditional Statement）**的真值特性與基本邏輯運算子的運算規則：

1. 條件句的真值特性：
   對於條件句 $A \rightarrow B$，當且僅當前項 $A$ 為真（True, $\text{T}$）且後項 $B$ 為假（False, $\text{F}$）時，其真值才為假（$\text{F}$）；其餘情況（$\text{T}\rightarrow\text{T}$、$\text{F}\rightarrow\text{T}$、$\text{F}\rightarrow\text{F}$）皆為真（$\text{T}$）。
2. 基本邏輯運算子定義：
   • 取與（Conjunction, $\wedge$）：僅在參與運算的命題皆為 $\text{T}$ 時，結果才為 $\text{T}$。
   • 取或（Disjunction, $\vee$）：只要參與運算的命題中有任一者為 $\text{T}$，結果即為 $\text{T}$。
   • 否定（Negation, $\neg$）：將命題真值反轉（$\text{T} \mapsto \text{F}$，$\text{F} \mapsto \text{T}$）。
3. 邏輯運算優先順序（Precedence）：
   在沒有括號的情況下，優先順序為：否定 $\neg$ $>$ 取與 $\wedge$ $>$ 取或 $\vee$ $>$ 條件句 $\rightarrow$。

---

解題方法

步驟一：推導各基本命題的唯一真值
題目給定複合命題 $(p \wedge q) \rightarrow r$ 為假（$\text{F}$）。
根據條件句假值的定義：

• 前項 $(p \wedge q)$ 必須為真（$\text{T}$）
• 後項 $r$ 必須為假（$\text{F}$）

由 $p \wedge q \equiv \text{T}$，根據「取與」的定義，可推出：
$p \equiv \text{T}, \quad q \equiv \text{T}$

結合後項可完整獲得三基本命題的真值：
$p = \text{T}, \quad q = \text{T}, \quad r = \text{F}$

步驟二：代入各選項進行邏輯檢驗
將求得的真值組合 $(p, q, r) = (\text{T}, \text{T}, \text{F})$ 分別代入各選項的敘述中，判斷各敘述本身的真假（True 或 False）。

---

選項分析

核心觀念

1. 映滿函數（Onto / Surjective Function）的定義：
   設 $f: X \to Y$ 為一函數，若對於對應域（Codomain）$Y$ 中的每一個元素 $y \in Y$，都至少存在一個定義域（Domain）$X$ 中的元素 $x \in X$ 使得 $f(x) = y$，則稱 $f$ 為映滿函數（值域等於對應域，即 $f(X) = Y$）。

2. 函數總數公式：
   設 $|X| = m$ 且 $|Y| = n$，從 $X$ 到 $Y$ 的所有可能函數總數為 $n^m$。

3. 映滿函數數量的計算公式：

   • 方法一（排容原理 / 扣除法）：
     當對應域大小 $n = 2$ 時，非映滿函數僅包含「所有元素皆映射至第一個元素」與「所有元素皆映射至第二個元素」這 2 個常數函數（Constant Functions）。因此，映滿函數數量為：
     $n^m - 2 = 2^m - 2$
   • 方法二（第二類 Stirling 數）：
     從大小為 $m$ 的集合映射到大小為 $n$ 的集合，其映滿函數總數可表示為：
     $n! \cdot S(m, n)$
     其中 $S(m, n)$ 為將 $m$ 個相異物分成 $n$ 個相同非空堆的第二類 Stirling 數（Stirling Numbers of the Second Kind）。

---

解題方法

本題給定定義域 $X = \{1, 2, 3, 4\}$（$|X| = m = 4$）與對應域 $Y = \{a, b\}$（$|Y| = n = 2$）。

步驟一：計算從 $X$ 到 $Y$ 的所有函數總數

每一個 $X$ 中的元素都有 2 種選擇（可以映射至 $a$ 或 $b$），故總函數個數為：

核心觀念

本題主要考查離散數學中**有限級數和（Finite Summation）與等差數列（Arithmetic Progression）**的求和公式，以及多項式次數與常數項的定義。

1. 等差級數求和公式：若一數列為等差數列，其首項為 $a_1$、末項為 $a_N$、項數為 $N$，則級數和為：
   $S_N = \frac{N \times (a_1 + a_N)}{2}$
2. 級數拆解性質：
   $\sum_{i=k}^{n} a_i = \sum_{i=1}^{n} a_i - \sum_{i=1}^{k-1} a_i$
   其中自然數求和公式為 $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$。
3. 多項式的階（Order/Degree）與常數項：多項式 $f(n) = a_k n^k + \dots + a_1 n + a_0$ 中，最高次方項 $n^k$ 的指數 $k$ 即為多項式的階（Order/Degree）；不含變數項的純數值 $a_0$ 即為常數項。

---

解題方法

目標為求出 $f(n) = \sum_{i=5}^{n} (2i + 9)$ 的封閉形式（Closed-form expression），並代入特定值進行計算與選項驗證。

方法一：等差級數求和法

觀察被加項 $a_i = 2i + 9$ 為一首項與公差明確的等差數列：

• 首項（$i=5$）：$a_5 = 2(5) + 9 = 19$
• 末項（$i=n$）：$a_n = 2n + 9$
• 項數 $N$：從 $5$ 到 $n$ 共有 $N = n - 5 + 1 = n - 4$ 項

代入等差級數求和公式：
$f(n) = \frac{(n - 4) \cdot [19 + (2n + 9)]}{2}$
$f(n) = \frac{(n - 4) \cdot (2n + 28)}{2}$
$f(n) = (n - 4)(n + 14)$
$f(n) = n^2 + 10n - 56$

方法二：標準級數拆解法

利用和的拆解性質：
$f(n) = \sum_{i=5}^{n} (2i + 9) = \sum_{i=1}^{n} (2i + 9) - \sum_{i=1}^{4} (2i + 9)$

計算前 $n$ 項和：
$\sum_{i=1}^{n} (2i + 9) = 2 \sum_{i=1}^{n} i + 9n = 2 \cdot \frac{n(n+1)}{2} + 9n = n^2 + n + 9n = n^2 + 10n$

核心觀念

本題考驗「對數（Logarithm）的基本運算性質」與「對數方程式的求解及真數條件驗證」。
主要使用的定義與定理如下：

1. 對數相減律（商律）：
   $\log_b A - \log_b B = \log_b \left(\frac{A}{B}\right) \quad (A > 0, B > 0, b > 0, b \neq 1)$
2. 對數與指數的互換定義：
   $\log_b y = x \iff y = b^x$
3. 對數的真數條件：
   對於 $\log_b f(x)$，變數代入後必須滿足真數 $f(x) > 0$。

---

解題方法

步驟一：運用對數律合併左式
根據對數相減律，將左式的兩項合併：
$\log_{10}(3x^2) - \log_{10} 6 = 1$
$\iff \log_{10}\left(\frac{3x^2}{6}\right) = 1$

簡化真數的分式：
$\log_{10}\left(\frac{x^2}{2}\right) = 1$

步驟二：轉換為指數形式求解 $x$
依據對數定義，底數為 10，可得：
$\frac{x^2}{2} = 10^1 = 10$
兩邊同乘以 2：
$x^2 = 20$
開平方解得：
$x = \sqrt{20} \quad \text{或} \quad x = -\sqrt{20}$

步驟三：驗證真數條件
原式對數項的真數為 $3x^2$。
不論 $x = \sqrt{20}$ 或 $x = -\sqrt{20}$，其平方均為 $x^2 = 20$，代入得 $3x^2 = 60 > 0$，皆符合真數必須大於 0 的定義。因此正負兩解皆為有效解。

步驟四：求數值近似值並與選項比對
評估 $\sqrt{20}$ 的數值：
因 $4^2 = 16$ 且 $5^2 = 25$，可知 $4 < \sqrt{20} < 5$。
精確計算得 $\sqrt{20} \approx 4.47214$。

因此方程式的兩個解分別為：
$x_1 \approx 4.472, \quad x_2 \approx -4.472$

核心觀念

本題考查**二項式定理（Binomial Theorem）與多項式係數和（Sum of Coefficients）**的求法。

對於多項式 $P(x, y) = (ax + by)^n$，其二項式展開式為：
$(ax + by)^n = \sum_{k=0}^{n} \binom{n}{k} (ax)^{n-k} (by)^k$

展开式中所有項的係數總和，即為將所有變數皆代入 $1$ 時的多項式函數值 $P(1, 1)$。

---

解題方法

1. 建立多項式函數：
   設 $P(x, y) = (3x - 5y)^{11}$。

2. 代入變數求係數和：
   要求展開式中所有係數的總和，將 $x = 1$ 與 $y = 1$ 代入函數：
   $P(1, 1) = (3 \cdot 1 - 5 \cdot 1)^{11} = (3 - 5)^{11}$

3. 計算指數數值：
   $(3 - 5)^{11} = (-2)^{11}$
   由於底數為負數（$-2$），且次方為奇數（$11$），運算結果必然保持負號：
   $(-2)^{11} = -2048$

核心觀念

本題考查**二項式定理（Binomial Theorem）**及其展開式一般項的應用。
對任意實數 $a, b$ 與正整數 $n$，二項式定理展開式如下：
$(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$
其中一般項（第 $k+1$ 項）可表示為：
$T_{k+1} = \binom{n}{k} a^{n-k} b^k \quad (k = 0, 1, 2, \dots, n)$
解題關鍵在於將給定函數整理成一般項形式，並透過同類項次數的合算，求出特定次項 $x^m$ 所對應的 $k$ 值與係數。

---

解題方法

已知函數 $H(x) = \left(x^2 - \frac{1}{2x}\right)^9$，可視為二項式 $(a+b)^n$ 展開，其中：
$a = x^2, \quad b = -\frac{1}{2x} = -\frac{1}{2} x^{-1}, \quad n = 9$

Step 1：寫出展開式一般項
$T_{k+1} = \binom{9}{k} \left(x^2\right)^{9-k} \left(-\frac{1}{2x}\right)^k \quad (k = 0, 1, 2, \dots, 9)$

Step 2：分離變數與係數
將 $x$ 的次方與常數係數分開整理：
$T_{k+1} = \binom{9}{k} \cdot x^{18-2k} \cdot \left(-\frac{1}{2}\right)^k \cdot x^{-k}$
$T_{k+1} = \binom{9}{k} \left(-\frac{1}{2}\right)^k x^{18-3k}$

其中 $x$ 的次方數為 $18 - 3k$，變數 $k \in \{0, 1, 2, \dots, 9\}$。

---

選項分析

• (a) 錯誤
  常數項代表 $x$ 的次方數為 $0$，令 $18 - 3k = 0 \implies k = 6$。
  將 $k = 6$ 代入一般項求係數：
  $\binom{9}{6} \left(-\frac{1}{2}\right)^6 = \binom{9}{3} \cdot \frac{1}{64} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} \cdot \frac{1}{64} = 84 \cdot \frac{1}{64} = \frac{21}{16}$
  選項聲稱常數項為 $\frac{21}{8}$，故為錯誤。

題目解析與觀念說明

8 個位元獨立且均勻地隨機生成 0 或 1，每個位元為 1 或 0 的機率皆為 $\frac{1}{2}$。

事件定義如下：

• $E_1$：第 0 位元為 1 $\implies P(E_1) = \frac{1}{2}$
• $E_2$：第 7 位元為 0 $\implies P(E_2) = \frac{1}{2}$
• $E_3$：第 3 與第 4 位元皆為 1 $\implies P(E_3) = \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$

由於各個位元相互獨立，事件 $E_1, E_2, E_3$ 亦彼此獨立。

---

選項推導與檢驗

• (a) 計算 $P(E_1 \cap E_2)$
  由獨立性：
  $P(E_1 \cap E_2) = P(E_1) \times P(E_2) = \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$
  故 (a) 正確。

核心觀念
本題主要考驗 一階非齊項線性遞迴關係式（First-order non-homogeneous linear recurrence relation） 的求法，以及 同餘（Modular arithmetic） 的整數性質判定。
主要涉及的知識點與公式如下：

1. 平移常數法（待定係數法）：針對一階非齊項遞迴式 $A_n = c A_{n-1} + k$（其中 $c \neq 1$），可設其特解為常數 $d = \frac{k}{1-c}$，並將遞迴式改寫為等比關係 $A_n - d = c(A_{n-1} - d)$。
2. 二進位次方基礎數值：考場常考 $2^n$ 的數值（如 $2^{10} = 1024$, $2^{11} = 2048$, $2^{14} = 16384$, $2^{22} = 4194304$）。
3. 模運算（同餘）：判定 $A_n$ 是否為 3 的倍數，即檢驗 $A_n \equiv 0 \pmod 3$ 是否成立。

---

解題方法
已知遞迴關係式與初始條件為：
$A_n = 2A_{n-1} + 3, \quad A_0 = 1$

步驟一：求遞迴關係式的一般項 $A_n$
將原式兩邊同時加上 $3$：
$A_n + 3 = 2A_{n-1} + 6$
$A_n + 3 = 2(A_{n-1} + 3)$

定義新數列 $B_n = A_n + 3$，則 $\{B_n\}$ 為公比等於 $2$ 的等比數列：
$B_n = 2 B_{n-1} = B_0 \cdot 2^n$

代入初始條件 $A_0 = 1$ 計算 $B_0$：
$B_0 = A_0 + 3 = 1 + 3 = 4$

故 $B_n$ 的一般項為：
$B_n = 4 \cdot 2^n = 2^{n+2}$

還原得 $A_n$ 的一般項公式為：
$A_n = B_n - 3 = 2^{n+2} - 3$

---

選項分析

• (a) $A_{20} = 732694$：錯誤
  將 $n = 20$ 代入一般項：
  $A_{20} = 2^{22} - 3 = 4,194,304 - 3 = 4,194,301$
  計算結果 $4194301 \neq 732694$，故選項 (a) 錯誤。

題目解析與霍夫曼樹（Huffman Tree）建構

1. 初始節點與頻率（按頻率由小到大排序）：
   $\text{C: 1}, \text{O: 2}, \text{U: 3}, \text{N: 4}, \text{T: 5}, \text{E: 6}, \text{R: 7}$

2. 霍夫曼樹建構過程（每次合併頻率最小的兩個節點）：

   • Step 1: 合併 $\text{C}(1)$ 與 $\text{O}(2) \rightarrow (1+2=3)$
     • 現有節點：$\text{U}(3), (3), \text{N}(4), \text{T}(5), \text{E}(6), \text{R}(7)$
   • Step 2: 合併 $\text{U}(3)$ 與 $(3) \rightarrow (3+3=6)$
     • 現有節點：$\text{N}(4), \text{T}(5), \text{E}(6), (6), \text{R}(7)$
   • Step 3: 合併 $\text{N}(4)$ 與 $\text{T}(5) \rightarrow (4+5=9)$
     • 現有節點：$\text{E}(6), (6), \text{R}(7), (9)$
   • Step 4: 合併 $\text{E}(6)$ 與 $(6) \rightarrow (6+6=12)$
     • 現有節點：$\text{R}(7), (9), (12)$
   • Step 5: 合併 $\text{R}(7)$ 與 $(9) \rightarrow (7+9=16)$
     • 現有節點：$(12), (16)$
   • Step 6: 合併 $(12)$ 與 $(16) \rightarrow (12+16=28)$（完成根節點建構）

核心觀念

本題考查離散數學與基礎代數中的有限項級數求和（Summation of Finite Series）與多項式係數分析（Polynomial Coefficient Analysis）。

主要使用的求和公式如下：

1. 連續自然數平方和公式：
   $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$
2. 常數項求和公式：
   $\sum_{k=1}^n c = c \cdot n$

---

解題方法

Step 1：表示為 Sigma 求和形式與拆項

觀察給定的級數 $H(n)$：
$H(n) = (1^2 + 3^2) + (2^2 + 3^2) + \dots + (n^2 + 3^2)$

可將第 $k$ 項表示為 $a_k = k^2 + 3^2 = k^2 + 9$，因此求和式寫為：
$H(n) = \sum_{k=1}^n (k^2 + 9)$

利用求和算符的線性性質拆開：
$H(n) = \sum_{k=1}^n k^2 + \sum_{k=1}^n 9$

Step 2：套用求和公式並展開

代入已知公式：
$H(n) = \frac{n(n+1)(2n+1)}{6} + 9n$

將分子展開：
$n(n+1)(2n+1) = n(2n^2 + 3n + 1) = 2n^3 + 3n^2 + n$

因此：
$H(n) = \frac{2n^3 + 3n^2 + n}{6} + 9n$

將分式拆解為各次方的多項式：
$H(n) = \frac{2}{6}n^3 + \frac{3}{6}n^2 + \frac{1}{6}n + 9n = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{55}{6}n$

整理得 $H(n)$ 的降冪多項式為：
$H(n) = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{55}{6}n + 0$

---

選項分析

• (a) 錯誤
  由展開式 $H(n) = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{55}{6}n$ 可知，$H(n)$ 不包含獨立常數項，即常數