115 年 國立中山大學資訊工程學系碩士班甲組《離散數學》

核心觀念

• 多重集合的排列：當字母有重複時，排列數需除以各重複字母的階乘。
• 間隙法 (gap method)：先排列不含限制條件的字母，之後將受限制的字母插入產生的「間隙」中，以保證不相鄰。
• 組合選取：從產生的間隙中選取放置限制字母的位置，使用二項式係數 $\binom{n}{k}$。

---

解題方法

1. 分離字母
   • 原字串 ENGINEERING 含 11 個字母。
   • 各字母出現次數

$E:3,\; N:3,\; G:2,\; I:2,\; R:1$

• 先將 E（受「不相鄰」限制）抽出，其餘 8 個字母為

$\{N,N,N,\; G,G,\; I,I,\; R\}$

2. 排列其餘 8 個字母
   這是一個多重集合的排列，個數為

$\frac{8!}{3!\,2!\,2!\,1!}= \frac{40320}{6\cdot2\cdot2}=1680$

3. 建立間隙
   排好 8 個字母後，可產生 9 個間隙（包括首尾）：

$\_\,L_1\,\_\,L_2\,\_\,\dots\,L_8\,\_$

核心觀念
本題屬於「有界正整數組合」的計數問題。需利用 星星與條棒（Stars and Bars） 公式，結合 上界限制（每個變數只能取 $1\sim5$）的排除法（或等價的變數平移）來求解。

解題方法

1. 平移變數：將限制 $x,y,z\in\{1,2,3,4,5\}$ 轉換為非負整數。設
   $x'=x-1,\qquad y'=y-1,\qquad z'=z-1$
   則 $x',y',z'\ge0$，且上界變為 $x',y',z'\le4$。原方程式變為
   $(x'+1)+(y'+1)+(z'+1)=10\;\Longrightarrow\;x'+y'+z'=7.$

2. 先不考慮上界：若只要求 $x',y',z'\ge0$，利用星星與條棒公式，非負整數解的個數為
   $\binom{7+3-1}{3-1}=\binom{9}{2}=36.$

3. 排除上界違反的情形（即有變數 $>4$）。使用容斥原理：

   • 設 $A_x$ 為「$x'>4$」的集合，同理 $A_y,A_z$。
   • 計算 $|A_x|$：令 $x''=x'-5\;(x''\ge0)$，則 $x''+y'+z'=2$，解的個數為 $\binom{2+3-1}{2}= \binom{4}{2}=6$。同理 $|A_y|=|A_z|=6$。
   • 計算兩兩交集 $|A_x\cap A_y|$：令 $x''=x'-5,\;y''=y'-5$，則 $x''+y''+z'= -3$，無非負解，故交集個數為 $0$。同理其他兩兩交集皆為 $0$。
   • 三重交集 $|A_x\cap A_y\cap A_z|$ 更不可能出現，個數 $0$。

核心觀念

• 可被整除的定義：若整數 $n$ 能寫成 $n = kd$，其中 $k$ 為整數，則稱 $n$ 能被 $d$ 整除。
• 容斥原理（Inclusion–Exclusion Principle）：計算「至少滿足其中一個條件」的個數時，須先加上各單條件的個數，再減去兩兩交集的個數，最後加回全部條件同時成立的個數。
• 整數區間內可被 $d$ 整除的個數：對於區間 $[a,b]$（$a,b$ 為正整數），可被 $d$ 整除的數量為
  $\Big\lfloor\frac{b}{d}\Big\rfloor-\Big\lfloor\frac{a-1}{d}\Big\rfloor.$

---

解題方法

1. 設定區間
   3 位數的範圍為 $[100,999]$。

2. 計算單獨可被 3、5、7 整除的個數

   • 被 $3$ 整除的個數

$$N_3=\Big\lfloor\frac{999}{3}\Big\rfloor-\Big\lfloor\frac{99}{3}\Big\rfloor =333-33=300.$$

• 被 $5$ 整除的個數

$$N_5=\Big\lfloor\frac{999}{5}\Big\rfloor-\Big\lfloor\frac{99}{5}\Big\rfloor =199-19=180.$$

• 被 $7$ 整除的個數

$$N_7=\Big\lfloor\frac{999}{7}\Big\rfloor-\Big\lfloor\frac{99}{7}\Big\rfloor =142-14=128.$$

3. 計算兩兩交集（同時被兩個數整除）的個數
   交集的公倍數即為兩數的最小公倍數（LCM）。

   • $3$ 與 $5$ 的 LCM 為 $15$

$$N_{3\cap5}= \Big\lfloor\frac{999}{15}\Big\rfloor-\Big\lfloor\frac{99}{15}\Big\rfloor =66-6=60.$$

核心觀念

• 最大公因數 (Greatest Common Divisor, GCD)：兩個或多個整數的最大公因數是能同時整除這些整數的最大正整數。
• 歐幾里得算法 (Euclidean algorithm)：對任意正整數 $a,b$（$a>b$），
  $\gcd(a,b)=\gcd(b,\,a\bmod b)$
  透過不斷以較大者除以較小者取餘數，最終餘數為 $0$ 時的除數即為 GCD。此算法的正確性來自「若 $d$ 整除 $a$ 與 $b$，則 $d$ 亦整除 $a-b\lfloor a/b\rfloor$」的性質。

---

解題方法

1. 列寫數字
   $a=1\,066\,601,\qquad b=343\,033$

2. 第一次取餘
   $1\,066\,601 = 3\cdot 343\,033 + 37\,502$
   $\Rightarrow\gcd(1\,066\,601,343\,033)=\gcd(343\,033,37\,502)$

3. 第二次取餘
   $343\,033 = 9\cdot 37\,502 + 5\,515$
   $\Rightarrow\gcd(343\,033,37\,502)=\gcd(37\,502,5\,515)$

4. 第三次取餘
   $37\,502 = 6\cdot 5\,515 + 4\,412$
   $\Rightarrow\gcd(37\,502,5\,515)=\gcd(5\,515,4\,412)$

核心觀念
本題屬於格點路徑計數（lattice path）問題。

• 允許的步伐有三種：右移 $R:(0,1)$、上移 $U:(1,0)$、右上斜移 $D:(1,1)$。
• 從左下角 $(1,1)$ 到右上角 $(5,5)$ 必須使 $x$、$y$ 各增加 $4$。
• 典型工具：多項式係數（multinomial coefficient） 或 遞迴/動態規劃 $f(i,j)=f(i-1,j)+f(i,j-1)+f(i-1,j-1)$。

---

解題方法

1. 設定變數
   設走 $R$ 的次數為 $r$，走 $U$ 的次數為 $u$，走 $D$ 的次數為 $d$。
   依題目條件得到線性方程式

$$\begin{cases} u+d = 4,\\[2mm] r+d = 4. \end{cases}$$

因此

$r = 4-d,\qquad u = 4-d,\qquad d\in\{0,1,2,3,4\}.$

2. 路徑排列數
   對於固定的 $d$，總步數 $n=r+u+d = 8-d$。
   步伐的排列方式為多項式係數

$$N(d)=\frac{n!}{r!\,u!\,d!} =\frac{(8-d)!}{(4-d)!\,(4-d)!\,d!}.$$

3. 逐項求和

$d$	$r=4-d$	$u=4-d$	$n=8-d$	$N(d)=\dfrac{n!}{r!u!d!}$
0	4	4	8	$\displaystyle\frac{8!}{4!4!}=70$

核心觀念

• 本題屬於「組合」中的「選擇」類問題，要求在集合 $S=\{1,2,\dots ,9\}$ 中選出 3 個不相鄰的元素。
• 需運用「間距（gap）」的概念或「Stars and Bars」技巧，將「不相鄰」的限制轉換成普通的組合計算。
• 相關定理：若從長度為 $n$ 的序列中挑選 $k$ 個元素且任意兩者之間至少相差 $d$，則等價於從長度 $n-(d-1)(k-1)$ 的序列中挑 $k$ 個，即
  $\binom{\,n-(d-1)(k-1)\,}{k}.$
  本題 $d=2$（必須至少間隔 1），$n=9$，$k=3$，得到 $\binom{7}{3}$。

---

解題方法

1. 設定變數
   設所選的三個數為 $a<b<c$，且滿足 $b\ge a+2,\;c\ge b+2$（即不相鄰）。

2. 引入間距修正
   定義
   $x_1 = a,\qquad x_2 = b-1,\qquad x_3 = c-2.$
   由於 $b\ge a+2$ ⇒ $x_2 = b-1 \ge a+1 = x_1+1$，同理 $c\ge b+2$ ⇒ $x_3 \ge x_2+1$。
   因此 $x_1 < x_2 < x_3$，且
   $1\le x_1,\qquad x_3 = c-2 \le 9-2 = 7.$

核心觀念
本題考查的是模同餘下的乘法階（order）概念。對於給定的模數 $n$（此處 $n=13$），若 $a$ 與 $n$ 互質，則存在最小的正整數 $k$ 使得
$a^{\,k}\equiv 1\pmod n.$
此 $k$ 稱為 $a$ 在模 $n$ 下的階。解題時常利用費馬小定理與歐拉定理來限制可能的階，並透過直接驗算找出最小解。

解題方法

1. 確認互質條件：$2$ 與 $13$ 為質數且互質，可使用費馬小定理。
2. 依費馬小定理，對於質數 $p=13$，有
   $2^{12}\equiv 1\pmod{13}.$
   因此 $x$ 必為 $12$ 的因數。列出 $12$ 的正因數：$1,2,3,4,6,12$。
3. 逐一檢驗 $2^{d}\pmod{13}$，尋找最小 $d$ 滿足同餘式。
   • $d=1$: $2^{1}=2\not\equiv1\pmod{13}$。
   • $d=2$: $2^{2}=4\not\equiv1\pmod{13}$。
   • $d=3$: $2^{3}=8\not\equiv1\pmod{13}$。
   • $d=4$: $2^{4}=16\equiv3\pmod{13}$，仍不等於 $1$。

核心觀念

• 函數的原像（pre‑image）：對於集合 $B\subseteq A$，$f^{-1}(B)=\{x\in A\mid f(x)\in B\}$。題目直接給出若干原像的值，等價於「哪些元素必須映射到哪些值」以及「哪些值絕對不能被其他元素映射」。
• 集合的划分：利用原像條件把定義域 $A$ 切分成若干互不相交的子集，分別討論它們的可能映射。
• 乘法原理：若不同子集之間的映射選擇互相獨立，總的函數個數等於各子集的選擇數乘積。

---

解題方法

1. 確認每條原像條件的意義

   • $f^{-1}(\{1,3\})=\varnothing$：沒有 任意 $x\in A$ 可以使 $f(x)=1$ 或 $f(x)=3$。因此 $1,3$ 兩個值在值域中必不可被映射。
   • $f^{-1}(\{4,6\})=\{1,3,7\}$：恰好 $1,3,7$ 這三個定義域元素的函數值落在 $\{4,6\}$ 之內；其他元素不可映至 $4$ 或 $6$。
   • $f^{-1}(\{7,9\})=\{8,9\}$：恰好 $8,9$ 兩個元素的函數值落在 $\{7,9\}$ 之內；其餘元素不可映至 $7$ 或 $9$。

2. 將 $A$ 分割

題目中的 $L$ 定義有缺漏；以下依合理還原

$$L=\bigcup_{i=1}^{8}\Sigma^i$$

計算。

長度為 $n$ 的字串中，固定一次出現子字串 $\text{bay}$，共有 $(n-2)4^{n-3}$ 種。兩次出現時起始位置至少相隔 $3$，須用排容原理扣除：

核心觀念

本題考查離散數學與機率論中的經典模型——賭徒破產問題（Gambler's Ruin Problem）與隨機漫步（Random Walk）。主要運用以下定義與定理：

1. 條件期望值與全機率公式（Law of Total Probability for Expectations）：
   將當前狀態的期望值拆解為下一階段所有可能轉移狀態的期望值加權和，建立二階非齊次線性差分方程（Difference Equation）。
2. 馬爾可夫鏈（Markov Chain）之吸收態（Absorbing State）：
   當 Adam 的資金達到 $0$ 元或 $10$ 元時，遊戲立即停止，此兩狀態為吸收態，其剩餘期望遊戲次數為 $0$。

---

解題方法

步驟一：定義狀態與變數
設 Adam 與 Eve 的資金總和為 $N = 5 + 5 = 10$ 元。
令 $E_k$ 表示當 Adam 擁有 $k$ 元（此時 Eve 擁有 $10 - k$ 元）時，直到其中一人輸光（即 Adam 的資金到達 $0$ 元或 $10$ 元）為止，還需要的期望遊戲次數，其中 $k \in \{0, 1, 2, \dots, 10\}$。

步驟二：建立差分方程與邊界條件
每場遊戲為公平賭局（勝率與敗率皆為 $1/2$）。當 Adam 擁有 $k$ 元（$1 \le k \le 9$）時：

• 以概率 $\frac{1}{2}$ 勝出，資金變為 $k+1$ 元；
• 以概率 $\frac{1}{2}$ 落敗，資金變為 $k-1$ 元。

進行該場遊戲耗費 $1$ 次，故由全機率公式可列出遞迴關係式：
$E_k = 1 + \frac{1}{2} E_{k+1} + \frac{1}{2} E_{k-1}, \quad \text{其中 } 1 \le k \le 9$

當資金達到邊界（吸收態）時，遊戲立即結束：
$E_0 = 0, \quad E_{10} = 0$

步驟三：求解差分方程通式
將遞迴式同乘以 $2$ 並移項整理：
$E_{k+1} - 2E_k + E_{k-1} = -2$
$(E_{k+1} - E_k) - (E_k - E_{k-1}) = -2$

令一階差分數列為 $d_k = E_k - E_{k-1}$（$1 \le k \le 10$），上式可寫為：
$d_{k+1} - d_k = -2$

此表明 $d_k$ 為公差 $-2$ 的等差數列，其一般式為：
$d_k = d_1 - 2(k - 1)$

利用累加法表達 $E_k$：
$E_k = E_0 + \sum_{j=1}^{k} d_j = 0 + \sum_{j=1}^{k} [d_1 - 2(j - 1)] = k d_1 - 2 \cdot \frac{(k - 1)k}{2} = k d_1 - k(k - 1)$

核心觀念

本題考查離散數學（Discrete Mathematics）中的古典機率（Classical Probability）、重複組合（Combination with Repetition）與排容原理（Inclusion-Exclusion Principle）（亦可用生成函數 Generating Function 求解）。

關鍵公式與定義如下：

1. 古典機率定義：
   $P(E) = \frac{|E|}{|S|} = \frac{\text{滿足條件的事件數}}{\text{所有可能的樣本點總數}}$
2. 重複組合（H）：
   將 $n$ 個相同的物件放入 $m$ 個不同的箱子中（可為空箱），非負整數解 $(y_1, y_2, \dots, y_m)$ 的組數為：
   $H^m_n = \binom{n + m - 1}{n} = \binom{n + m - 1}{m - 1}$
3. 排容原理：
   針對變數上限限制（如 $y_i \le 5$），先求出無上限下的非負整數解總數，再扣除至少有一個變數超過上限的違規組合數。

---

解題方法

步驟一：計算樣本空間總數 $|S|$

投擲 1 顆公正 6 面骰子 1 次，出現點數有 6 種可能。
連續投擲 5 次，樣本空間總數為：
$|S| = 6^5 = 7776$

步驟二：建立不定方程式與限制條件

設第 $i$ 次投擲出現的點數為 $x_i$（其中 $i = 1, 2, 3, 4, 5$），點數和為 15 的方程式為：
$x_1 + x_2 + x_3 + x_4 + x_5 = 15, \quad \text{其中 } 1 \le x_i \le 6 \quad (\forall i \in \{1,2,3,4,5\})$

為使用重複組合公式，進行變數變換。令 $y_i = x_i - 1$，則限制條件轉為 $0 \le y_i \le 5$，原式轉化為：
$y_1 + y_2 + y_3 + y_4 + y_5 = 10, \quad \text{其中 } 0 \le y_i \le 5$

步驟三：利用排容原理求非負整數解個數 $|E|$

1. 無上限限制的非負整數解總數：
   $N_{total} = H^5_{10} = \binom{10 + 5 - 1}{10} = \binom{14}{4} = \frac{14 \times 13 \times 12 \times 11}{4 \times 3 \times 2 \times 1} = 1001$

2. 扣除違規解（至少有一個 $y_i \ge 6$）：
   若某變數 $y_i \ge 6$，令 $y_i' = y_i - 6 \ge 0$，方程式變為：
   $y_1 + \dots + y_i' + \dots + y_5 = 10 - 6 = 4$

   • 選擇哪一個變數違規（$y_i \ge 6$）共有 $\binom{5}{1} = 5$ 種選擇。

核心觀念

本題考查：

• 合取：$q \land r$、$p \land r$
• 否定：$\neg(p \land r)$
• 蘊涵：$A\to B$ 僅在 $A$ 為真且 $B$ 為假時為假
• 雙條件：$A\leftrightarrow B$ 在 $A$、$B$ 真值相同時為真

題目中的符號 $q^r$ 表示 $q\land r$，$-(p^r)$ 表示 $\neg(p\land r)$。因此原命題為

$$p\leftrightarrow\left[(q\land r)\to\neg(p\land r)\right]$$

解題方法

先依照運算層次，由內而外建立欄位：

1. 計算 $q\land r$
2. 計算 $p\land r$
3. 計算 $\neg(p\land r)$
4. 計算 $(q\land r)\to\neg(p\land r)$
5. 最後計算 $p\leftrightarrow\left[(q\land r)\to\neg(p\land r)\right]$

真值表

$p$	$q$	$r$	$q\land r$	$p\land r$	$\neg(p\land r)$	$(q\land r)\to\neg(p\land r)$	$p\leftrightarrow[(q\land r)\to\neg(p\land r)]$
T	T	T	T	T	F	F	F
T	T	F	F	F	T	T	T
T	F	T	F	T	F	T	T

任取 Adam，考慮他與其餘 $5$ 人的關係。由鴿籠原理，其中至少有 $3$ 人同時與 Adam 相識，或至少有 $3$ 人同時與 Adam 陌生。

設這 $3$ 人為 $X,Y,Z$。