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

核心觀念

本題涵蓋離散數學四大核心主題：

1. 鴿籠原理與邏輯推理 (Pigeonhole Principle & Logical Deduction)：命題充分條件的嚴謹性與資訊完整性判定。
2. 指數與多項式方程之整數解 (Integer Solutions of Exponential Equations)：利用代數分區討論（負整數、零、正整數）與函數成長速率比較整數解的唯一性。
3. 指數大小比較 (Comparison of Exponential Expressions)：利用常用次方夾擠（將 $5$ 與 $4$ 化為以 $2$ 為底的關係）進行手算精確估算。
4. 圖論之平面圖判定 (Planar Graphs & Kuratowski's Theorem)：歐拉公式 (Euler's Formula) 推論與庫拉托夫斯基定理對 $K_5$ 與 $K_{3,3}$ 非平面性的判定。

解題方法

本題為倒扣機制極嚴格的是非題（答錯一題倒扣 8 分），解題切入點如下：

1. 第 (1) 小題：檢視已知條件是否必然能導出結論。若能構造合理的極端反例（如總題數不足或學生集合完全不重疊），即可判定該命題為 False。
2. 第 (2) 小題：將方程式 $2^x = x^2 + x^3$ 改寫為 $2^x = x^2(1+x)$，按整數範圍分成 $x < 0$、$x = 0$、$x > 0$ 三區間討論，並利用指數成長速於多項式成長驗證解的唯一性。
3. 第 (3) 小題：尋找底數 $5$ 與 $2$ 的數量級關聯。利用 $5^3 = 125 < 128 = 2^7$，將 $5^{4321}$ 與 $4^{5321} = 2^{10642}$ 統一化為以 $2$ 為底的指數進行大小比較。
4. 第 (4) 小題：引用圖論經典定理與歐拉公式推論 $e \le 3v - 6$ 及 $e \le 2v - 4$，分別驗證 $K_5$ 與 $K_{3,3}$ 的非平面性。

選項分析

(1) 命題分析：(F)

題目原文：Observations showed that at least 100 students successfully got correct answers in eight questions, and 200 students successfully answered the rest questions. We concluded that some students got at least 11 questions right.

• 詳細推導與證明：
  此命題為錯誤 (False)。
  結論「必有學生答對至少 11 題」無法由已知條件必然成立，反例說明如下：
  1. 總題數未限定：若該次考試總題數僅有 10 題，則「其餘題目 (the rest questions)」只有 $10 - 8 = 2$ 題。此時第一群 100 名學生每人答對 8 題，第二群 200 名學生每人答對 2 題，全校無任何人答對 11 題以上。
  2. 學生集合不必然重疊：即使總題數為 15 題（前 8 題與其餘 7 題），答對前 8 題的 100 名學生與答對其餘 7 題的 200 名學生可以是完全不同的兩群人。第一群學生每人僅答對 8 題，第二群學生每人僅答對 7 題，兩群學生皆未達到 11 題。
     因此，該推理在邏輯上不成立。

(2) 命題分析：(T)

題目原文：There is only one integer solution to $2^x = x^2 + x^3$.

• 詳細推導與證明：
  此命題為正確 (True)。
  考慮方程式：
  $2^x = x^2(1+x)$
  將 $x \in \mathbb{Z}$ 分區討論：

  • 情況一：$x < 0$（負整數）
    設 $x = -k$，其中 $k \ge 1$ 為正整數。

    • 左式 (LHS)：$2^{-k} = \frac{1}{2^k} > 0$（恆為正分數）。
    • 右式 (RHS)：$(-k)^2 (1-k) = k^2(1-k)$。
      • 當 $k = 1$ ($x = -1$) 時，$\text{RHS} = 1^2(1-1) = 0 \neq \text{LHS}$。
      • 當 $k \ge 2$ ($x \le -2$) 時，$1-k \le -1$，故 $\text{RHS} = k^2(1-k) \le -4 < 0$。
        左式為正數而右式小於等於 $0$，故負整數範圍內無解。

  • 情況二：$x = 0$

    • $\text{LHS} = 2^0 = 1$。
    • $\text{RHS} = 0^2(1+0) = 0$。
      因 $1 \neq 0$，故 $x = 0$ 非解。

核心觀念

地圖著色要求共用邊界線段的區域使用不同顏色；只在一個點相接的區域不算相鄰。要證明最少顏色數，需先給出合法著色，再證明更少的顏色不可能。

解題方法

依原圖，外圍的 $S_1$ 與四個角落區域相鄰；內部的 $S_4、S_5、S_6$ 由上而下排列。沿著共用邊界交替著色，可用兩種顏色：

依圖檢查，每一對共用邊界線段的區域顏色皆不同，因此這是合法著色。

最少顏色證明

核心觀念

子集合 $S\subseteq L$ 是 $L$ 的子格，必須對原格 $L$ 的交與聯封閉：任取 $u,v\in S$，皆須滿足

其中，$u\wedge_L v$ 是最大共同下界，$u\vee_L v$ 是最小共同上界。

若 $u\preceq v$，則

兩個結果自然都在 $S$ 中。因此，判斷子格時只需檢查集合內的不可比較元素對。

解題方法

依原卷的 Hasse 圖，由下往上讀取：$a,b$ 覆蓋 $x$；$c,d$ 覆蓋 $a$；$c,e$ 覆蓋 $b$；$y$ 覆蓋 $c,d,e$。其中 $x$ 是最小元素，$y$ 是最大元素，所有交、聯都依此原格計算。

（一）$L_1=\{x,a,b,y\}$：不是子格

$a,b$ 不可比較。它們的共同上界為 $c,y$，且 $c\preceq y$，所以

但 $c\notin L_1$，因此 $L_1$ 對聯不封閉，不是子格。雖然 $a\wedge_L b=x\in L_1$，仍不足以滿足子格條件。

（二）$L_2=\{x,a,e,y\}$：是子格

$x$ 與 $y$ 分別是最小、最大元素，因此唯一需要檢查的不可比較元素對是 $a,e$。

核心觀念

Kruskal 演算法將所有邊依權重由小到大排列，逐邊加入生成樹；若加入某邊會形成環，就跳過。對含有 $n$ 個頂點的連通圖，最小生成樹會有 $n-1$ 條邊。

依原卷掃描圖，頂點標示為 $0,1,2,3,4,5$，共六個頂點；圖上的邊與權重為 $(0,1):10$、$(0,2):20$、$(1,4):10$、$(1,3):50$、$(2,3):20$、$(2,4):33$、$(3,4):20$、$(3,5):2$、$(4,5):1$。這與題目文字所附的五頂點邊表不同，以下依原卷圖形作答。

解題方法

依權重由小到大檢查各邊：

核心觀念

把二分圖中的配對視為匹配：匹配內任兩條邊都不能共用端點。最大匹配是邊數最多的匹配；若每個頂點都恰好配對一次，則稱為完美匹配。

解題方法

依原卷圖讀得左右頂點集合為 $L=\{1,2,3,4,5\}$、$R=\{a,b,c,d,e\}$，鄰接關係為：

取以下五條邊作為匹配：

已知 $x$ 與 $y$ 皆為質數（Prime numbers），且滿足方程式：
$x^y + y^x = xy$

證明與推導過程

1. 比較大小關係：
   因為 $x$ 與 $y$ 皆為質數，所以 $x \ge 2$ 且 $y \ge 2$。
   根據指數函數與線性函數的增長率比較，當 $x \ge 2$ 時：
   $x^y > x$
   同理，當 $y \ge 2$ 時：
   $y^x > y$

核心觀念

本題屬於離散數學中**計數原理（Counting Principles）與組合學（Combinatorics）**的基本應用題，主要考查以下重點概念：

1. 組合數（Combination）：從 $n$ 個相異物件中不考慮順序取 $k$ 個物件的組合數，公式為：
   $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$
2. 乘法原理（Multiplication Principle）：若一任務可拆解為連續兩個步驟，第一步驟有 $a$ 種可能，第二步驟有 $b$ 種可能，則完成該任務共有 $a \times b$ 種方法。
3. 加法原理（Addition Principle）：若一任務可分為若干互相排斥（Disjoint）的類別，則完成該任務的總方法數為各類別方法數之和。
4. 反面扣除法／排容原理（Complement Method）：用全部可能的選擇總數，減去不符合條件（未同時包含兩種球）的選擇數。

解題方法

本題給定 5 顆棒球與 4 顆籃球，球的總數為 $5 + 4 = 9$ 顆。需從中選出 3 顆球，且限制選出的 3 顆球中必須至少包含一顆棒球與一顆籃球。

以下提供兩種標準且嚴謹的推導方法：

推導方法一：正面分類討論法（Direct Method）

選取 3 顆球且滿足「至少 1 顆棒球且至少 1 顆籃球」的組合只有以下兩種互斥情況：

1. 情況一：選取 2 顆棒球與 1 顆籃球

   • 從 5 顆棒球中選取 2 顆：$C(5, 2) = \frac{5 \times 4}{2 \times 1} = 10$ 種方法。
   • 從 4 顆籃球中選取 1 顆：$C(4, 1) = 4$ 種方法。
   • 由乘法原理，此情況共有 $C(5, 2) \times C(4, 1) = 10 \times 4 = 40$ 種選擇。

2. 情況二：選取 1 顆棒球與 2 顆籃球

   • 從 5 顆棒球中選取 1 顆：$C(5, 1) = 5$ 種方法。
   • 從 4 顆籃球中選取 2 顆：$C(4, 2) = \frac{4 \times 3}{2 \times 1} = 6$ 種方法。
   • 由乘法原理，此情況共有 $C(5, 1) \times C(4, 2) = 5 \times 6 = 30$ 種選擇。

根據加法原理，符合條件的總選擇數為：
$40 + 30 = 70$

推導方法二：反面扣除法（Complement Method）

計算任選 3 顆球的任意組合總數，再扣除「全選棒球」及「全選籃球」這兩種不合條件的情況：

1. 任選 3 顆球的總方法數：
   $C(9, 3) = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84$