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

核心觀念

本題屬於離散數學中的初等數論（Elementary Number Theory）與二進位指數方程式（Exponential Diophantine Equations）。
主要考驗的觀念與定理包含：

1. 同底數冪次轉換：利用指數律將不同底數化為以 2 為底的標準型態：$4^y = (2^2)^y = 2^{2y}$ 與 $8^z = (2^3)^z = 2^{3z}$。
2. 算術基本定理與偶因數提取法：利用 2 的次方與奇數因數的特性，配合質因數分解唯一性（二進位表示唯一性），推導出三個指數項的唯一數值集合。
3. 整除性與變數約束：變數 $x, y, z \in \mathbb{N}$（自然數），指數分別為 $x$（任意自然數）、$2y$（必須為偶數）、$3z$（必須為 3 的倍數）。

解題方法

步驟一：將方程式統一改寫為以 2 為底的指數形式
原式為：
$2^x + 4^y + 8^z = 328$
利用指數律 $4^y = 2^{2y}$ 與 $8^z = 2^{3z}$，將原式改寫為：
$2^x + 2^{2y} + 2^{3z} = 328$

步驟二：證明 328 分解為三個 2 的冪次和之指數集合必為 $\{3, 6, 8\}$
設三個指數分別為 $A, B, C$（即 $\{A, B, C\} = \{x, 2y, 3z\}$），不失一般性假設 $A \le B \le C$。方程式變為：
$2^A + 2^B + 2^C = 328$

1. 當 $A < B < C$ 時：
   提出 $2^A$ 可得：
   $2^A (1 + 2^{B-A} + 2^{C-A}) = 328 = 2^3 \times 41$
   由於 $B-A > 0$ 且 $C-A > 0$，故括號內 $(1 + 2^{B-A} + 2^{C-A})$ 必為奇數。
   根據算術基本定理，等式兩邊偶因數部分（2 的次方）必須相等，因此：
   $2^A = 2^3 \implies A = 3$
   將 $A = 3$ 代回等式：
   $1 + 2^{B-3} + 2^{C-3} = 41 \implies 2^{B-3} + 2^{C-3} = 40$
   提出 $2^{B-3}$（其中 $B-3 < C-3$）：
   $2^{B-3} (1 + 2^{C-B}) = 40 = 2^3 \times 5$
   由於 $C-B > 0$，$(1 + 2^{C-B})$ 為奇數，故：
   $2^{B-3} = 2^3 \implies B - 3 = 3 \implies B = 6$
   代回可得：
   $1 + 2^{C-6} = 5 \implies 2^{C-6} = 4 = 2^2 \implies C = 8$
   故指數集合為 $\{3, 6, 8\}$。

2. 當存在指數相同的情況時：

   • 情況 2-1（$A = B < C$）：$2 \cdot 2^A + 2^C = 2^{A+1}(1 + 2^{C-A-1}) = 328 = 2^3 \times 41 \implies A+1 = 3 \implies A=2$。代回得 $1 + 2^{C-3} = 41 \implies 2^{C-3} = 40$，無整數解。
   • 情況 2-2（$A < B = C$）：$2^A + 2 \cdot 2^B = 2^A(1 + 2^{B+1-A}) = 328 = 2^3 \times 41 \implies A = 3$。代回得 $1 + 2^{B-2} = 41 \implies 2^{B-2} = 40$，無整數解。

Ans: $\pm 67 \pm 82i$ 與 $\pm 82 \pm 67i$（共 8 個）

觀念與公式

1. 高斯整數環 $\mathbb{Z}[i]$：範數（Norm）定義為 $N(a+bi) = a^2 + b^2$。
2. 不可約元素（Irreducible Elements / Gaussian Primes）：若 $N(\alpha) = p$ 為實質質數（Real Prime），則 $\alpha$ 在 $\mathbb{Z}[i]$ 中必為不可約元素。
3. 質數在 $\mathbb{Z}[i]$ 中的分解性質：
   • 若實質質數 $p \equiv 1 \pmod 4$，則 $p$ 可唯一表示為兩個平方數之和 $a^2 + b^2$（不計符號與順序），且 $p = (a+bi)(a-bi)$，其中 $a \pm bi$ 皆為不可約元素。

推導過程

1. 檢查 11213 的素性與特徵：
   題目給定 $11213 = 67^2 + 82^2$。
   • $67^2 + 82^2 = 4489 + 6724 = 11213$。
   • $11213 \equiv 1 \pmod 4$。
   • 經檢驗 11213 為實質質數。

核心觀念

題目要從所有白色格子中選出 6 格，未要求每列或每行最多選幾格，因此使用組合公式：從 $n$ 個不同物件中選 $r$ 個，選取順序不影響結果，共有 $\binom{n}{r}$ 種。

解題方法

依圖逐列計算白色格子數：

• 第 1 列：5 格
• 第 2 列：3 格
• 第 3 列：4 格
• 第 4 至第 6 列：每列 5 格，共 15 格

Ans: $a_n = 3456 \cdot \frac{1}{n!} + n! \sum_{k=1}^{n} \frac{2^k}{k!}$

詳解

給定遞迴關係式：
$a_n = \frac{1}{n} a_{n-1} + 2^n \quad (n \ge 1, \ a_0 = 3456)$

步驟一：遞迴關係式同乘 $n!$ 化簡

兩邊同乘以 $n!$：
$n! \cdot a_n = (n-1)! \cdot a_{n-1} + n! \cdot 2^n$

令 $b_n = n! \cdot a_n$，則 $b_0 = 0! \cdot a_0 = 3456$。原式可改寫為：
$b_n = b_{n-1} + n! \cdot 2^n$

觀念說明

色多項式 (Chromatic Polynomial) $P(G, \lambda)$ 表示將圖 $G$ 的頂點以 $\lambda$ 種顏色著色，使得任意相鄰頂點顏色皆不相同的著色方法總數。

在求解給定圖 $G$ 的色多項式時，常用的經典方法為刪減-收縮定理 (Deletion-Contraction Theorem)：
$P(G, \lambda) = P(G - e, \lambda) - P(G \cdot e, \lambda)$
其中 $G - e$ 表示從圖 $G$ 中刪除邊 $e$，$G \cdot e$ 表示將邊 $e$ 的兩個端點收縮（合併）為單一頂點。

解題步驟

由於題目考卷印刷未附圖形 $G$ 之具體結構圖檔，以下提供兩類研究所考試最常出現之圖形推導範例：

情況一：若圖 $G$ 為 $n$ 個頂點的樹狀圖 (Tree, $T_n$)

1. 任意選定一根頂點，其有 $\lambda$ 種顏色可選擇。
2. 剩餘的 $n-1$ 個頂點，每個頂點只需要與其父節點顏色不同即可，故各有 $\lambda - 1$ 種顏色選擇。
3. 依乘法原理，其色多項式為：