112 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《離散數學》

核心觀念
本題屬於「貨幣系統」或「金幣問題」的典型應用，核心在於 整數線性組合（非負整數係數）與 Frobenius coin problem。

• 若一組正整數集合 $S=\{v_1,\dots ,v_n\}$ 的最大公因數 $\gcd(S)=1$，則存在只有限個正整數無法由 $S$ 表示；最大無法表示的數稱為 Frobenius 數。
• 本題要求 所有 $\ge5$ 的正整數皆可表示，等價於「Frobenius 數 ≤4」。
• 因所有面額 $v_i\ge5$，若 $5\le k\le9$，任何兩個面額的和至少為 $10$，因此 $k$ 必須本身就是某個面額。

---

解題方法

1. 必要性證明

   • 假設 $S$ 能表示所有 $\ge5$ 的正整數。
   • 取任意 $k\in\{5,6,7,8,9\}$。若 $k\notin S$，則要用兩個或以上面額相加得到 $k$，最小的可能和為 $5+5=10>k$，矛盾。
   • 故 $S$ 必須至少包含 5、6、7、8、9 這五個面額。因此 $n\ge5$。

2. 充分性證明（歸納法）

   • 設 $S=\{5,6,7,8,9\}$。
   • 基礎情形：$5,6,7,8,9$ 均為集合中的面額，顯然可表示。
   • 歸納假設：任意 $m$ ($5\le m\le t$) 可由 $S$ 表示，其中 $t\ge9$。
   • 歸納步驟：考慮 $t+1\;(≥10)$。寫 $t+1 = 5 + (t-4)$。因 $t-4\ge5$，依歸納假設 $t-4$ 可由 $S$ 表示，於是 $t+1$ 亦可表示。
   • 由此歸納可得 所有 $m\ge5$ 均可由 $S$ 表示。

3. 最小化 $n$

   • 由第一步已證 $n\ge5$，而第二步展示 $n=5$ 已足夠。因此 最小值 $n_{\min}=5$。

核心觀念

本題的核心觀念為弗羅貝尼烏斯硬幣問題（Coin Problem / Frobenius Problem）、貝祖定理（Bézout's Identity）以及強數學歸納法（Strong Mathematical Induction）。

1. 貨幣組合問題（Frobenius Coin Problem）：
   給定 $n$ 個互質的正整數面額 $v_1, v_2, \ldots, v_n$，其能以非負整數係數線性組合出的金額集合為：

   $$S = \{ a_1 v_1 + a_2 v_2 + \cdots + a_n v_n \mid a_i \in \mathbb{N} \cup \{0\} \}$$

   若 $\gcd(v_1, v_2, \ldots, v_n) = 1$，則必存在一個最大的無法湊出的整數（Frobenius Number，記為 $g$），使得所有大於等於 $g + 1$ 的整數皆可被表出。

2. 雙面額的西爾維斯特公式（Sylvester's Theorem, 1884）：
   若只有兩種面額 $v_1, v_2$ 且 $\gcd(v_1, v_2) = 1$，則無法湊出的最大金額為：

   $$g(v_1, v_2) = v_1 v_2 - v_1 - v_2$$

   即從金額 $v_1 v_2 - v_1 - v_2 + 1 = (v_1 - 1)(v_2 - 1)$ 開始，所有大於等於該值的整數均可由 $v_1$ 與 $v_2$ 的非負整數線性組合構成。

3. 單一面額的不可能性：
   若只發行 $1$ 種面額 $v_1$（其中 $v_1 \ge 5$），則能湊出的金額只有 $v_1$ 的倍數 $\{v_1, 2v_1, 3v_1, \ldots\}$，無法覆蓋所有大於等於 $c$ 的連續整數。

---

解題方法與完整證明

題目要求：

• 面額 $v_i$ 必須為整數且 $v_i \ge 5$。
• 必須能夠湊出所有金額 $x \ge c$（其中 $c \ge 50$ 為給定的整數常數）。
• 求最小的面額種類數 $n$。

步驟 1：證明 $n = 1$ 不可能

若僅發行 $1$ 種面額 $v_1$（$v_1 \ge 5$），則可支付的金額集合為：

$$S_1 = \{ k \cdot v_1 \mid k \in \mathbb{N} \}$$

若要覆蓋所有整數 $x \ge c$，則集合 $S_1$ 必須包含 $c, c+1, c+2, \ldots$ 等連續整數。然而，相鄰兩個可支付金額的差至少為 $v_1 \ge 5 > 1$。例如金額 $k \cdot v_1 + 1$（當 $k \cdot v_1 \ge c$ 時）顯然無法被整除，故不可能僅用 $1$ 種面額。因此，必有 $n \ge 2$。

步驟 2：證明 $n = 2$ 恆成立（構造法）

若發行 $2$ 種面額 $v_1$ 與 $v_2$（取 $5 \le v_1 < v_2$），且選取互質的相鄰整數：

$$\gcd(v_1, v_2) = 1$$

根據西爾維斯特公式（Sylvester's Theorem），利用面額 $v_1, v_2$ 所無法湊出的最大整數（Frobenius Number）為：

$$g(v_1, v_2) = v_1 v_2 - v_1 - v_2$$

只要令門檻值滿足：

$$c > g(v_1, v_2) \iff c \ge v_1 v_2 - v_1 - v_2 + 1 = (v_1 - 1)(v_2 - 1)$$

則所有整數 $x \ge c$ 皆可表示為 $x = a v_1 + b v_2$，其中 $a, b$ 為非負整數。

核心觀念

• 鴿子洞原理（Pigeonhole Principle）：若有 $n$ 個項目被放入少於 $n$ 個盒子，必有至少一個盒子內含兩個以上的項目。
• 圖的度（degree）：在一個無向簡單圖 $G=(V,E)$ 中，頂點 $v\in V$ 的度 $deg(v)$ 為與 $v$ 相連的邊數，即認識的人數。
• 度的範圍：對於 $|V|=n$，每個度 $deg(v)$ 必屬於 $\{0,1,\dots ,n-1\}$。若同時存在度 $0$ 的頂點與度 $n-1$ 的頂點，會產生矛盾（因為度 $n-1$ 的人認識所有其他人，導致不存在度 $0$ 的人）。

解題方法

1. 建立模型：將一次派對的參與者視為圖的頂點，若兩人相互認識（知道對方），就在圖中加一條無向邊。此時每位參與者所「認識的參與者數」即為該頂點的度。
2. 分析可能的度值
   • 若存在度 $n-1$（即有人認識全部其他 $n-1$ 人），則不可能同時有度 $0$（因為每個人至少被那位全認識的人認識）。
   • 若不存在度 $n-1$，則所有度值均在 $\{0,1,\dots ,n-2\}$ 之內。

核心觀念

• 本題屬於 Ramsey 理論 的典型例題。
• 以圖論表示：把每位參加者視為節點，若兩人互相認識則在兩節點之間畫一條 紅色邊（或稱 acquaintance），若兩人互不相識則畫一條 藍色邊（或稱 stranger）。
• 要證明的是：在任意 $n\ge 10$ 個節點的完全圖 $K_n$ 中，必存在 紅色三角形 $K_3$（三人互相認識）或 藍色四點獨立集 $I_4$（四人互相陌生）。
• 此實質上等價於證明 Ramsey 數 $R(3,4)=9$，因為 $R(3,4)$ 定義為最小的 $N$，使得任意 $K_N$ 必含 $K_3$（紅）或 $I_4$（藍）。已知 $R(3,4)=9$，故對所有 $n\ge9$（含 $10$）皆成立。

---

解題方法

1. 選取基準點
   任取一位參加者 $A$。其餘至少 $9$ 位參與者與 $A$ 的關係必為「認識」或「不認識」兩種之一。

2. 鴿巢原理分兩種情形

   • 情形一：$A$ 與至少 $5$ 位認識（即 $A$ 的紅邊度 $\deg_R(A)\ge5$）
     • 取這 $5$ 位認識 $A$ 的人集合 $S$。
     • 若 $S$ 中任兩人之間有紅邊，則形成紅色三角形：$A$ 與這兩人互相認識，證得「三互相認識」。

核心觀念

• 簡單圖 (simple graph)：無自環、無重邊。
• 連通分量 (connected component)：圖中每一個最大連通子圖。
• 樹 (tree)：一個連通且無環的圖，對於 $v$ 個頂點必有恰好 $v-1$ 條邊。
• 森林 (forest)：若圖的所有連通分量皆為樹，則整體稱為森林。

此題要求在已知頂點數 $n$ 與連通分量數 $k$ 的條件下，求 邊的最小可能數目，即找出使邊數最少的結構。

---

解題方法

1. 分解成各分量
   把 $G$ 的 $n$ 個頂點分配給 $k$ 個連通分量，令第 $i$ 個分量有 $v_i$ 個頂點，則
   $\sum_{i=1}^{k} v_i = n,\qquad v_i\ge 1.$

2. 每個分量的最少邊數
   為了保持第 $i$ 個分量連通，必須至少形成一棵樹，故最少需要 $v_i-1$ 條邊（若 $v_i=1$，即孤立點，則 $v_i-1=0$）。

3. 整體最少邊數
   所有分量的邊數相加即得 $G$ 的最少邊數：

$|E|_{\min}= \sum_{i=1}^{k} (v_i-1)=\Big(\sum_{i=1}^{k} v_i\Big)-k = n-k .$

核心觀念

• 簡單圖 (simple graph)：無自環、無重邊的無向圖。
• 連通分支 (connected component)：圖中互相可達的頂點集合。
• 完全圖 (complete graph) $K_m$：有 $m$ 個頂點且每兩點皆相連，邊數為 $\displaystyle \binom{m}{2}= \frac{m(m-1)}2$。
• 離散數學裡常用的極值技巧：在固定總和 $\sum_{i=1}^k n_i=n$ 的情況下，$\displaystyle \sum_{i=1}^k\binom{n_i}{2}$ 的上界可透過 凸性 或 均值不等式 取得。

---

解題方法

1. 把問題轉成「把$n$ 個頂點分成 $k$ 個分支」
   設第 $i$ 個連通分支的頂點數為 $n_i\;(i=1,\dots,k)$，則

$n_1+n_2+\cdots+n_k=n,\qquad n_i\ge 1.$

在第 $i$ 個分支內，若要讓邊數最多，必須是完全圖 $K_{n_i}$，其邊數為 $\displaystyle \binom{n_i}{2}$。

2. 目標函數
   整體圖的邊數上限為

$$E_{\max}= \sum_{i=1}^{k}\binom{n_i}{2} =\frac12\sum_{i=1}^{k}n_i(n_i-1).$$

3. 極大化 $\displaystyle \sum n_i(n_i-1)$
   觀察函數 $f(x)=x(x-1)$ 為凸函數（二階導數 $f''(x)=2>0$）。在固定 $\sum n_i=n$ 的條件下，凸函數的和在極端分配時取得最大值。
   因此，要使 $\sum f(n_i)$ 最大，只需要讓一個 $n_i$ 盡可能大，其餘 $n_j$ 為最小值 $1$（因為每個分支至少要有一個頂點）。
   設

$n_1=n-k+1,\qquad n_2=n_3=\dots=n_k=1.$

此時

$$\sum_{i=1}^{k}\binom{n_i}{2} =\binom{n-k+1}{2}+ \underbrace{\binom{1}{2}+\cdots+\binom{1}{2}}_{k-1\text{項}} =\binom{n-k+1}{2}.$$

核心觀念

• 完全數 (perfect number)：正整數 $n$ 若其所有真因數（不含 $n$ 本身）之和等於 $n$，即 $\sigma(n)-n=n$，則稱 $n$ 為完全數。
• 因數和函數 $\sigma$：對任意正整數 $m$，若其質因數分解為 $m=\prod_{i=1}^{k}p_i^{e_i}$，則

$\sigma(m)=\prod_{i=1}^{k}\frac{p_i^{e_i+1}-1}{p_i-1}$

為所有正因數之和。

• 梅森質數 (Mersenne prime)：形如 $2^{p}-1$（$p$ 為正整數）的質數。
• 歐幾里得定理（Euclid）：若 $2^{p}-1$ 為質數，則 $(2^{p-1})(2^{p}-1)$ 為完全數。此題即要求證明此命題。

---

解題方法

1. 寫出待證明數的因數結構
   設 $M=2^{p}-1$ 為質數，則欲證的數為

$N = 2^{p-1}M.$

觀察 $N$ 的質因數分解：

• $2$ 的指數為 $p-1$（因為 $2^{p-1}$ 為 $2$ 的冪），
• 其餘唯一質因數為 $M$。
  因此

$N = 2^{\,p-1}\cdot (2^{p}-1)=2^{\,p-1}\cdot M$

為兩個互質質因數的乘積。

2. 利用因數和公式計算 $\sigma(N)$
   由於 $\sigma$ 為乘法函數（互質因數的 $\sigma$ 可相乘），得

$\sigma(N)=\sigma\!\left(2^{\,p-1}\right)\cdot\sigma(M).$

• 計算 $\sigma\!\left(2^{\,p-1}\right)$：

$$\sigma\!\left(2^{\,p-1}\right)=1+2+2^{2}+\cdots+2^{\,p-1} =\frac{2^{p}-1}{2-1}=2^{p}-1=M.$$

• 計算 $\sigma(M)$：
  由於 $M$ 本身是質數，僅有因數 $1$ 與 $M$，故

$\sigma(M)=1+M=1+(2^{p}-1)=2^{p}.$

代回：

$\sigma(N)=\bigl(2^{p}-1\bigr)\cdot 2^{p}=2^{p}\,(2^{p}-1).$

3. 求真因數和
   完全數的定義要求

$\sigma(N)-N = N.$

核心觀念

1. 同位數數值的代數展開（因式分解法）：
   若一個十進位正整數由 $2k$ 個相同的數字組成，可將其每兩位一組分塊，提出公因數 $99$：

   $$10^{2k} - 1 = (10^2 - 1)(10^{2k-2} + 10^{2k-4} + \dots + 10^2 + 1)$$

   其中 $10^2 - 1 = 99 = 9 \times 11$。

2. $11$ 的整除性判定法（Alternating Sum Divisibility Rule）：
   十進位整數 $N = \sum_{i=0}^{n} a_i 10^i$ 滿足：

   $$10 \equiv -1 \pmod{11} \implies N \equiv \sum_{i=0}^{n} a_i (-1)^i \pmod{11}$$

   即「奇數位數字之和」與「偶數位數字之和」的差若能被 $11$ 整除，則原數 $N$ 必能被 $11$ 整除。

---

解題方法

題目給定之數字由 $32$ 個 $9$ 所組成：

$$N = \underbrace{9999\dots99}_{32 \text{ 個 } 9} = 10^{32} - 1$$

要求在無需進行大數質因數分解的前提下，找出滿足以下三個條件的因數 $d$：

1. $d \mid N$
2. $d$ 不是 $3$ 的倍數（$3 \nmid d$）
3. $2 \le d \le 99$

可透過以下兩種無需實際分解大數的途徑立即求得：

方法一：兩位一節代數提公因數法

因為該數共有 $32$ 位，而 $32$ 為偶數，將每相鄰兩位「$99$」視為一節：

$$N = 99 \times 10^{30} + 99 \times 10^{28} + \dots + 99 \times 10^2 + 99$$

提出公因數 $99$：

$$N = 99 \times \left( 10^{30} + 10^{28} + \dots + 10^2 + 1 \right)$$

顯然 $99$ 為 $N$ 的因數。將 $99$ 進行基礎因數分解：

$$99 = 9 \times 11$$

因此 $11$ 亦必為 $N$ 的因數。

核心觀念

• Big‑O 定義：對於兩個函數 $f,g:\mathbb N^{+}\to\mathbb R$，
  $f=O(g)\iff \exists C>0,\;N\in\mathbb N^{+}\ \text{使得}\ \forall n\ge N,\ |f(n)|\le C\,|g(n)|.$
• 等價關係需要自反、對稱、傳遞三性。
• 偏序關係需要自反、反對稱、傳遞三性。
• 全序關係在偏序的基礎上，還要求任意兩元素可比較（$x\le y$ 或 $y\le x$）。

---

解題方法

1. 檢查自反性

$f=O(f) \quad(\text{取 }C=1,\ N=1)$

成立，故 $\star$ 自反。

2. 檢查對稱性（等價關係）
   只需找一對函數使 $f=O(g)$ 成立而 $g=O(f)$ 不成立。
   取

$f(n)=n,\qquad g(n)=n^{2}.$

則 $f=O(g)$（取 $C=1,\ N=1$），但不存在常數 $C$ 使 $n^{2}\le Cn$ 對所有大 $n$ 成立，故 $g\neq O(f)$。
因此 $\star$ 非對稱，不構成等價關係。

3. 檢查傳遞性（偏序與全序均需）
   若 $f=O(g)$ 且 $g=O(h)$，則存在 $C_{1},N_{1}$ 與 $C_{2},N_{2}$ 滿足

$$|f(n)|\le C_{1}|g(n)|\;(n\ge N_{1}),\qquad |g(n)|\le C_{2}|h(n)|\;(n\ge N_{2}).$$

合併得

$|f(n)|\le C_{1}C_{2}|h(n)|\;(n\ge \max\{N_{1},N_{2}\}),$

故 $f=O(h)$。傳遞性成立。

4. 檢查反對稱性（偏序所必須）
   只要找到兩個不同函數滿足相互的 $O$ 關係，即可證明非反對稱。
   取

$f(n)=n,\qquad g(n)=2n.$

兩者皆屬於同階增長，且

$f=O(g),\quad g=O(f)$

核心觀念

• Euler ﹡函數 $\phi(n)$：​在 $1,2,\dots ,n-1$ 中與 $n$ 互質的正整數個數。
• 互質：若 $\gcd(a,b)=1$，則 $a$ 與 $b$ 沒有共同的質因數。
• 中國餘數定理 (CRT)：當 $\gcd(a,b)=1$ 時，映射
  $\displaystyle f:\mathbb Z_{ab}\to\mathbb Z_a\times\mathbb Z_b,\qquad f(k)=\bigl(k\bmod a,\;k\bmod b\bigr)$
  是雙射。

解題方法

1. 拆解互質條件
   若 $\gcd(k,ab)=1$，因為 $a$、$b$ 互質，必有
   $\gcd(k,a)=1\quad\text{且}\quad\gcd(k,b)=1.$
   反過來，若同時滿足 $\gcd(k,a)=1$ 與 $\gcd(k,b)=1$，則 $\gcd(k,ab)=1$。

2. 建立集合與映射
   定義
   $S_{ab}=\{\,k\mid 1\le k\le ab-1,\;\gcd(k,ab)=1\,\},$

$$S_a=\{\,x\mid 1\le x\le a-1,\;\gcd(x,a)=1\,\},\qquad S_b=\{\,y\mid 1\le y\le b-1,\;\gcd(y,b)=1\,\}.$$

想證明 $|S_{ab}|=|S_a|\cdot|S_b|$。

3. 利用 CRT 的雙射
   因 $\gcd(a,b)=1$，CRT 給予雙射

$$\Phi:\mathbb Z_{ab}\longrightarrow\mathbb Z_a\times\mathbb Z_b,\quad \Phi(k)=(k\bmod a,\;k\bmod b).$$

若 $k\in S_{ab}$，則 $\gcd(k,ab)=1$，根據步驟 1 可得

核心觀念

• 本題測試 一階謂詞邏輯 的表述能力，需把自然語句「所有人都有兩位父母」翻譯成只允許使用 $\forall,\exists,\neq,\in,\to,\wedge,\vee,\leftrightarrow,\neg$ 的形式。
• 重要的概念包括：
  1. 全稱量化（$\forall$）用於「所有」的敘述。
  2. 存在量化（$\exists$）用於「至少有」的敘述。
  3. 不等式（$\neq$）保證兩位父母是不同的個體。
  4. 集合成員（$\in$）保證所談的個體屬於人集合 $P$。

解題方法

1. 確定變數範圍
   • 令 $y$ 表示任意「人」，必須先寫 $y\in P$。
2. 寫出「有兩位父母」的存在條件
   • 需要兩個可能相同的變數 $x_1,x_2$，並加上 $x_1\neq x_2$ 以排除同一個人是兩次父母的情形。
   • 同時加入 $Parent(x_i,y)$（$i=1,2$）來表達「$x_i$ 為 $y$ 的父母」。
   • 為保證 $x_1,x_2$ 也是人，加入 $x_i\in P$。
3. 組合全稱與存在量化
   • 先對所有 $y\in P$ 施行全稱，接著在其範圍內使用存在量化描述兩位父母。
4. 精簡與排列
   • 論述順序只要保持邏輯正確即可，通常寫成

核心觀念
本題考查遞迴式定義在一階謂詞邏輯中的寫法。

• Parent(x,y)：$x$ 為 $y$ 的父母。
• Ancestor(x,y)：$x$ 為 $y$ 的祖先。
• 祖先的定義 含兩層含意：
  1. 父母本身即為祖先；
  2. 若 $x$ 為某個父母的祖先，則 $x$ 也是 $y$ 的祖先。

在僅允許 $\forall,\ \exists,\ \neq,\ \in,\ \to,\ \wedge,\ \vee,\ \leftrightarrow,\ \neg$ 的語言中，需要將上述自然語意完整轉譯為等值的邏輯式。

---

解題方法

1. 寫出「必要且充分」的條件：
   由定義可得
   $\text{Ancestor}(x,y) \iff \bigl(\text{Parent}(x,y) \;\vee\; \exists z\,[\text{Parent}(z,y) \wedge \text{Ancestor}(x,z)]\bigr).$
   • 左邊是欲定義的謂詞；
   • 右邊是兩個互斥且完整的情形（父母或父母的祖先）。
2. 使用 $\forall$ 表示「若且唯若」：
   為了符合題目要求的僅允許的符號，可將等價式寫成
   $\forall x\,\forall y\;\bigl(\text{Ancestor}(x,y) \leftrightarrow [\text{Parent}(x,y) \;\vee\; \exists z\;(\text{Parent}(z,y) \wedge \text{Ancestor}(x,z))]\bigr).$

核心觀念

• 量詞與命題變項：使用 $\forall,\exists$ 量詞，變項的取值範圍皆為全體人集合 $P$。
• 基本關係：
  • $Parent(x,y)$ ：$x$ 為 $y$ 的父母。
  • $Ancestor(x,y)$ ：$x$ 為 $y$ 的祖先（可視為已定義的二元關係）。
  • $Fight(x,y)$ ：$x$ 與 $y$ 有爭執。
• 衍生概念：
  • 子女（offspring）：$z$ 為 $x$ 的子女 ⇔ $Parent(x,z)$。
  • 「有爭執」的否定：$¬Fight(x,z)$ 或 $\neg \exists z\,(Parent(x,z)\land Fight(x,z))$。

---

解題方法

1. 明確化語意

   • 「某人」 → $\exists x$。
   • 「與其祖先有爭執」 → 存在一個祖先 $y$ 使 $Ancestor(y,x)$ 且 $Fight(x,y)$。
   • 「但與其子女(offspring)沒有爭執」 → 對所有子女 $z$，若 $Parent(x,z)$ 則 $\neg Fight(x,z)$，等價於「不存在同時滿足 $Parent(x,z)$ 與 $Fight(x,z)$」的 $z$。

2. 寫成邏輯式

   • 先寫出「與祖先有爭執」的子式：
     $\exists y\,(Ancestor(y,x)\land Fight(x,y))$
   • 再寫出「與子女無爭執」的子式：
     $\neg\exists z\,(Parent(x,z)\land Fight(x,z))$
     （或等價寫成 $\forall z\,(Parent(x,z)\to\neg Fight(x,z))$）
   • 兩子式以 conjunction $\land$ 連接，最後以 $\exists x$ 包起整體：

$$\boxed{\displaystyle \exists x\Bigl(\bigl[\exists y\,(Ancestor(y,x)\land Fight(x,y))\bigr]\land \bigl[\neg\exists z\,(Parent(x,z)\land Fight(x,z))\bigr]\Bigr)}$$

若偏好全稱量詞寫法，可改寫為