110 年 國立政治大學資訊科學系碩士班《計算機數學》

核心觀念

設 $\Phi=\varnothing$ 為空集合：

• 空集合沒有任何元素，即 $\Phi$ 中沒有元素。
• 對任意集合 $A$，都有 $\varnothing\subseteq A$。
• 集合的基數 $|\varnothing|=0$。
• $\{\Phi\}$ 是「以空集合 $\Phi$ 為唯一元素」的集合，因此 $|\{\Phi\}|=1$。

解題方法

逐一依照「元素屬於集合」與「集合包含於集合」的定義判斷。

集合包含關係 $A\subseteq B$ 的定義是：$A$ 的每一個元素都屬於 $B$。由於空集合沒有元素，因此不存在元素違反條件，故空集合是任何集合的子集合：

$$\varnothing\subseteq A$$

對所有集合 $A$ 均成立。

選項分析

(A) $\Phi\in\Phi$

錯誤。$\Phi=\varnothing$ 沒有任何元素，因此不可能有

$$\Phi\in\Phi$$

空集合不是自己的元素。

(B) $\Phi\subseteq\Phi$

正確。任何集合都是自己的子集合，且空集合沒有元素需要檢查，因此

$$\varnothing\subseteq\varnothing$$

成立。

本題在考驗集合論中的基本運算與性質，特別是關於有限集合的計數公式、冪集以及集合運算的分配律、減法等。題目要求找出一個「錯誤」的敘述。

我們逐一分析每個選項：

(A) $|A \cup B| = |A| + |B| - |A \cap B|$
這是集合論中「排容原理」（Principle of Inclusion-Exclusion）對於兩個集合的公式。它給出了兩個集合聯集的元素個數。這個公式是正確的。
證明：當我們計算 $|A| + |B|$ 時，屬於 $A \cap B$ 的元素被計算了兩次。為了得到正確的聯集個數，我們需要減去一次 $A \cap B$ 的元素個數。
因此，此敘述為真。

(B) $P(A \cup B) = P(A) \cup P(B)$
這裡 $P(X)$ 代表集合 $X$ 的冪集（power set），即包含 $X$ 所有子集的集合。
這個敘述聲稱兩個集合的聯集的冪集等於它們各自冪集的聯集。
讓我們用一個反例來檢驗這個敘述。
設 $A = \{a\}$ 且 $B = \{b\}$。
則 $A \cup B = \{a, b\}$。
$P(A \cup B) = \{\Phi, \{a\}, \{b\}, \{a, b\}\}$。
$P(A) = \{\Phi, \{a\}\}$。
$P(B) = \{\Phi, \{b\}\}$。
$P(A) \cup P(B) = \{\Phi, \{a\}\} \cup \{\Phi, \{b\}\} = \{\Phi, \{a\}, \{b\}\}$。
比較 $P(A \cup B)$ 和 $P(A) \cup P(B)$，我們發現 $P(A \cup B)$ 中包含元素 $\{a, b\}$，而 $P(A) \cup P(B)$ 中不包含 $\{a, b\}$。
因此，$P(A \cup B) \neq P(A) \cup P(B)$。
這個敘述是錯誤的。
正確的關係是：如果 $A \subseteq B$，則 $P(A) \subseteq P(B)$。

本題考驗集合論中關於聯集、交集、差集和對稱差集（symmetric difference）的性質，特別是這些運算在推導集合相等性時的條件。題目要求找出一個「正確」的敘述。

我們逐一分析每個選項：

(A) If $A \cup C = B \cup C$, then $A = B$
這個敘述聲稱，如果兩個集合與第三個集合的聯集相等，那麼這兩個集合本身就相等。
這不一定正確。我們可以舉一個反例。
設 $A = \{1\}$, $B = \{1, 2\}$, $C = \{3\}$。
則 $A \cup C = \{1\} \cup \{3\} = \{1, 3\}$。
$B \cup C = \{1, 2\} \cup \{3\} = \{1, 2, 3\}$。
這裡 $A \cup C \neq B \cup C$。

再試一個反例，讓聯集相等。
設 $A = \{1\}$, $B = \{1, 2\}$, $C = \{2\}$。
則 $A \cup C = \{1\} \cup \{2\} = \{1, 2\}$。
$B \cup C = \{1, 2\} \cup \{2\} = \{1, 2\}$。
此時 $A \cup C = B \cup C$ 成立，但 $A \neq B$。
因此，此敘述為假。

(B) If $A \cap C = B \cap C$, then $A = B$
這個敘述聲稱，如果兩個集合與第三個集合的交集相等，那麼這兩個集合本身就相等。
這也不一定正確。
設 $A = \{1\}$, $B = \{1, 2\}$, $C = \{1\}$。
則 $A \cap C = \{1\} \cap \{1\} = \{1\}$。
$B \cap C = \{1, 2\} \cap \{1\} = \{1\}$。
此時 $A \cap C = B \cap C$ 成立，但 $A \neq B$。
因此，此敘述為假。

核心觀念

本題考查模冪運算，以及指數法則：

$$(a^7)^9=a^{7\cdot 9}=a^{63}$$

因此題目等價於計算：

$$2^{63}\pmod{101}$$

因為 $101$ 是質數，費馬小定理給出：

$$2^{100}\equiv 1\pmod{101}$$

本題指數 $63<100$，不需先化簡指數，直接利用平方快速計算即可。

解題方法

逐步計算 $2$ 的平方冪：

$$2^{10}=1024\equiv 14\pmod{101}$$

因此：

$$2^{20}\equiv 14^2=196\equiv 95\pmod{101}$$

又因為：

$$2^{40}\equiv 95^2=9025\equiv 36\pmod{101}$$

將 $63$ 分解為：

$$63=40+20+3$$

所以：

$$2^{63}=2^{40}\cdot 2^{20}\cdot 2^3$$

代入上述結果：

$$2^{63}\equiv 36\cdot 95\cdot 8\pmod{101}$$

先計算：

核心觀念

同餘的定義為

$$a\equiv b\pmod m \quad\Longleftrightarrow\quad m\mid(a-b).$$

也就是存在整數 $t$，使得

$$a-b=mt.$$

本題的判斷關鍵，是將「同餘」轉換成「整除」，再檢查倍乘後是否仍可被指定模數整除。

---

解題方法

由 $a\equiv b\pmod n$ 可知

$$n\mid(a-b),$$

因此存在整數 $t$，使得

$$a-b=nt.$$

兩邊乘以整數 $k$：

$$ka-kb=k(a-b)=knt.$$

所以

$$kn\mid(ka-kb),$$

即

$$ka\equiv kb\pmod{kn}.$$

此外，因為 $n\mid kn$，若

$$kn\mid(a-b),$$

則必然有

$$n\mid(a-b),$$

因此

$$a\equiv b\pmod n.$$

---

選項分析

(A) 正確

由

$$a\equiv b\pmod n$$

可得 $n\mid(a-b)$。乘以整數 $k$ 後，

$$ka-kb=k(a-b),$$

仍可被 $n$ 整除，因此

$$ka\equiv kb\pmod n.$$

---

(B) 正確

由 $n\mid(a-b)$，存在整數 $t$ 使

$$a-b=nt.$$

乘以 $k$ 得

$$ka-kb=knt.$$

因此 $kn\mid(ka-kb)$，所以

本題考驗邏輯學中的基本命題邏輯和謂詞邏輯的等價關係。題目要求找出一個「正確」的敘述。

我們逐一分析每個選項：

(A) $\neg (p \rightarrow q) \equiv \neg p \vee q$
這是對蘊含（implication）的否定規則。
根據蘊含的定義，$p \rightarrow q \equiv \neg p \vee q$。
所以，$\neg (p \rightarrow q) \equiv \neg (\neg p \vee q)$。
根據德摩根定律，$\neg (\neg p \vee q) \equiv \neg (\neg p) \wedge \neg q \equiv p \wedge \neg q$。
因此，$\neg (p \rightarrow q) \equiv p \wedge \neg q$。
選項給出的 $\neg p \vee q$ 是 $p \rightarrow q$ 本身。
所以，$\neg (p \rightarrow q) \equiv \neg p \vee q$ 是錯誤的。
正確的等價式是 $\neg (p \rightarrow q) \equiv p \wedge \neg q$。

(B) $(p \leftrightarrow q) \equiv \neg p \leftrightarrow q$
這是雙條件（biconditional）的等價關係。
雙條件 $p \leftrightarrow q$ 為真若且唯若 $p$ 和 $q$ 的真值相同。
$\neg p \leftrightarrow q$ 為真若且唯若 $\neg p$ 和 $q$ 的真值相同。
這意味著 $p$ 和 $q$ 的真值必須不同。
所以，$(p \leftrightarrow q)$ 表示 $p, q$ 同真值，而 $\neg p \leftrightarrow q$ 表示 $p, q$ 異真值。
它們是互斥的，不是等價的。
事實上，$(p \leftrightarrow q) \equiv \neg (\neg p \leftrightarrow q)$。
因此，此敘述為假。

(C) $\exists x (Q(x) \wedge R(x)) \equiv \forall x (\neg Q(x) \vee R(x))$
這是關於量詞（quantifier）的轉換規則，涉及存在量詞（existential quantifier）和全稱量詞（universal quantifier）。
左邊是 $\exists x (Q(x) \wedge R(x))$，表示「存在一個 $x$ 使得 $Q(x)$ 和 $R(x)$ 都成立」。
右邊是 $\forall x (\neg Q(x) \vee R(x))$。

本題考驗謂詞邏輯（predicate logic）中量詞（quantifiers）的性質，特別是關於全稱量詞（$\forall$）和存在量詞（$\exists$）與邏輯連接詞（$\vee$, $\wedge$, $\rightarrow$）結合時的蘊含關係。題目要求找出一個「錯誤」的敘述。

我們逐一分析每個選項：

(A) $\forall x[Q(x) \vee R(x)] \rightarrow \forall x Q(x) \vee \forall x R(x)$
左邊敘述：對於所有的 $x$， $Q(x)$ 或 $R(x)$ 為真。
右邊敘述：對於所有的 $x$，$Q(x)$ 為真，或者對於所有的 $x$，$R(x)$ 為真。
這個蘊含關係是「錯誤」的。
反例：設論域為整數。
$Q(x)$: $x$ 是偶數。
$R(x)$: $x$ 是奇數。
左邊：$\forall x [x \text{ is even} \vee x \text{ is odd}]$。這句話為真，因為每個整數不是偶數就是奇數。
右邊：$\forall x [x \text{ is even}] \vee \forall x [x \text{ is odd}]$。
$\forall x [x \text{ is even}]$ 為假（例如 $x=3$ 不是偶數）。
$\forall x [x \text{ is odd}]$ 為假（例如 $x=2$ 不是奇數）。
所以，右邊是 $False \vee False \equiv False$。
因此，左邊為真，右邊為假，蘊含關係不成立。
此敘述為假。

(B) $\forall x[Q(x) \rightarrow R(x)] \rightarrow \forall x Q(x) \rightarrow \forall x R(x)$
左邊敘述：對於所有的 $x$，如果 $Q(x)$ 為真，則 $R(x)$ 為真。
右邊敘述：如果對於所有的 $x$，$Q(x)$ 為真，則對於所有的 $x$，$R(x)$ 為真。
這個蘊含關係是「正確」的。
證明：假設左邊 $\forall x[Q(x) \rightarrow R(x)]$ 為真。
現在我們要證明右邊的蘊含 $\forall x Q(x) \rightarrow \forall x R(x)$。
假設 $\forall x Q(x)$ 為真。這意味著對於任何一個 $x$，$Q(x)$ 都為真。
又因為我們假設了 $\forall x[Q(x) \rightarrow R(x)]$ 為真，所以對於這個任意的 $x$， $Q(x) \rightarrow R(x)$ 也為真。

本題考驗組合學中的排列與組合問題，特別是涉及條件約束的計數。題目要求找出一個包含五個 0 和十四個 1 的位元字串的數量，條件是每個 0 都必須緊接著兩個 1。

我們將每個 0 和它必須跟隨的兩個 1 視為一個整體單元。這個單元的形式是 "011"。
這個單元 "011" 包含一個 0 和兩個 1。
我們總共有五個 0，所以我們會有五個這樣的 "011" 單元。
這五個 "011" 單元總共使用了 $5 \times 1 = 5$ 個 0，以及 $5 \times 2 = 10$ 個 1。

我們被要求構成一個包含「exactly five 0s and fourteen 1s」的字串。
我們已經使用了 5 個 0 和 10 個 1 來構成五個 "011" 單元。
剩下的 1 的數量是 $14 - 10 = 4$ 個 1。

現在，我們的問題就轉變為：如何排列這五個 "011" 單元和剩餘的四個 1？
我們總共有 $5$ 個 "011" 單元和 $4$ 個獨立的 1。
這總共是 $5 + 4 = 9$ 個項目需要排列。

這是一個關於重複項的排列問題。我們有 9 個位置來放置這些項目。
其中有 5 個項目是相同的（"011" 單元），另外 4 個項目也是相同的（獨立的 1）。
但是，題目問的是「bit strings」，這意味著我們需要將這些單元組合起來形成一個字串。
我們有 5 個 "011" 單元和 4 個獨立的 1。
我們可以將這 $5+4=9$ 個「單元」（"011" 作為一個單位，獨立的 1 作為一個單位）進行排列。

我們有 9 個「位置」可以放置這些項目。
其中 5 個位置將被 "011" 佔據，4 個位置將被獨立的 1 佔據。

本題考驗組合學中的「隔板法」（stars and bars）問題，並結合了限制條件的處理。題目要求將九個相同的積木分給四個小孩 A, B, C, D，其中小孩 A 最多只能得到兩個積木。

首先，我們將問題分解。這是一個將 $n$ 個相同物品分給 $k$ 個不同收件者的問題。如果沒有任何限制，將 $n$ 個相同物品分給 $k$ 個不同收件者的方法數是 $C(n+k-1, k-1)$ 或 $C(n+k-1, n)$。
在這裡，$n=9$ (積木數量)，$k=4$ (小孩數量)。
如果沒有任何限制，總分法數是 $C(9+4-1, 4-1) = C(12, 3) = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = 2 \times 11 \times 10 = 220$。

但是，我們有額外的限制：小孩 A 最多只能得到兩個積木。
這意味著小孩 A 得到的積木數量 $x_A$ 必須滿足 $x_A \le 2$。
所以，$x_A$ 可以是 0, 1, 或 2。
小孩 B, C, D 得到的積木數量 $x_B, x_C, x_D$ 沒有限制，即 $x_B, x_C, x_D \ge 0$。
總共有九個積木，所以 $x_A + x_B + x_C + x_D = 9$。

我們可以使用「排除法」來解決這個問題。
總方法數（220）減去小孩 A 得到的積木數量超過 2 的情況。
小孩 A 得到的積木數量超過 2，意味著 $x_A \ge 3$。

我們計算 $x_A \ge 3$ 的情況。
令 $x_A' = x_A - 3$。由於 $x_A \ge 3$，所以 $x_A' \ge 0$。
原方程式變為 $(x_A' + 3) + x_B + x_C + x_D = 9$。
$x_A' + x_B + x_C + x_D = 9 - 3 = 6$。

本題考驗組合學中的「分堆」（partition）或「分區」（distribution）問題，特別是涉及相同物品分給相同容器的問題。題目要求將五個臨時員工（視為相同物品）放入四個相同的辦公室。

這是一個將 $n$ 個相同物品分給 $k$ 個相同容器的問題。
在這裡，$n=5$ (員工數量)，$k=4$ (辦公室數量)。
由於辦公室是相同的，我們關心的是每個辦公室裡有多少個員工，而不是哪個員工在哪個辦公室。
這相當於將整數 5 分成最多 4 個部分的和。
例如，如果我們將 5 個員工分給 4 個辦公室，可能的情況是：
(5, 0, 0, 0) - 一個辦公室有 5 人，其他 3 個沒有人。
(4, 1, 0, 0) - 一個辦公室 4 人，一個 1 人，兩個沒有人。
(3, 2, 0, 0) - 一個辦公室 3 人，一個 2 人，兩個沒有人。
(3, 1, 1, 0) - 一個辦公室 3 人，兩個 1 人，一個沒有人。
(2, 2, 1, 0) - 兩個辦公室 2 人，一個 1 人，一個沒有人。
(2, 1, 1, 1) - 一個辦公室 2 人，三個 1 人。

我們需要列出所有可能的「分法」（partitions of the integer 5 into at most 4 parts）。
分法是 (part1, part2, part3, part4)，其中 part1+part2+part3+part4 = 5，且 parts 都是非負整數。由於辦公室相同，順序不重要。我們通常將 parts 按降序排列。

1. 5 個員工全放入一個辦公室：
   (5, 0, 0, 0) - 1 種分法。

2. 4 個員工放入一個辦公室，剩下 1 個員工：
   (4, 1, 0, 0) - 1 種分法。

3. 3 個員工放入一個辦公室：
   a) 剩下 2 個員工。可以分給另一個辦公室：(3, 2, 0, 0) - 1 種分法。
   b) 剩下 2 個員工，要分給兩個不同的辦公室（每人 1 個）：(3, 1, 1, 0) - 1 種分法。

4. 2 個員工放入一個辦公室：
   a) 剩下 3 個員工。
   i) 3 個員工全放入另一個辦公室：(2, 3, 0, 0) - 這與 (3, 2, 0, 0) 相同，已計。
   ii) 3 個員工分給兩個辦公室，例如 (2, 1)：(2, 2, 1, 0) - 1 種分法。
   iii) 3 個員工分給三個辦公室，每人 1 個：(2, 1, 1, 1) - 1 種分法。

5. 沒有辦公室放入 3 個或更多員工：
   也就是說，每個辦公室最多放入 2 個員工。
   由於總共 5 個員工，這意味著必須有 (2, 2, 1, 0) 或 (2, 1, 1, 1) 的組合。
   (2, 2, 1, 0) - 已計。
   (2, 1, 1, 1) - 已計。

我們來系統地列出所有可能的非負整數解 $x_1 + x_2 + x_3 + x_4 = 5$，其中 $x_i$ 是每個辦公室的人數，且順序不重要。
我們將 $x_i$ 按降序排列：$x_1 \ge x_2 \ge x_3 \ge x_4 \ge 0$。

• $x_1 = 5$: (5, 0, 0, 0) - 1 種
• $x_1 = 4$: (4, 1, 0, 0) - 1 種
• $x_1 = 3$:
  • $x_2 = 2$: (3, 2, 0, 0) - 1 種
  • $x_2 = 1$: (3, 1, 1, 0) - 1 種
• $x_1 = 2$:
  • $x_2 = 2$: (2, 2, 1, 0) - 1 種
  • $x_2 = 1$: (2, 1, 1, 1) - 1 種

總共有 $1 + 1 + 1 + 1 + 1 + 1 = 6$ 種分法。

核心觀念

本題考查聯立同餘式與廣義中國剩餘定理。當模數不一定互質時，可逐步合併同餘式；若

$$x\equiv r_1\pmod {m_1},\qquad x\equiv r_2\pmod {m_2},$$

則兩式有解的條件是

$$r_1\equiv r_2\pmod{\gcd(m_1,m_2)}.$$

合併後的週期為

$$\operatorname{lcm}(m_1,m_2).$$

解題方法

先處理前兩個同餘式。由

$$x\equiv 7\pmod 9$$

可令

$$x=7+9t.$$

代入第二式 $x\equiv4\pmod {12}$：

$$7+9t\equiv4\pmod {12},$$

因此

$$9t\equiv-3\equiv9\pmod {12}.$$

因為 $\gcd(9,12)=3$，兩邊同除以 $3$，得到

$$3t\equiv3\pmod4.$$

由於 $3^{-1}\equiv3\pmod4$，所以

$$t\equiv1\pmod4.$$

令 $t=1+4s$，則

$$x=7+9(1+4s)=16+36s.$$

再代入第三個同餘式 $x\equiv16\pmod {21}$：

$$16+36s\equiv16\pmod {21},$$

故

$$36s\equiv0\pmod {21}.$$

因為 $\gcd(36,21)=3$，約去公因數 $3$：

$$12s\equiv0\pmod7.$$

又 $12\equiv5\pmod7$，且 $5$ 在模 $7$ 下可逆，因此

$$s\equiv0\pmod7.$$

核心觀念

設 $R$ 為 $A$ 上的二元關係。

• 對稱性：若 $(a,b)\in R$，則 $(b,a)\in R$。
• 反對稱性：若 $(a,b)\in R$ 且 $(b,a)\in R$，則必須有 $a=b$。
• 反自反性：對所有 $a\in A$，$(a,a)\notin R$。

本題要求關係同時具備對稱性與反對稱性，且不是反自反關係。

---

解題方法

將有序對分成兩類討論。

1. 不同元素形成的有序對

若 $a\neq b$，由對稱性可知：

$$(a,b)\in R \Longrightarrow (b,a)\in R$$

但反對稱性要求當 $a\neq b$ 時，$(a,b)$ 與 $(b,a)$ 不可同時屬於 $R$。因此，對任意不同元素 $a,b$，兩者都不能出現在關係中：

$$(a,b)\notin R,\qquad (b,a)\notin R$$

所以，$R$ 只能包含對角線上的有序對：

$$(a,a),\qquad a\in A$$

2. 對角線上的有序對

$A$ 有 $n$ 個元素，因此共有 $n$ 個對角線有序對：

$$(a_1,a_1),(a_2,a_2),\ldots,(a_n,a_n)$$

每一個 $(a,a)$ 都可以自由選擇「放入」或「不放入」$R$，故同時滿足對稱性與反對稱性的關係共有：

$$2^n$$

其中，唯一的反自反關係是完全不包含任何對角線有序對的空關係：

核心觀念

設 $A$ 有 $n$ 個元素，二元關係 $R$ 是 $A \times A$ 的子集合。

• 反身性（reflexive）：對所有 $a \in A$，$(a,a) \in R$。
• 對稱性（symmetric）：若 $(a,b) \in R$，則 $(b,a) \in R$。

題目要求計算「反身但不對稱」的二元關係數量。

---

解題方法

先固定反身性所要求的對角元素：

$$(a,a),\quad a\in A$$

共有 $n$ 個對角有序對，這些元素必須全部屬於 $R$，沒有選擇自由。

因此，只需處理非對角有序對。非對角有序對共有

$$n^2-n=n(n-1)$$

個，所以反身關係總數為

$$2^{n^2-n}.$$

接著扣除同時反身且對稱的關係。

對於任意兩個不同元素 $a,b$，對稱性要求 $(a,b)$ 與 $(b,a)$ 必須同時出現，或同時不出現。將這兩個有序對視為一組，共有

$$\frac{n(n-1)}{2}$$

組。每一組都有 $2$ 種選擇，因此反身且對稱的關係數量為

$$2^{n(n-1)/2}.$$

所以反身但不對稱的關係數量為

$$\boxed{2^{n(n-1)}-2^{n(n-1)/2}}.$$

---

選項分析

(A) $2^{n^2}-2^{n^2-n+1}$

錯誤。反身關係的對角元素已被固定，反身關係總數應為

$$2^{n^2-n},$$

核心觀念

本題考查「完全 $4$ 元樹」的計數關係。

• 每位轉寄者都把信寄給 $4$ 位不同的人。
• 讀到信但沒有再寄出的人，視為樹的葉節點。
• 由於沒有人收到超過一封信，因此整個傳遞過程可視為一棵樹。
• 設轉寄者人數為 $s$，未轉寄者人數為 $100$，總人數為 $k$。

樹中每位轉寄者產生 $4$ 條向外的連線，因此總邊數為 $4s$。另一方面，包含第一人在內的總人數為 $k$，樹的邊數也等於 $k-1$，所以：

$$k-1=4s$$

又因為所有人可分為轉寄者與未轉寄者：

$$k=s+100$$

解題方法

將 $k=s+100$ 代入 $k-1=4s$：

$$s+100-1=4s$$ $$s+99=4s$$ $$3s=99$$ $$s=33$$

因此總人數為：

$$k=s+100=33+100=133$$

計算 $k$ 除以 $11$ 的餘數：

$$133=11\times 12+1$$

所以：

$$k\bmod 11=1$$

也可直接利用樹的葉節點公式驗算。對每位轉寄者產生 $4$ 個子節點的完全 $4$ 元樹，葉節點數 $L$ 與轉寄者數 $s$ 滿足：

$$L=3s+1$$

代入 $L=100$：

核心觀念

本題結合以下三個觀念：

1. 平面圖的 Euler 公式

$n-e+f=2$

其中 $n$ 為頂點數、$e$ 為邊數、$f$ 為面數。

2. 二分圖不含奇圈

   因此平面二分圖的每個面，其邊界長度至少為 $4$。

3. 面度數總和公式

$\sum \deg(\text{各面})=2e$

每條邊都會被兩個面共同使用。

---

解題方法

已知 $n=12$。設圖的邊數為 $e$，面數為 $f$。

由於圖是簡單二分平面圖，不存在三角形，且簡單圖不會出現長度為 $2$ 的面。因此每個面的邊界至少有 $4$ 條邊，故

$2e=\sum \deg(\text{各面})\ge 4f$

得到

$f\le \frac e2$

代入 Euler 公式：

$12-e+f=2$

由 $f\le \frac e2$，可得

$$2=12-e+f \le 12-e+\frac e2 =12-\frac e2$$

因此

$\frac e2\le 10$

所以

$e\le 20$

接著確認上界可以達到。考慮完全二分圖

核心觀念

本題考查以 Huffman coding（霍夫曼編碼） 求一段字串的最小編碼長度。

對於每個字元依出現頻率建立二元前綴碼，最小總位元數可由 Huffman 演算法求得：

1. 每次選取頻率最小的兩個節點合併。
2. 合併後的頻率為兩者之和。
3. 持續合併至只剩一個根節點。
4. 所有合併時產生的新頻率總和，即為最小編碼總長度 $k$。

---

解題方法

原字串為：

$$\texttt{aaabbcddddddeeeeeffgggggghhhhiii}$$

各字元出現次數如下：

字元	出現次數
$a$	$3$
$b$	$2$
$c$	$1$
$d$	$6$
$e$	$5$
$f$	$2$
$g$	$6$
$h$	$4$
$i$	$3$

頻率總和為：

$$3+2+1+6+5+2+6+4+3=32$$

依頻率由小到大排列：

$$1,2,2,3,3,4,5,6,6$$

進行 Huffman 合併：

核心觀念

本題考查三階常係數線性非齊次遞迴關係，主要使用：

1. 齊次遞迴的特徵方程。
2. 重根所對應的齊次解形式。
3. 待定係數法求非齊次特解。
4. 代入初始條件求常數。
5. 最後進行模 $11$ 運算。

原遞迴式可改寫為

$$a_n-7a_{n-1}+16a_{n-2}-12a_{n-3}=n4^n.$$

---

解題方法：求齊次解

先考慮齊次遞迴：

$$a_n-7a_{n-1}+16a_{n-2}-12a_{n-3}=0.$$

其特徵方程為

$$r^3-7r^2+16r-12=0.$$

因式分解得

$$r^3-7r^2+16r-12=(r-2)^2(r-3).$$

因此特徵根為 $2$（二重根）與 $3$（單根），齊次解為

$$a_n^{(h)}=\alpha 2^n+b n2^{n-1}+c3^n.$$

其中 $b n2^{n-1}$ 與常見的 $bn2^n$ 只差一個常數倍，完全等價。

---

解題方法：求非齊次特解

右側非齊次項為 $n4^n$。由於 $4$ 不是特徵根，設特解為

$$a_n^{(p)}=(d_2n^2+d_1n+d_0)4^n.$$

令

$$p(n)=d_2n^2+d_1n+d_0,$$

則 $a_n^{(p)}=p(n)4^n$。代入遞迴式並除以 $4^n$：

$$p(n)-\frac74p(n-1)+p(n-2)-\frac3{16}p(n-3)=n.$$

計算各項：

$$p(n-1)=d_2(n-1)^2+d_1(n-1)+d_0,$$ $$p(n-2)=d_2(n-2)^2+d_1(n-2)+d_0,$$ $$p(n-3)=d_2(n-3)^2+d_1(n-3)+d_0.$$

比較 $n^2$、$n$ 與常數項，可得

$$\frac{d_2}{16}n^2+\frac{d_1}{16}n+ \left(\frac{5d_1+d_0}{16}\right)=n.$$

因此係數比較為

$$\frac{d_2}{16}=0,$$ $$\frac{d_1}{16}=1,$$ $$\frac{5d_1+d_0}{16}=0.$$

解得

$$d_2=0,\qquad d_1=16,\qquad d_0=-80.$$

所以特解為

$$a_n^{(p)}=(16n-80)4^n.$$

---

代入初始條件

完整解為