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

核心觀念

內層迴圈每執行一次，就會執行一次 print。因此，只要逐一計算每個外層迴圈的內層執行次數，再加總即可；印出的乘積 $i \times j$ 不影響執行次數。

解題方法

(a) 當外層變數 $i$ 固定時，$j$ 從 $1$ 跑到 $i$，內層共執行 $i$ 次。總執行次數為

$$\sum_{i=1}^{567} i = \frac{567 \times 568}{2} = 161028$$

(b) 將第二行改為 $j := 1$ 到 $i^2$ 後，固定 $i$ 時，內層共執行 $i^2$ 次。總執行次數為

核心觀念

正整數 $n$ 是合數，表示 $n>1$，且存在整數 $a,b$ 滿足

$$n=ab,\qquad 1<a<n,\quad 1<b<n.$$

本題要證明：每個合數都有一個質數因數。關鍵是利用正整數的良序性，從 $n$ 的所有大於 $1$ 的正因數中，取出最小的一個。

解題方法

令 $d$ 為 $n$ 的最小正因數，且 $d>1$。這樣的因數確實存在，因為 $n$ 本身是大於 $1$ 的因數。

接著證明 $d$ 是質數。若 $d$ 不是質數，由於 $d>1$，它便是合數，因此存在整數 $r,s$ 使得

$$d=rs,\qquad 1<r<d,\quad 1<s<d.$$

核心觀念

本題考察鴿籠原理與整數的質因數分解。每個正整數 $m$ 都能唯一寫成

$$m=2^k r,$$

其中 $k\geq 0$，而 $r$ 是奇數。這裡的 $r$ 稱為 $m$ 的奇數部分。

若兩個整數有相同的奇數部分，便可寫成 $2^a r$ 與 $2^b r$。當 $a\leq b$ 時，$2^a r\mid 2^b r$，因此兩者必有一個整除另一個。

解題方法

將 $\{1,2,\ldots,336\}$ 中的每個整數，依其奇數部分分組。可能的奇數部分為

$$1,3,5,\ldots,335,$$

共 $168$ 個，也就是 $168$ 個組別。

現在從這 $336$ 個整數中選出 $169$ 個。由鴿籠原理，至少有兩個被選整數落在同一組，也就是有相同的奇數部分。設這兩個整數為 $2^a r$ 與 $2^b r$，不妨令 $a\leq b$，則

$$2^b r=2^{b-a}(2^a r),$$

所以 $2^a r\mid 2^b r$。因此所選整數中必有一對 $x,y$，使得 $x\mid y$ 或 $y\mid x$。

(b) 推廣結果

核心觀念

字串以 $xy$ 為「真前綴」（proper prefix），表示字串的前兩個字元固定為 $x,y$，且整個字串長度必須大於 $2$。字母表 $\Sigma=\{v,w,x,y,z\}$ 有 $5$ 個字元，每個後續位置都可從這 $5$ 個字元中任選。

解題方法

長度為 $n$ 的字串中，前兩個字元已固定為 $xy$，剩下 $n-2$ 個位置各有 $5$ 種選擇，因此符合條件的字串數為 $5^{n-2}$。因為總長度最多為 $8$，且必須大於 $2$，所以考慮 $n=3,4,\ldots,8$：

核心觀念

每次擲出的點數都是 $1$ 到 $6$，且 11 次擲骰彼此獨立。因此，所有有序結果等可能，總數為 $6^{11}$。所求機率等於「點數總和為 $35$ 的有序結果數」除以 $6^{11}$。

計數時使用隔板法與容斥原理：先把每次點數減去 $1$，轉成非負整數變數，再以容斥原理處理每個變數至多為 $5$ 的限制。

解題方法

令第 $i$ 次擲骰的點數為 $X_i$，並設 $Y_i=X_i-1$。則 $0\le Y_i\le5$，而

$$X_1+\cdots+X_{11}=35 \quad\Longleftrightarrow\quad Y_1+\cdots+Y_{11}=24.$$

先暫時不限制 $Y_i\le5$。由隔板法，非負整數方程式 $Y_1+\cdots+Y_{11}=24$ 的解數為

$$\binom{24+11-1}{11-1}=\binom{34}{10}.$$

接著以容斥原理排除至少一個變數大於等於 $6$ 的情形。若指定 $k$ 個變數各扣除 $6$，剩下的總和為 $24-6k$，因此該情形的解數為 $\binom{34-6k}{10}$。由於 $24-6k\ge0$，只需計算至 $k=4$：

核心觀念

這題考二階常係數非齊次遞迴關係。先解齊次遞迴式，得到通解中的指數項；再依右側常數項尋找特解，最後代入初始條件決定常數。

解題方法

先考慮對應的齊次遞迴式

$$a_{n+2}-4a_{n+1}+3a_n=0.$$

設解為 $a_n=r^n$，代入後得到特徵方程

$$r^2-4r+3=0,$$

因式分解為

$$(r-1)(r-3)=0.$$

因此齊次解為

$$a_n^{(h)}=C+D3^n.$$

原式右側為常數 $-360$。由於特徵根 $1$ 對應常數項，常數特解會與齊次解重複，因此設一次式特解

$$a_n^{(p)}=kn.$$

代入左側：

$$k(n+2)-4k(n+1)+3kn=-2k.$$

核心觀念

在 $\mathbb{Z}_{82}$ 中，$[23]^{-1}$ 是滿足 $23x\equiv 1\pmod{82}$ 的剩餘類。模反元素存在的條件是 $\gcd(23,82)=1$。歐幾里得算法可求最大公因數，並透過回代將最大公因數寫成 $23$ 與 $82$ 的整數線性組合。

解題方法

先用歐幾里得算法求最大公因數：

$$\begin{aligned} 82&=3\cdot 23+13\\ 23&=1\cdot 13+10\\ 13&=1\cdot 10+3\\ 10&=3\cdot 3+1 \end{aligned}$$

最後的非零餘數是 $1$，因此 $\gcd(23,82)=1$，反元素存在。由最後一式開始回代：

核心觀念

這題考非負整數解的計數，可用「隔板法」（Stars and Bars）。對方程式

$$c_1+c_2+c_3+c_4+c_5=n$$

其中 $c_i\geq 0$，非負整數解的數量為

$$\binom{n+5-1}{5-1}.$$

解題方法

把 $37$ 個相同的單位視為星號，並用 $4$ 個隔板分成 $5$ 組；每組星號的數量分別代表 $c_1,c_2,c_3,c_4,c_5$。某組沒有星號時，表示該變數等於 $0$，因此隔板可以相鄰，也可以出現在星號兩端。