111 年 國立中山大學資訊工程學系資訊安全碩士班《離散數學與演算法》

核心觀念

本題屬於代數學（Abstract Algebra）中的「環論」（Ring Theory）基礎證明題，主要考查以下定義與公理：

1. 具單位元的環（Ring with Unity）：若環 $R$ 中存在一個乘法單位元 $1_R \in R$，使得對所有 $x \in R$，皆滿足 $x \cdot 1_R = 1_R \cdot x = x$。
2. 可逆元（Unit）與乘法反元素（Multiplicative Inverse）：在具單位元 $1_R$ 的環 $R$ 中，若元素 $u \in R$ 存在另一個元素 $v \in R$ 滿足 $u \cdot v = v \cdot u = 1_R$，則稱 $u$ 為環 $R$ 的可逆元（Unit），且稱 $v$ 為 $u$ 的乘法反元素，記作 $u^{-1} = v$。
3. 乘法結合律（Associativity of Multiplication）：環 $R$ 的乘法運算對任意三元素 $x, y, z \in R$ 皆滿足 $(x \cdot y) \cdot z = x \cdot (y \cdot z)$。

解題方法

要證明 $ab$ 為環 $R$ 的可逆元（Unit），必須根據定義在 $R$ 中找到一個元素 $x$，使得 $(ab)x = x(ab) = 1_R$。若此元素存在，則 $ab$ 即為可逆元，且其反元素 $(ab)^{-1} = x$。

詳細推導步驟：

1. 已知條件轉化：
   因為 $a, b$ 皆為 $R$ 的可逆元，故各自存在乘法反元素 $a^{-1}, b^{-1} \in R$，滿足：
   $a a^{-1} = a^{-1} a = 1_R$
   $b b^{-1} = b^{-1} b = 1_R$

2. 構造候選反元素並驗證右可逆性（Right Inverse）：
   取元素 $x = b^{-1} a^{-1} \in R$，計算 $(ab)x$：
   $(ab)(b^{-1}a^{-1}) = a (b b^{-1}) a^{-1} \quad (\text{依據乘法結合律})$

先將 36 本相異書任意排列，共有 $36!$ 種。再於相鄰書本間的 35 個空隙中選 4 個作為五層書架的分界。

因每層至少放 2 本書，相當於正整數解

核心觀念

• 鴿籠原理（Pigeonhole Principle）：若將 $n$ 個物件（鴿子）放入 $m$ 個類別（鴿籠）中，且 $n > m$，則至少有一個類別包含 2 個或以上的物件。
• 組合計數與極值範圍：
  • 設集合 $S$ 的元素個數為 $|S| = k$，則大小為 $r$ 的子集數量為組合數 $\binom{k}{r}$。
  • 子集元素和的上界由集合內可能的最大相異正整數決定。

解題方法

證明目標：證明存在兩個不同的非空子集 $A, B \subseteq S$，使得 $\sum_{x \in A} x = \sum_{y \in B} y$。

步驟一：選定適當的子集族作為「鴿子」
設 $S = \{a_1, a_2, a_3, a_4, a_5, a_6\}$ 為由 6 個相異正整數組成的集合，且最大元素小於等於 14。
考慮 $S$ 中所有元素個數為 1、2 或 3 的子集：

• 大小為 1 的子集數量：$\binom{6}{1} = 6$
• 大小為 2 的子集數量：$\binom{6}{2} = 15$
• 大小為 3 的子集數量：$\binom{6}{3} = 20$

將這些子集作為「鴿子」，鴿子總數 $n$ 為：
$n = \binom{6}{1} + \binom{6}{2} + \binom{6}{3} = 6 + 15 + 20 = 41$

步驟二：估算子集元素和的範圍作為「鴿籠」
對於上述任意大小不超過 3 的子集 $A \subseteq S$，其元素和 $\sum_{x \in A} x$ 的可能範圍計算如下：

1. 最小可能和：當子集僅包含 $S$ 中最小的正整數時取得，因為元素皆為正整數，故和至少為 $1$。
2. 最大可能和：當子集包含 $S$ 中最大的 3 個整數時取得。

核心觀念

本題屬於離散數學中組合數學（Combinatorics）的經典題型——重複組合（Combination with Repetition / $H$-combinations） 與 非負整數解個數問題。

1. 物件與容器特性識別：
   • 公司採購的 22 台自動販賣機視為相同物（Indistinguishable Objects）。
   • 6 個部門（sub-divisions）為相異容器（Distinguishable Bins）。
2. 重複組合公式：
   將 $k$ 個相同物分配給 $n$ 個相異對象，允許有人沒分到（即非負整數解 $y_i \ge 0$），其分配方法總數為：
   $H^n_k = \binom{n+k-1}{k} = \binom{n+k-1}{n-1}$
3. 限制條件轉換（預先分配法）：
   當題目規定每個對象至少需分得 $m$ 個物品（$x_i \ge m$）時，可先將每人所需的 $m$ 個物品預先扣除分配，將正整數或有限制條件的方程式轉化為標準的「非負整數解」問題。

解題方法

步驟一：建立數學方程式

設 $x_i$ 表示第 $i$ 個部門分得的自動販賣機數量（其中 $i = 1, 2, 3, 4, 5, 6$）。
根據題意，總台數為 22 台，且每個部門至少分配到 2 台，可列出不定方程式與變數限制條件：
$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 22$
$\text{限制條件：} x_i \ge 2 \quad (\forall i \in \{1, 2, 3, 4, 5, 6\})$

步驟二：變數變換（預先分配）

先預先給 6 個部門各分發 2 台自動販賣機，共耗去：
$6 \times 2 = 12 \text{ 台}$
令變數 $y_i = x_i - 2$（代表各部門預分配後，額外獲得的販賣機數量），則 $y_i \ge 0$。代入原式進行變換：
$(y_1 + 2) + (y_2 + 2) + (y_3 + 2) + (y_4 + 2) + (y_5 + 2) + (y_6 + 2) = 22$
$y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 22 - 12 = 10$
$\text{其中 } y_i \ge 0 \quad (i = 1, 2, 3, 4, 5, 6)$

步驟三：代入重複組合公式計算

求解方程式 $y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 10$ 的非負整數解個數，即為將 10 個相同的剩餘販賣機分配給 6 個相異部門的方法數 $H^6_{10}$：
$H^6_{10} = \binom{6 + 10 - 1}{10} = \binom{15}{10} = \binom{15}{5}$

由遞迴式

及 $p_0=0,\ p_1=1$，得

乘積 $stuvwxyz$ 共有 $8$ 個因子。完全括號化的方式數為第 $7$ 個卡塔蘭數：

核心觀念

本題屬於離散數學中**組合數學（Combinatorics）與鴿籠原理（Pigeonhole Principle / 平均值原理）**的典型應用。
關鍵觀念包含：

1. 環狀排列與重複計數（Double Counting / Summation Trick）：將 $1$ 至 $16$ 共 $16$ 個數字排列於圓環上，每一個位置的數字恰好會被包覆在 $3$ 組相鄰的三數組合中。因此，所有連續三數之和的總和，等於 $1$ 至 $16$ 總和的 $3$ 倍。
2. 廣義鴿籠原理 / 平均值原理（Generalized Pigeonhole Principle / Average Principle）：若 $n$ 個實數的平均值為 $\mu$，則其中必定存在至少一個數值大於或等於 $\mu$（即 $\max(S_i) \ge \mu$）。

解題方法

本題採用**鴿籠原理（或反證法）**進行嚴謹證明與推導：

步驟一：定義變數與建立模型

設 $1$ 到 $16$ 的任意一種環狀排列順序依序為 $x_1, x_2, x_3, \dots, x_{16}$，其中 $(x_1, x_2, \dots, x_{16})$ 為集合 $\{1, 2, \dots, 16\}$ 的一個置換（Permutation）。
由於數字排成圓環，定義指標 modulo $16$（即 $x_{17} = x_1, x_{18} = x_2$）。

設圓盤上所有的連續三個數字之和為 $S_i$：
$S_i = x_i + x_{i+1} + x_{i+2}, \quad \forall i \in \{1, 2, \dots, 16\}$
圓盤上共有 $16$ 組這樣的連續三數之和（$S_1, S_2, \dots, S_{16}$）。

步驟二：計算所有三數之和的總和

將這 $16$ 組連續三數之和全部相加：
$\sum_{i=1}^{16} S_i = \sum_{i=1}^{16} (x_i + x_{i+1} + x_{i+2})$

因為每一個數字 $x_k$ 恰好會在 $S_{k-2}, S_{k-1}, S_k$ 這三組連續三數中出現各一次，所以總和相當於 $1$ 到 $16$ 的總和乘以 $3$：
$\sum_{i=1}^{16} S_i = 3 \times \sum_{k=1}^{16} x_k$

計算 $1$ 到 $16$ 的等差級數和：
$\sum_{k=1}^{16} x_k = \frac{16 \times (1 + 16)}{2} = 136$

因此，$16$ 組連續三數之和的總和為：
$\sum_{i=1}^{16} S_i = 3 \times 136 = 408$

核心觀念

堆積排序（Heapsort）是一種基於比較（Comparison-based）的排序演算法，利用**最大堆積（Max-Heap）**這項資料結構來達成高效排序。

1. 最大堆積（Max-Heap）之定義：

   • 結構上為一棵完全二元樹（Complete Binary Tree），通常以一維陣列 $A$ 儲存。對於索引為 $i$ 的節點（索引從 $1$ 開始）：
     • 父節點索引：$\text{PARENT}(i) = \lfloor i / 2 \rfloor$
     • 左子節點索引：$\text{LEFT}(i) = 2i$
     • 右子節點索引：$\text{RIGHT}(i) = 2i + 1$
   • 滿足最大堆積性質（Max-Heap Property）：對所有非根節點 $i$，恆滿足 $A[\text{PARENT}(i)] \ge A[i]$。因此，堆積的根節點 $A[1]$ 必定儲存整個堆積中的最大值。

2. Heapsort 演算法的三大核心元件：

   • Max-Heapify：維護最大堆積性質。當某節點的左右子樹皆符合 Max-Heap，但該節點本身可能破壞 Max-Heap 性質時，將該節點下沈（Sift-down）至合適位置。
   • Build-Max-Heap：將任意未排序的長度為 $n$ 之陣列，由下而上（Bottom-up）轉化為 Max-Heap。
   • Heapsort：先建立 Max-Heap，再重複將根節點（最大值）與目前堆積末端元素交換，將堆積大小減 $1$，並對新根節點執行 Max-Heapify，直到所有元素排序完成。

解題方法

一、 Heapsort 演算法表達（Pseudocode）

1. 維護最大堆積：Max-Heapify(A, i, heap_size)

Max-Heapify(A, i, heap_size):
    l = LEFT(i)
    r = RIGHT(i)
    largest = i
    
    if l <= heap_size and A[l] > A[largest]:
        largest = l
    if r <= heap_size and A[r] > A[largest]:
        largest = r
        
    if largest != i:
        swap(A[i], A[largest])
        Max-Heapify(A, largest, heap_size)

2. 建構最大堆積：Build-Max-Heap(A, n)

因為葉節點（索引為 $\lfloor n/2 \rfloor + 1$ 到 $n$）本身天然滿足 Heap 性質，故只需從最後一個非葉節點 $\lfloor n/2 \rfloor$ 開始往回至根節點 $1$ 進行 Max-Heapify。

Build-Max-Heap(A, n):
    heap_size = n
    for i = floor(n / 2) down to 1:
        Max-Heapify(A, i, heap_size)

3. 堆積排序主程式：Heapsort(A, n)

Heapsort(A, n):
    Build-Max-Heap(A, n)
    heap_size = n
    for i = n down to 2:
        swap(A[1], A[i])          // 將最大值移至陣列末端
        heap_size = heap_size - 1 // 排除已排序的末端元素
        Max-Heapify(A, 1, heap_size) // 恢復根節點之 Max-Heap 性質

二、 時間複雜度詳細分析

Heapsort 的整體時間複雜度由 Build-Max-Heap 與排序主迴圈兩部分構成。

1. Max-Heapify 之時間複雜度分析

• 在高度為 $h$ 的節點上執行 Max-Heapify，最壞情況下需要沿著樹枝一路下沈至葉節點。
• 每次遞迴比較與交換耗時 $O(1)$，最多執行 $h$ 次遞迴。
• 一棵包含 $k$ 個節點的堆積，樹高為 $h = \lfloor \log_2 k \rfloor$。
• 結論：對高度為 $h$ 之節點執行 Max-Heapify 的時間複雜度為 $O(h)$；對大小為 $k$ 之堆積根節點執行 Max-Heapify，時間複雜度為 $O(\log k)$。

2. Build-Max-Heap 之時間複雜度詳細推導

直觀分析可能會認為：執行 $\lfloor n/2 \rfloor$ 次 Max-Heapify，每次耗時 $O(\log n)$，故總時間為 $O(n \log n)$。但這是過度鬆散的上界。精確的鬆緊上界分析如下：

• 樹高與節點數量的關係：
  在一棵大小為 $n$ 的完全二元樹中，高度為 $h$ 的節點數量最多為：
  $n_h = \left\lceil \frac{n}{2^{h+1}} \right\rceil$
  樹的最大高度為 $H = \lfloor \log_2 n \rfloor$。

• 總時間代價求和：
  將所有高度的節點執行 Max-Heapify 的代價加總：
  $T_{\text{build}}(n) = \sum_{h=0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h) \le O\left( n \sum_{h=0}^{\infty} \frac{h}{2^h} \right)$

• 無窮級數求和推導：

完全 $n$ 叉樹中，每個內部節點至多有 $n$ 個子節點。根節點位於第 $0$ 層，因此第 $i$ 層至多有 $n^i$ 個節點。葉節點皆位於第 $h$ 層，故

兩邊取以 $n$ 為底的對數（$n>1$）：

核心觀念

本題考查**動態規劃（Dynamic Programming, DP）**在經典演算法——**0/1 背包問題（0-1 Knapsack Problem）**上的應用與複雜度分析。

1. 0/1 特性與最佳子結構（Optimal Substructure）：
   在 0/1 背包問題中，每個物品 $i$（重量 $w_i$、效益值 $b_i$）只有「放入背包（取值 1）」或「不放入背包（取值 0）」兩種選擇，物品不可分割。當考慮前 $i$ 個物品在背包容量為 $w$ 下的最佳解時：

   • 若選擇放入第 $i$ 個物品，則問題歸約為「前 $i-1$ 個物品在容量 $w - w_i$ 下的最佳解」加上 $b_i$；
   • 若選擇不放入第 $i$ 個物品，則歸約為「前 $i-1$ 個物品在容量 $w$ 下的最佳解」。
     此性質符合最佳子結構。

2. 重疊子問題（Overlapping Subproblems）：
   若採用單純遞迴求解，許多相同的容量與物品組合會被重複計算。動態規劃透過建立表格（DP Table）記錄已求解的子問題解答，可將時間複雜度降至偽多項式時間。

解題方法

1. 狀態定義（State Definition）

設 $DP[i][w]$ 表示從前 $i$ 個物品（物品編號 $1, 2, \dots, n$）中進行選擇，在背包總容量限制為 $w$（其中 $0 \le w \le W$）時，所能獲得的最大總效益值（Maximum Total Benefit Value）。

2. 狀態轉移方程式（State Transition Equation）

考慮第 $i$ 個物品（重量 $w_i$，效益值 $b_i$），其決策推導如下：

• 容量不足（$w < w_i$）：無法放入第 $i$ 個物品，最大效益延續前 $i-1$ 個物品在容量 $w$ 時的最佳解：
  $DP[i][w] = DP[i-1][w]$
• 容量足夠（$w \ge w_i$）：可選擇放或不放第 $i$ 個物品，取效益較大者：
  • 不放第 $i$ 個物品：效益為 $DP[i-1][w]$
  • 放入第 $i$ 個物品：效益為 $b_i + DP[i-1][w - w_i]$

綜合得狀態轉移方程式：
$DP[i][w] = \begin{cases} DP[i-1][w], & \text{if } w < w_i \\ \max\Big(DP[i-1][w], \; b_i + DP[i-1][w - w_i]\Big), & \text{if } w \ge w_i \end{cases}$

3. 邊界條件（Base Cases）

• 當沒有物品可選時（$i = 0$），效益為 $0$：
  $DP[0][w] = 0, \quad \forall \; 0 \le w \le W$
• 當背包容量為 $0$ 時（$w = 0$），無法裝入任何物品，效益為 $0$：
  $DP[i][0] = 0, \quad \forall \; 0 \le i \le n$

4. 演算法步驟與虛擬碼（Pseudocode）

Algorithm 01Knapsack(n, W, w, b):
    Input: Number of items n, maximum capacity W, weight array w[1..n], benefit array b[1..n]
    Output: Maximum total benefit value

    // 1. 初始化 DP 表格
    Declare DP[0..n][0..W]
    for w from 0 to W do:
        DP[0][w] = 0
    for i from 0 to n do:
        DP[i][0] = 0

    // 2. 填表（由小到大求解子問題）
    for i from 1 to n do:
        for w from 1 to W do:
            if w < w[i] then:
                DP[i][w] = DP[i-1][w]
            else:
                DP[i][w] = max(DP[i-1][w], b[i] + DP[i-1][w - w[i]])

    // 3. 回傳前 n 個物品在容量 W 下的最大效益
    return DP[n][W]