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

核心觀念

拓樸排序是將有向無環圖的頂點排成線性次序，且每條有向邊的起點都必須排在終點之前。題目要計算符合指定條件的拓樸排序數，占全部拓樸排序數的比例。

解題方法

由圖可讀出限制：$A\to B$、$B\to C,D$、$C,D\to E$、$C\to F$，以及 $D,E,F\to G$。因此 $A$ 必定最先，$B$ 次之，$G$ 必定最後。只需排列中間的 $C,D,E,F$，並遵守：

• $C,D$ 都在 $E$ 之前；
• $C$ 在 $F$ 之前。

符合這些限制的中間排列共有五種：

核心觀念

本題屬於組合計數與排列（Combinatorics and Permutations）的綜合應用題，核心觀念包含以下三項：

1. 組合公式（Combinations）：從 $n$ 個相異元素中取出 $k$ 個元素（不考慮順序）的方法數為：
   $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
2. 排列公式（Permutations）與限制條件：將選出的元素進行相異位置填入。對於形成的「四位數（Four-digit number）」，其最高位（千位數）不得為 $0$。
3. 加法原理與乘法原理（Addition and Multiplication Principles）：
   • 乘法原理：完成一個動作若需分階段進行，總方法數為各階段方法數相乘。
   • 加法原理：若解法劃分為若干互斥情況（Mutually Exclusive Cases），總方法數為各情況方法數相加。

---

解題方法

本題目標為從奇數集合 $\{1, 3, 5, 7, 9\}$ 選取 $2$ 個數字，從偶數集合 $\{0, 2, 4, 6\}$ 選取 $2$ 個數字，並組成數字不重複的有效四位數。

步驟一：計算選取數字組合的可能數

• 奇數選取：從 $5$ 個奇數中任意選取 $2$ 個，組合數為：
  $\binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$
• 偶數選取：從 $4$ 個偶數中任意選取 $2$ 個，組合數為：
  $\binom{4}{2} = \frac{4 \times 3}{2 \times 1} = 6$

步驟二：考慮數字 $0$ 對四位數首位的限制，劃分情況討論

由於選出的偶數中可能包含 $0$，而 $0$ 不能放在四位數的千位（最高位），因此將排列情況依「是否選到數字 $0$」分為兩類：

情況一：選取的 $2$ 個偶數中「不包含」數字 $0$

1. 選數方式：
   • 奇數：從 $\{1, 3, 5, 7, 9\}$ 選 $2$ 個，共 $\binom{5}{2} = 10$ 種。
   • 偶數：從非零偶數 $\{2, 4, 6\}$ 中選 $2$ 個，共 $\binom{3}{2} = 3$ 種。
   • 選數組合總數：$10 \times 3 = 30$ 種。
2. 排列方式：
   • 由於選出的 $4$ 個數字皆非 $0$，任意排列皆可形成有效的四位數。
   • $4$ 個相異數字的全排列數為 $4! = 24$ 種。
3. 情況一方法數：
   $30 \times 4! = 30 \times 24 = 720$

情況二：選取的 $2$ 個偶數中「包含」數字 $0$

1. 選數方式：
   • 奇數：從 $\{1, 3, 5, 7, 9\}$ 選 $2$ 個，共 $\binom{5}{2} = 10$ 種。
   • 偶數：固定包含 $0$，另一個偶數從 $\{2, 4, 6\}$ 選 $1$ 個，共 $\binom{3}{1} = 3$ 種。
   • 選數組合總數：$10 \times 3 = 30$ 種。
2. 排列方式：

已知 $x = 19$，求 $2^{217} \pmod{19}$。

【核心觀念：費馬小定理 (Fermat's Little Theorem)】

若 $p$ 為質數且 $\gcd(a, p) = 1$，則 $a^{p-1} \equiv 1 \pmod p$。

---

【推導過程】

因為 $R$ 為含單位元（identity）之可交換環（commutative ring with identity），且其特徵值（characteristic）為 $C(R) = 3$，故對任意 $x \in R$，皆滿足 $3x = 0$。

根據二次項定理（Binomial Theorem），在可交換環中，兩元素和的高次方可依二項式係數展開：

首先分析題目給定條件：
已知的條件式為 $(C_n^k)^{-1} = 0.7 \times (C_n^k)^{-1}$。
當 $(C_n^k)^{-1} \neq 0$ 時，同除以 $(C_n^k)^{-1}$ 會得到 $1 = 0.7$（不成立）。
因此唯一成立的條件為 $(C_n^k)^{-1} = 0$，亦即組合數 $C_n^k \to \infty$ 或者題目中將不存在的項取其倒數為 0，但在二項式係數標準定義下，欲求之五項總和可利用**曲棍球棒恆等式（Hockey-stick identity）**進行化簡：

$\sum_{i=0}^{4} \binom{m+i}{n+i} = \binom{m+5}{n+4} - \binom{m}{n-1}$

在組合學的推導與化簡中：
根據二項式係數恆等式（Hockey-stick Identity）：
$\sum_{i=0}^{k} \binom{m+i}{n+i} = \binom{m+k+1}{n+k} - \binom{m}{n-1}$

將 $k=4$ 代入求和式：
$C_m^n + C_{m+1}^{n+1} + C_{m+2}^{n+2} + C_{m+3}^{n+3} + C_{m+4}^{n+4} = \binom{m+5}{n+4} - \binom{m}{n-1}$

若從二項式遞迴關係式 $\binom{r}{k} = \binom{r+1}{k+1} - \binom{r}{k+1}$ 逐項展開：

Ans:

核心觀念

本題考查：

1. 費馬最後定理：當整數 $n>2$ 時，方程
   $x^n+y^n=z^n$
   沒有正整數解。

2. 畢氏三元組的參數表示：當 $n=2$ 時，方程為
   $x^2+y^2=z^2,$
   所有正整數解可由歐幾里得公式表示。

因此，本題必須分成 $n=2$ 與 $n>2$ 兩種情形討論。

解題方法

情形一：$n=2$

方程變為

$$x^2+y^2=z^2.$$

先考慮互質的原始畢氏三元組，即

$$\gcd(x,y,z)=1.$$

在原始畢氏三元組中，$x,y$ 一奇一偶。令偶數者為 $y$，則由歐幾里得參數公式可得：

$$x=m^2-k^2,\qquad y=2mk,\qquad z=m^2+k^2,$$

其中

$$m>k\ge 1,\qquad \gcd(m,k)=1,$$

且 $m,k$ 一奇一偶。

若三元組不是原始的，令其最大公因數為 $d$，則

$$x=dx_0,\qquad y=dy_0,\qquad z=dz_0,$$

其中 $(x_0,y_0,z_0)$ 是原始畢氏三元組。因此所有正整數解皆為

$$x=d(m^2-k^2),\qquad y=d(2mk),\qquad z=d(m^2+k^2),$$

或交換 $x,y$ 的位置，其中

$$d\ge 1,\qquad m>k\ge 1,\qquad \gcd(m,k)=1,$$

且 $m,k$ 一奇一偶。

驗算如下：

$$\begin{aligned} x^2+y^2 &=d^2(m^2-k^2)^2+d^2(2mk)^2\\ &=d^2\left(m^4-2m^2k^2+k^4+4m^2k^2\right)\\ &=d^2(m^4+2m^2k^2+k^4)\\ &=d^2(m^2+k^2)^2\\ &=z^2. \end{aligned}$$

例如取 $d=1,m=2,k=1$，可得

核心觀念

1. 同餘與奇偶性分析（Modulo Arithmetic & Parity）：
   整數平方後模 $4$ 的餘數必為 $0$（偶數平方）或 $1$（奇數平方）。利用此性質可快速推斷方程式兩邊變數的同餘約束。
2. 質數與平方和定理（Sum of Two Squares Theorem for Primes）：
   若 $p$ 為形如 $4k+3$ 的質數（即 $p \equiv 3 \pmod 4$），且 $p$ 整除兩數平方和 $q^2 + r^2$，則 $p$ 必同時整除 $q$ 與 $r$（即 $p \mid q$ 且 $p \mid r$）。此結論可由勒讓德符號（Legendre Symbol）與二次剩餘（Quadratic Residue）性質證明：若 $p \nmid q$，則可推得 $-1$ 為模 $p$ 的二次剩餘，但對 $p \equiv 3 \pmod 4$ 而言，$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = -1$，產生矛盾。
3. 質數的整除定義：
   若質數 $p$ 整除質數 $q$，由於質數的正因數僅有 $1$ 與自身，且 $p > 1$，因此必有 $p = q$。

---

解題方法

將原式 $p^3 = p^2 + q^2 + r^2$ 移項改寫為：
$p^2(p - 1) = q^2 + r^2$

步驟一：討論質數 $p$ 的奇偶性

1. 若 $p = 2$：
   代入左式得 $2^2(2 - 1) = 4$。
   因 $q, r$ 皆為質數，最小質數為 $2$，故右式最小值為 $q^2 + r^2 \ge 2^2 + 2^2 = 8 > 4$，故 $p = 2$ 無解。

2. 若 $p > 2$（$p$ 為奇質數）：
   因 $p$ 為奇數，故 $p - 1$ 為偶數，推得左式 $p^2(p - 1)$ 為偶數。
   因此右式 $q^2 + r^2$ 亦必須為偶數，這代表 $q$ 與 $r$ 的奇偶性相同（同為偶質數或同為奇質數）。

步驟二：討論 $q, r$ 的奇偶性

1. 若 $q, r$ 皆為偶質數：
   唯一偶質數為 $2$，即 $q = r = 2$。
   代入右式得 $q^2 + r^2 = 2^2 + 2^2 = 8$。
   方程式變為 $p^2(p - 1) = 8$。當 $p \ge 3$ 時，$p^2(p - 1) \ge 3^2 \times 2 = 18 > 8$，無解。

2. 若 $q, r$ 皆為奇質數：
   任何奇質數平方模 $4$ 皆同餘 $1$，即 $q^2 \equiv 1 \pmod 4$ 且 $r^2 \equiv 1 \pmod 4$。
   故右式 $q^2 + r^2 \equiv 1 + 1 \equiv 2 \pmod 4$。

   檢視左式 $p^2(p - 1)$ 模 $4$ 的同餘情況：

   • 若 $p \equiv 1 \pmod 4$，則 $p - 1 \equiv 0 \pmod 4$，故 $p^2(p - 1) \equiv 0 \pmod 4$，與右式模 $4$ 同餘 $2$ 矛盾。
   • 若 $p \equiv 3 \pmod 4$，則 $p - 1 \equiv 2 \pmod 4$，故 $p^2(p - 1) \equiv 1 \times 2 \equiv 2 \pmod 4$，符合右式條件。

   因此，任何可能的奇質數解 $p$ 必須滿足 $p \equiv 3 \pmod 4$。

步驟三：利用二次剩餘性質確定變數關係

由方程式 $q^2 + r^2 = p^2(p - 1)$ 可知，$p \mid (q^2 + r^2)$。