數學-初級組合
$n, m, a \sim k$ 皆代表正整數。 我假設你已經學會集合定義、基本排列組合等基本概念。
奇偶性質
例題 1-1. 有 101 盞點亮的燈，你一次可以開啓或關閉其中的 2 盞，請問你有辦法熄滅全部的燈嗎？
解：不能。101 是奇數，而你操作 $n$ 次的情況下影響了 $2n$ 盞燈，他永遠不可能爲 101 的奇數倍數（如果是偶數倍數，那就相當於熄滅後又被點亮了）。
例題 1-2. 是否存在一條直線和一個十一邊形（複雜多邊形：可以自交也可以是凹多邊形），使得那條直線在不經過任何頂點的情況下與所有邊相交？
解：11 是奇數，因此沒辦法。
在奇數邊的情況，永遠都會有連續的 3 條邊構成左邊的形狀，無法被一條直線通過；而在偶數邊的情況，永遠都可以構造出一個多變形使得任意連續 3 條邊構成右圖的形狀，因此只要讓他們重疊，最後再首尾相連，就可以構造出能貫穿所有邊的直線。
例題 1-3. $a, b, c, d, e, f \in {1, -1}$，有多少組 $(a, b, c, d, e, f)$ 滿足 $ab + bc + cd + de + ef + fa = 0$ ？
解：$0$ 組。根據題目約束，$ab,bc,cd,de,ef,fa$ 必然有 $3$ 個 $1$ 和 $3$ 個 $-1$，因此他們的乘積爲 $(abcdef)^2=-1$，產生矛盾，$abcdef \notin {1, -1}$，因此無解。
例題 1-4. 試證在一個團體中，握手次數爲奇數次的人數一定是偶數個。（握手定理）
解：令第 $i$ 個人握手次數爲 $a_i$，則 $\sum{a_i} = 2k$，因爲握手是兩個人之間相對的行爲，你握了我，我也必然握了你，且這過程中不存在第三個人。在這個情況下，$a_i$ 是奇數的數量必然是偶數，總數才會是偶數，
例題 1-5. 試證每個碳氫化合物分子中都必然含有偶數個氫原子。
解：氫的共價鍵數爲 $+1$；碳的共價鍵數爲 $+4$，而兩個碳之間可能會有 $1$ 到 $3$ 條共價鍵，因此我們討論與碳相接的原子數量可能。有 $2$、$3$、$4$（參見乙烷、乙烯、乙炔）。而我們着重考慮 $3$，然而要成爲雙鍵必然是兩個碳原子之間，因此邊數爲 3 的碳原子數也是偶數。根據握手定理，邊數爲 1 的氫也必然是偶數個。
例題 1-6. 存不存在一個九邊形，他的每一條邊都和其他八條邊中的恰一條邊相交 (不計算頂點重合)？
解：不存在；假設存在，他就有 $9 * 1 = 9$ 個交點，那他就只有 $9 / 2 = 4.5$ 對邊會相交，矛盾。
例題 1-7. 能不能把一個凸十三邊形分成若干個平行四邊形？
解：不能。十三邊形的外圍頂點總共 13 個，而平行四邊形構成的凸多邊形的外圍只能是 $4 + 2k$ 的形式。
賦值法
例題 2-1. 用 L 型三方塊去拼 $5\times 7$ 的拼圖板，可以重疊，但不可越界，是否能讓拼圖板上每一格被覆蓋的次數相同？
解：
我們將拼圖板每一格子賦予一個值，我們會發現對於任意 L 形，他的總和是 $0$ 或是 $3$。 然而以圖中的賦值狀態來說，整個拼圖板的總和爲 $-1$，那是否可能說數個 $0$ 和 $3$ 的總和是 $-1$？不可能，因此無解。
例題 2-2. 找出所有 $n$ 使得 $n × n$ 的棋盤可以用若干個 T 型四方塊覆蓋。
解：
我們把棋盤畫成西洋棋棋盤樣。
顯然，一個 T 形方塊會包含 3 個白色和 1 個黑色，或是 1 個白色和 3 個黑色。 假設前者的 T 形方塊有 $x$ 個，後者有 $y$ 個，則： $$ \begin{matrix}3x+y=\frac{n^2}{2},x+3y=\frac{n^2}{2}\end{matrix} $$ $$3x+y=x+3y, x=y$$ $$4x=\frac{n^2}2,8x=n^2,4|n$$ 我們於是證明了如果 $n$ 不是 $4$ 的倍數，那麼不可能可以填滿；接着構造 $4\times 4$ 的棋盤，來拼湊所有 $n = 4k$ 的棋盤，就可以說明 $n = 4k$。
（我們不能直接的說明 T 形方塊是 4 格，所以 $4|n$。因爲這只能代表 $4|n^2$，所以只能得到 $2|n$ 的結論）
例題 2-3. 若一個 7 × 7 棋盤被一些 L 型三方塊和一些方型四方塊 完全覆蓋，證明方型四方塊一定只有一個。
解：
這張 7 × 7 棋盤的總和是 $1$，而對於任意 L 形，其總和是 0 或是 3；對於任意方形，其總和固定是 1。
因爲 L 形是非負，我們知道結果一定是 1 個方形搭配數個總和爲 0 的 L。
不變量
例題 3-1. 我們是否可能經過若干次下列操作將字串 ”AAB” 變換成 字串 ”ABB”：
- 將字串 S 中的一個字元 B 換成 AA，或者將一個字元 A 換成 BB
- 將字串 S 中連續三個 A 或連續三個 B 刪掉
解：不可能。定義 $f(s) = num(A) - num(B) \pmod 3$，則兩種操作，皆不會改變 $f(s)$ 的值。而我們的目標，是要將 "AAB" 轉變爲 "ABB"，即是 $f(s)$ 由 $1$ 變 $2$。
例題 3-2. 黑板上寫著 1 ∼ 100 的正整數，每次擦掉其中兩個數 $x, y$ 並把 $xy + x + y$ 寫上去，求最後一個數字的可能值。
解：這是唯一的，是 $\Pi_{i=1}^{100}{(i+1)} - 1$，因爲這個操作無關順序性，而且對於 $4$ 個數字 $a, b, c, d$ 來說，結果會是 $abcd + abc + abd + acd + bcd + ac + ad + bc + bd + ab + cd + a + b + c + d$，也就是四個數字的所有組合（去除 $1$）。
鴿籠原理
定理 4-1. 把 $𝑚$ 隻鳥放入 $𝑛$ 個籠子裡，至少有一個籠子裡至少有 $\lceil \frac{m}{n} \rceil$ 隻鳥。 定理 4-2. 把 $𝑚$ 隻鳥放入 $𝑛$ 個籠子裡，存在某一個籠子裡至多有 $\lfloor \frac{m}{n} \rfloor$ 隻鳥。
例題 4-3. 有六個人，認識的關係是互相的，證明存在三個人互相認識或互相不認識。
解：對於某個人 A，他和其它五個人都存在認識或是不認識的關係。至少存在三個人他都認識或是都不認識。假設他認識這三個人 B、C、D，若 B、C 或 B、D 或是 C、D 互相認識，則存在三人互相認識；若 B、C 和 B、D 和 C、D 都不互相認識，則滿足 B、C、D 三人互相不認識；反之亦然。
例題 4-4. 認識的關係是互相的，任意 $𝑛$ 個人中必有兩個人認識的人數相同。
解：在 $n$ 個人中，只有認識 $0$ 個人到認識 $n - 1$ 個人總共 $n$ 種可能，但認識 $0$ 個人和認識 $n - 1$ 個人是衝突的：不可能存在一個人認識其它所有人，同時，某個人不被任何人認識。因此只有 $n - 1$ 種可能，但總共卻有 $n$ 個人。
例題 4-5. 從 52 張樸克牌中最少抽出多少張牌才能保證一定會有同花順（5 張連續花色的牌）？
解：將撲克牌按照點數模五分爲五個種類，搭配四個花色，則有 20 個集合；最優解的取法是假設四個花色的餘零集合都沒有任何元素，也就是從撲克牌中拿掉所有花色的 5 和 10，因此不會出現同花順的最大牌數爲 $52 - 4\times 2 = 44$，因此答案爲 $45$。
例題 4-6. ${1, ⋯ ,50}$ 排成一數列 $a$，則存在一個長度為 8 的遞增子序列（subsequence）或遞減子序列。
解：
我們用 $a_i$ 生成兩個數列 $I_i$ 和 $D_i$，前者代表以 $a_i$ 爲結尾的最長遞增子序列的長度；後者則是以 $a_i$ 爲結尾的最長遞減子序列長度。
假設題目敘述不成立，最大長度僅爲 7，則顯然 $I_i, D_i \in {1,...,7}$，則代表 $(I_i, D_i)$ 共有 $49$ 種可能，根據鴿籠原理，必然存在某個 $i \ne j$ 使得 $(I_i,D_i)=(I_j,D_j)$。
不失一般性假設 $i < j$，倘若 $a_i > a_j$，則說明 $D_j$ 是錯的，他至少是 $D_i + 1$；倘若 $a_i < a_j$，則說明 $I_j$ 是錯的，他至少是 $I_i + 1$，因此引發矛盾。
事實上這個可以推廣，若我們想要一個長度爲 $n$ 的 ${1, 2, ..., n}$ 數列，讓他亂排，存在長度爲 $s$ 的遞增子序列和長度爲 $r$ 的遞減子序列，則 $n \ge (s - 1)(r - 1) + 1$ （Erdős-Szekeres 1935）。
賽局理論（博弈論）
一些定義：
- 一場遊戲，如果是先手必勝，我們稱呼他爲 N；反之，稱呼他爲 P。
- 我們用 $w(G) \in {N, P}$ 來描述一場遊戲 $G$。
- 對於 $G, G^\prime$，如果 $\forall H, w(G+H)=w(G^\prime+H)$，則稱 $G, G'$ 等價，標註爲 $G\equiv G'$。
Lemma 1. $w(A) = P, \forall G, G \equiv G + A$
Lemma 2. $w(G + H) = P$ 若且唯若 $G \equiv H$：考慮 $G+G+H$，分成 $(G+G)+H=H$ 和 $G+(G+H) = G$ 兩個情況討論。
例題 5-1. $n$ 堆物品，每堆有 $a_i$ 個，兩個玩家輪流取走任意一堆的任意數量物品，但不能放棄，拿走最後一個物品的人獲勝，請問先手獲勝還是後手獲勝？（Nim 遊戲）
解：
定義 $X = a_1 \oplus a_2 \oplus ... \oplus a_n$。
推導：
- 遊戲結束時，必然 $X = 0$，因爲每一項都是 $0$。
- $X=0$ 的狀態無法直接轉移到 $X = 0$ 的狀態：假設原本第 $i$ 堆有 $a_i$ 個，拿走一部分，變成 $a_i^\prime$ 個，則 $X=X\oplus a_i \oplus a_i^\prime$，其中和 $a_i$ 做 XOR 是爲了抵消它（XOR 性質之一：$a\oplus a=0$）。
- $X\ne0$ 的狀態可以直接轉移到 $X = 0$ 的狀態：假設 $X$ 的最高有效位和第 $i$ 堆的 $a_i$ 相同（必然存在這樣的 $a_i$），則在第 $i$ 堆拿走 $a_i^\prime = a_i\oplus X$，而爲什麼能說明 $a_i^\prime < a_i$ 呢？因爲 $a_i^\prime$ 的最高位比 $a_i$ 小，因此前者必然比後者小。因此，$X=X\oplus a_i \oplus a_i^\prime = 0$。
- 每個人需要盡力爭取在自己的回合中使得 $X = 0$，因爲這樣對方就無法維持 $X = 0$，也意味着對方下一局不可能獲勝。
結論：當 $X \ne 0$ 時先手必勝；當 $X = 0$ 時後手必勝。
例題 5-2. $n$ 堆物品，每堆有 $a_i$ 個，兩個玩家輪流取走任意一堆的數量不超過 $k$ 個物品，但不能放棄，拿走最後一個物品的人獲勝，請問先手獲勝還是後手獲勝？
解：
定義 $X = (a_1 \mod (k + 1)) \oplus (a_2 \mod (k + 1)) \oplus ... \oplus (a_n \mod (k + 1))$
遊戲結束時，仍然滿足 $X = 0$。因爲假設自己操作完，使得 $X = 0$，此時可能某堆還有 $k + 1$ 個東西，下個人取走任意數量個，會導致 $X \ne 0$，輪到自己時依然可以取完它，保證 $X = 0$。因此不影響結果，雙方策略仍相同。
例題 5-3. 給定一個有向無環圖，以及一個起點，上面有一個棋子，兩位玩家沿着有向邊輪流推動棋子，最後不能移動的玩家敗北。（SG 函數）
解：
先介紹一個常見函數：$\text{mex}(S) = \text{min} (x | \forall x \notin S, x \ge 0) )$ 例如 $\text{mex}({1,2,3}) = 0$， $\text{mex}({0, 1, 2, 4}) = 3$ 。
對於狀態 $x$ 以及他的後繼 ${y_1, y_2, ..., y_k}$，定義函數 $\text{SG(x)}$： $$\text{SG}(x) = \text{mex}(\text{SG}(y_1), \text{SG}(y_2), ..., \text{SG}(y_k))$$ 例如這張圖：
$\text{SG}(start) \ne 0$，我們能判斷先手必勝。注意：我們是從那些 out-degree 爲 0 的點開始往前去用拓撲排序算 SG 值。
例題 5-4. 給定 $n$ 個有向無環圖，以及一個起點，上面有一個棋子，兩位玩家可以選擇其中一個有向無環圖上的棋子做操作，沿着有向邊輪流推動棋子，最後完全不能移動的玩家敗北。（SG 定理）
解： $$\text{SG}(S) = \text{SG}(G_1)\oplus\text{SG}(G_2)\oplus...\oplus\text{SG}(G_n)$$ 若 $\text{SG}(S) \ne 0$，則先手必勝。
想法：我們把每一個 $G_i$ 轉化成一個有 $\text{SG}(G_i)$ 個物品的堆，然後來進行 Nim 遊戲，用 Nim 遊戲來模擬這樣子的公平遊戲；事實上，大多數的公平遊戲都可以彼此轉換（這邊要提到所謂的公平遊戲的定義：兩個人輪流參與、可做出的決策集合僅和當前狀態有關、遊戲以玩家無法行動結束、會在有限步驟後以非平手結束）。
例題 5-5. $n$ 堆物品，每堆有 $a_i$ 個，兩個玩家輪流取走任意一堆的任意數量物品，但不能放棄，拿走最後一個物品的人敗北，請問先手獲勝還是後手獲勝？
解：
計算 $\text{SG}(T) = a_1 \oplus a_2 \oplus ... \oplus a_n$，則
- 當 $\forall i, a_i = 1$，SG 值爲 0 則 N（先手勝），反之 P（後手勝）。
- 當 $\exists i, a_i > 1$，SG 值爲 0 則 P，反之 N。
例題 5-5. $n$ 堆物品，每堆有 $a_i$ 個，兩個玩家輪流取走任意一堆的特定數量物品，可以取走的數量在集合 $S = {s_1,s_2,...,s_k}$ 中。而且不能放棄，拿走最後一個物品的人敗北，請問先手獲勝還是後手獲勝？
解：$\text{SG}(g_i) = mex({a_i - s_j | j \in N, 1\le j \le k})$, $\text{SG}(G)=\text{SG}(g_1)\oplus\text{SG}(g_2)\oplus...\oplus\text{SG}(g_n)$ 。
排列組合
例題 6-1. Dyck 詞是一個有 $n$ 個 X 和 $n$ 個 Y 組成的字串，且所有的前綴字串皆滿足 X 的個數大於等於 Y 的個數，請計算給定 $n$ 時，有多少個 Dyck 詞。
解：
等價於在 $n\times n$ 網格中，從左下角往右上角走，每一步都只能向右或向上，並且不能越過對角線的路徑數量。
$$C_n = \binom{2n}{n} - \binom{2n}{n+1}$$
$\binom{2n}{n}$ 是從 (0, 0) 走到 (n, n) 的方法數；$\binom{2n}{n+1}$ 是從 (-1, 1) 走到 (n, n) 的方法數。
從 (-1, 1) 走到 (n, n) 的每一條路徑，都可以對應到一條越過對角線的不合法路徑。
所有越過對角線的，我們可以將它越過對角線以前的部分反轉，形成另一條路徑。
這又被稱之爲卡塔蘭數（Catalan Number），在組合數學中相當常見。
例題 6-2. 2 種顏色對 3 個珠子染色，珠子可以順時針旋轉；請問有多少種着色方式？
解：
有 3 種旋轉方式，空轉、轉一格、轉兩個。
- 空轉的不動點數目是：8（所有元素）。
- 轉一格的不動點數目是：2（000、111）。
- 轉兩格的不動點數目是：2（000、111）。
Burnside 引理：$$\frac{1}{|G|}\sum_{g\in G}{變化 g 底下的不動點}$$ 因此根據 Burnside 引理，答案是 $\frac{1}{3}(8+2+2)=4$。
