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

核心觀念

1. 離散數（Discrete Number）的集域定義：在離散數學的範疇中，「離散數」指屬於離散集合（Discrete set）的數值，即整數集 $\mathbb{Z}$（或自然數集 $\mathbb{N}$）。本題環境下，變數 $x$ 與平方根式 $\sqrt{x^2 + 13}$ 的目標值均限定在整數域 $\mathbb{Z}$。
2. 算術平方根的非負性：對於任意實數 $x$，算術平方根 $\sqrt{x^2 + 13}$ 的結果必為非負數（$k \ge 0$）。
3. 丟番圖方程式（Diophantine Equation）與質數因子分解：形如 $k^2 - x^2 = C$ 的不定方程式可透過平方差公式分解為 $(k-x)(k+x) = C$。若常數 $C$ 為質數（Prime number），則其在整數集內的因數分解組合必有限且可完全列舉。

解題方法

步驟一：設定整數變數與限制條件
設 $\sqrt{x^2 + 13} = k$，其中 $k$ 為離散數（即正整數 $k \in \mathbb{Z}^+$），$x$ 為整數（$x \in \mathbb{Z}$）。
由於 $x^2 \ge 0$，可得 $x^2 + 13 \ge 13$，故 $k = \sqrt{x^2 + 13} \ge \sqrt{13} \approx 3.605$，代表 $k$ 為大於等於 $4$ 的正整數。

步驟二：代數變換與平方差分解
將等式兩邊平方：
$x^2 + 13 = k^2$

移項整理成平方差形式：
$k^2 - x^2 = 13$
$(k - x)(k + x) = 13$

步驟三：列舉質數 $13$ 的所有整數因數對
因為 $13$ 為質數，且 $k, x \in \mathbb{Z}$，故 $(k-x)$ 與 $(k+x)$ 必然為 $13$ 的整數因數。$13$ 在整數範圍內的因數分解對 $(d_1, d_2)$ 僅有以下四種組合：

1. 狀況一：$\begin{cases} k - x = 1 \\ k + x = 13 \end{cases}$
   兩式相加得 $2k = 14 \implies k = 7$。
   將 $k = 7$ 代回第 2 式可得 $7 + x = 13 \implies x = 6$。
   此時 $k = 7 > 0$，符合算術平方根之要求。

本題為聯立遞迴關係式（System of Recurrence Relations），可利用矩陣特徵值法或生成函數法求解。以下採用矩陣特徵值法進行求解與證明。

將原聯立遞迴關係式改寫為矩陣形式：
$\begin{bmatrix} x_n \\ y_n \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 2 & 3 \end{bmatrix} \begin{bmatrix} x_{n-1} \\ y_{n-1} \end{bmatrix}$

設矩陣 $A = \begin{bmatrix} 4 & 3 \\ 2 & 3 \end{bmatrix}$，則對任意 $n \ge 0$ 有：
$\begin{bmatrix} x_n \\ y_n \end{bmatrix} = A^n \begin{bmatrix} x_0 \\ y_0 \end{bmatrix} = A^n \begin{bmatrix} 7 \\ 7 \end{bmatrix}$

1. 求矩陣 $A$ 之特徵值（Eigenvalues）與特徵向量（Eigenvectors）：

特徵方程式為：
$\det(A - \lambda I) = \begin{vmatrix} 4 - \lambda & 3 \\ 2 & 3 - \lambda \end{vmatrix} = (4 - \lambda)(3 - \lambda) - 6 = \lambda^2 - 7\lambda + 6 = 0$
解得特徵值為 $\lambda_1 = 6, \lambda_2 = 1$。

• 當 $\lambda_1 = 6$ 時：
  $(A - 6I)\mathbf{v} = \begin{bmatrix} -2 & 3 \\ 2 & -3 \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \implies \mathbf{v}_1 = \begin{bmatrix} 3 \\ 2 \end{bmatrix}$

核心觀念

本題屬於離散數學與機率論中的古典機率（Classical Probability）與超幾何分布（Hypergeometric Distribution）期望值之綜合計算題。主要涉及以下核心觀念：

1. 組合數（Combination）：從 $n$ 個相異物中不放回取 $r$ 個的方法數為 $\binom{n}{r} = \frac{n!}{r!(n-r)!}$。
2. 古典機率定義：事件 $A$ 發生的機率 $P(A) = \frac{n(A)}{n(S)}$，其中 $n(S)$ 為樣本空間總數，$n(A)$ 為事件 $A$ 的可能結果數。
3. 超幾何分布與期望值（Expected Value）：
   • 若自總數 $N$ 個物品（其中包含 $K$ 個目標物）中，不放回隨機抽取 $n$ 個物品，設抽中目標物的數量為隨機變數 $x$，則 $x$ 服從超幾何分布 $H(N, K, n)$。
   • 離散型隨機變數的期望值定義為 $E(x) = \sum x \cdot P(x)$。
   • 超幾何分布的期望值公式為 $E(x) = n \times \frac{K}{N}$。

解題方法

Step 1：求水果總數 $N$

設籃子內的水果總數為 $N = 4 + y + z$。
從 $N$ 個水果中隨機不放回取出 2 個水果，樣本空間的總組合數為 $\binom{N}{2} = \frac{N(N-1)}{2}$。

已知取出 2 個皆為蘋果（$x=2$）的機率為 $\frac{1}{6}$：
$P(x=2) = \frac{\binom{4}{2}}{\binom{N}{2}} = \frac{6}{\frac{N(N-1)}{2}} = \frac{12}{N(N-1)} = \frac{1}{6}$

整理上式可得：
$N(N-1) = 72 \implies N^2 - N - 72 = 0 \implies (N-9)(N+8) = 0$

因為水果數量 $N$ 必為正整數，故取 $N = 9$。
由此可知 $y + z = N - 4 = 9 - 4 = 5$。

Step 2：求橘子數量 $y$ 與哈密瓜數量 $z$

已知取出 1 個蘋果與 1 個橘子的機率為 $\frac{1}{3}$：
從 4 個蘋果中取 1 個蘋果有 $\binom{4}{1} = 4$ 種取法；從 $y$ 個橘子中取 1 個橘子有 $\binom{y}{1} = y$ 種取法。
樣本空間總組合數為 $\binom{9}{2} = 36$。

$P(\text{1 蘋果, 1 橘子}) = \frac{\binom{4}{1} \times \binom{y}{1}}{\binom{9}{2}} = \frac{4y}{36} = \frac{y}{9} = \frac{1}{3}$

解得橘子數量：
$y = 3$

再由 $y + z = 5$，可得哈密瓜數量：
$z = 5 - 3 = 2$

Step 3：計算蘋果數量的期望值 $E(x)$

隨機變數 $x$ 表示取出的蘋果個數，其可能取值為 $0, 1, 2$。

【題目觀念】
排列組合（Counting & Combinations）、矩陣填字受限問題（Restricted Arrangements in Grid）。

【詳細解析】

1. 題目條件分析：
   欲將字母集合 $\{x, x, y, y, z, z\}$ 填入 $3 \times 2$ 網格（3 列 2 行）：
   • 列條件（Row condition）：每列包含 2 個不同字母。即每列恰由 $\{x, y\}, \{y, z\}, \{x, z\}$ 中的一種組合構成。
   • 行條件（Column condition）：每行包含 3 個不同字母。因為全域字母集只有 $x, y, z$ 各 2 個且每列 2 格，故兩行各自必須恰好為全排列 $\{x, y, z\}$。

核心觀念

DFS（深度優先搜尋）的訪問順序會受每個節點鄰接點的選擇順序影響。依圖中連線，邊為 $AC, AB, AE, BE, EF, ED, FD$。題目所說的「不連續」是指 $F$ 與 $B$ 在訪問順序中不相鄰。

解題方法

從 $A$ 開始後，$C$ 是葉節點；其餘節點 $B,E,F,D$ 形成一個連通部分。DFS 一旦從 $A$ 進入這個連通部分，就會先將其中節點全部走訪完，才回到 $A$ 訪問 $C$。因此，$C$ 只會在整個訪問順序的最前端（緊接 $A$ 之後）或最後端。

先列出 $B,E,F,D$ 部分的所有可能 DFS 訪問順序：

題意解析與說明
本題要求將命題公式 $(p \rightarrow q) \rightarrow (q \wedge r)$ 化簡為主合取範式 (Principal Conjunctive Normal Form, PCNF / Maxterm Canonical Form)，即由極大項（Maxterm）構成的合取（AND, $\wedge$）型態。

解題步驟

1. 利用邏輯等價律化簡原式為 CNF：
   由蘊涵律 $A \rightarrow B \equiv \neg A \vee B$：
   $p \rightarrow q \equiv \neg p \vee q$
   原式可化為：
   $(p \rightarrow q) \rightarrow (q \wedge r) \equiv \neg (\neg p \vee q) \vee (q \wedge r)$

   根據德摩根律（De Morgan's Laws）與雙重否定律：
   $\neg (\neg p \vee q) \equiv p \wedge \neg q$
   因此：
   $\text{原式} \equiv (p \wedge \neg q) \vee (q \wedge r)$

   根據分配律（Distributive Laws）：
   $(p \wedge \neg q) \vee (q \wedge r) \equiv (p \vee (q \wedge r)) \wedge (\neg q \vee (q \wedge r))$
   $\equiv (p \vee q) \wedge (p \vee r) \wedge (\neg q \vee q) \wedge (\neg q \vee r)$

   由於 $(\neg q \vee q) \equiv \mathbf{T}$（恆真律），可刪去該項：
   $\text{原式} \equiv (p \vee q) \wedge (p \vee r) \wedge (\neg q \vee r)$

核心觀念

本題考查離散數學中的命題邏輯（Propositional Logic）與組合計數（Combinatorial Enumeration）。

1. 組合數（Combinations）：
   從 $n$ 個相異元素中無順序地取出 $k$ 個元素，總組合數公式為：
   $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
   本題自 4 人 $\{A, B, C, D\}$ 中選取 2 人完成任務，未加入限制條件前的樣本空間總組合數為 $\binom{4}{2} = 6$ 種。

2. 蘊涵式（Implication）的邏輯語意：
   邏輯命題 $P \implies Q$（若 $P$ 則 $Q$）等價於 $\neg P \lor Q$。

   • 當前件 $P$ 為假（False）時，整個蘊涵命題自動為真（虛真，Vacuously True）。
   • 當前件 $P$ 為真（True）時，後件 $Q$ 必須為真（True），該命題才為真。

解題方法

採用窮舉法（Exhaustive Enumeration）搭配邏輯條件篩選進行推導：

步驟一：列出所有未受限的 2 人組合

由集合 $S = \{A, B, C, D\}$ 取 2 人的所有可能組合共 $\binom{4}{2} = 6$ 種：
$C_1 = \{A, B\}, \quad C_2 = \{A, C\}, \quad C_3 = \{A, D\}, \quad C_4 = \{B, C\}, \quad C_5 = \{B, D\}, \quad C_6 = \{C, D\}$

步驟二：建構題目限制條件之邏輯表示式

設 $A, B, C, D$ 分別表示該成員被選中的布林變數（1 表示選中，0 表示未選中）：

• 條件 1：「若選 A，則必選 C 或 D」
  $A \implies (C \lor D) \quad \equiv \quad \neg A \lor C \lor D$
  即：若選取了 A，則組合中不得同時缺少 C 與 D。
• 條件 2：「B 與 C 不能同時被選」
  $\neg (B \land C)$
  即：組合中不可同時包含 $\{B, C\}$。
• 條件 3：「若選 C，則必不選 D」
  $C \implies \neg D \quad \equiv \quad \neg (C \land D)$
  即：組合中不可同時包含 $\{C, D\}$。

步驟三：條件篩選與驗證

1. 由條件 2 排除組合 $\{B, C\}$。
2. 由條件 3 排除組合 $\{C, D\}$。
3. 針對剩餘組合驗證條件 1：
   • $\{A, B\}$：選取了 $A$，但 $C$ 與 $D$ 均未被選取，違反條件 1，排除。