# C(組合)
## 排列組合
## 範例$1.2.$
將 $24$ 顆雞蛋分裝到紅、黃、綠的三個籃子。每個籃子都要有雞蛋，且黃、綠兩個籃子裡都裝奇數顆。請計算分裝的方法數。 $(102\ 學測)$
:::spoiler `參考解答在這！！！`
:::success
$<$ **菜鳥解法** $>$
$11 + 10 + \cdots + 1 = {1 + 11 \over 2} \times 11 = 66$

$<$ **電神解法** $>$
可以看出紅色籃子中有偶數顆雞蛋，因此可以假設紅、黃、綠中分別有 $2a, (2b - 1), (2c - 1)$ 顆雞蛋 $(a,b,c \in \mathbb{N})$，則 $2a + 2b - 1 + 2c - 1 = 24 \implies a + b + c = 13$。
於是，共有 $C^{12}_2 = 66$ 種方法。
:::

## 範例$1.3.$
將 $1$、$2$、$3$、$\cdots$、$9$ 等 $9$ 個數字排成九位數 (數字不得重複)，使得前 $5$ 位從左至右遞增、且後 $5$ 從左至右遞減。試問共有幾個滿足條件的九位數？$(112\ 學測)$
:::spoiler `參考解答在這！！！`
:::success
\begin{align*}
C^8_4 \times C^4_4 = \frac{8!}{4!4!} \times 1 = 70\\
\end{align*}
:::

## 範例$1.4.$
由 $0$ 與 $1$ 組成的 $20$ 位數的正整數中，$11$ 的倍數有多少個？$(改編自2023\ TRML)$
:::spoiler `參考解答在這！！！`
:::success
$<$ **新手解法** $>$
令 $20$ 位數 $S = \overline{a_1 a_2 a_3 \cdots a_{20}}$，其中 $a_1 = 1$。
並令奇數位為 $(a_1, a_3, \cdots,a_{19})$， 偶數位為 $(a_2, a_4, \cdots, a_{20})$
若要使 $S$ 為 $11$ 的倍數，則
\begin{align*}
(a_1+a_3+\cdots+a_{19}) - (a_2+a_4+\cdots+a_{20}) = 11k\ (k \in \mathbb{Z})\\
\end{align*}
不難得知 $k$ 必為 $0$，因此若奇數位共有 $m$ 個 $0$ ，則偶數位亦有 $m$ 個 $0$
故
\begin{align*}
所求 &= C^9_9C^{10}_9 + C^9_8C^{10}_8 + \cdots + C^9_0C^{10}_0(個).\\
\end{align*}

$<$ **進階解法** $>$
上述的方法中，有太多項要進行運算，因此，我們可以加強觀察到的性質，以此簡化計算過程，以下說明加強版的性質。

同樣令 $S = \overline{a_1a_2\cdots a_{20}}$，
並令奇數位$(a_1, a_3, \cdots,a_{19})$中有 $\alpha$ 個 $0$， 偶數位$(a_2, a_4, \cdots, a_{20})$中有 $\beta$ 個 $1$
由上述觀察性質得知：
\begin{align*}
10-\beta=\alpha \implies \alpha + \beta = 10
\end{align*}
這就相當於在 $S$ 的 $20$ 個位數中任取 $10$ 個位數。若取到奇數位，則此位數為 $0$；反之，若取到偶數位，則為 $1$。而沒取到的奇數位為 $1$、沒取到的偶數位為 $0$。
故有 $C^{20}_{10}$ 種可能。
然而，$a_1$ 必為 $1$，故所求為 $\displaystyle {C^{20}_{10} \over 2}$(個).
:::

## 範例$1.5.$
已知 $A,B,C$ 是集合 $\{1,2,...,2024\}$ 的子集，且滿足 $A \subseteq B \subseteq C$，則這樣的有序組 $(A,B,C)$ 的總數為？
:::spoiler `參考解答在這！！！`
:::success
由題可知，集合中的 $2024$ 個元素有四種狀態可以選擇。
四種狀態分別為：
1. 同時在 $A,B,C$ 中
2. 在 $A,B$ 中但不在 $C$ 中
3. 在 $A$ 中但不在 $B,C$ 中
4. 皆不在 $A,B,C$ 中

如圖所示，故所求一共有 $4^{2024}$ 種。
:::

## 範例$1.6.$
將一個正方形分割為若干$(>1)$個矩形，其中任一矩形的邊皆與正方形的邊平行。已知任意通過正方形內部且平行於正方形的邊的直線必定通過某矩形的內部（不含邊界）。試證明至少有一矩形與正方形的四邊皆不相交。 (2007 ISL C2)

:::spoiler `參考解答在這！！！`
:::success
以下所述的“內部”不包含邊界。
以下將平行於正方形的邊，與正方形內部相交，卻不與任一矩形內部相交的直線稱為“分割線”，將與正方形的四邊皆不相交的矩形稱為“哈哈”。

假設存在一種不含分割線及哈哈的分割方式。我們考慮其中使用最少矩形的方法。
注意到這種方法中任兩個矩形沒有共用邊，否則可將兩個矩形合併（如圖一），得到一個仍滿足條件且使用更少矩形的方法。

將初始的正方形設為 $ABCD$，其中 $A,B$ 分別為正方形的左下角和右下角。
現在考慮包含 $A, B$ 兩點的矩形 $a, b$（$a \neq b$，否則其上邊形成分割線），不妨設 $a$ 的高度不高於 $b$，接著考慮與 $a$ 的右下角相鄰的矩形 $c$ ，以下分兩種情況討論。

*$Case ~ 1. ~$* 如圖二，$c$ 的高度小於 $a$，此時考慮同時與 $a, c$ 相鄰的矩形 $d$，$d$ 顯然不與 $\overline{AB}, \overline{AD}, \overline{BC}$ 相交，故其必與 $\overline{CD}$ 相交，否則 $d$ 將成為哈哈，然而，此時 $c,d$ 的邊就形成了一條分割線，與假設矛盾。

*$Case ~ 2. ~$* 如圖三，$c$ 的高度大於 $a$，此時考慮同時與 $a, c$ 相鄰的矩形 $d$，$d$ 顯然不與 $\overline{AB}, \overline{AD}, \overline{BC}$ 相交（若 $d$ 與 $\overline{AD}$ 相交，則 $a$ 和 $d$ 有共用邊），故其必與 $\overline{CD}$ 相交，否則 $d$ 將成為哈哈，然而，此時 $a,d$ 的邊就形成了一條分割線，再次與假設矛盾。
:::

## 鴿籠原理

## 範例$2.2.$
證明任意六個人中必有三個人互相認識或互相不認識。

:::spoiler `參考解答在這！！！`
:::success
令此六人為 $A_1, A_2, A_3, A_4, A_5, A_6$。
由鴿籠原理知，對 $A_1$ 而言，在剩下五個人中，他/她必然認識或不認識其中三個（若認識人數大於不認識人數，則其至少認識三人，反之亦然。）不妨設 $A_1$ 認識 $A_2, A_3, A_4$，此時若 $A_2, A_3, A_4$ 中有兩人互相認識，則他/她們與 $A_1$ 形成互相認識的三人。否則，若$A_2, A_3, A_4$ 中不存在互相認識的兩人，則他們形成互相不認識的三個人。
:::

## 範例$2.3.$
是否能將 $1$ 到 $81$ 填入 $9 \times 9$ 的方格中，使得相鄰（有公共邊）的兩格之差的絕對值不大於 $5$？
:::spoiler `參考解答在這！！！`
:::success
$81$ 與 $1$ 相差 $80$，已知對角線兩端相差 $16$ 格，故他們與相鄰的格子相差必大於等於$\displaystyle \left\lceil\frac{80}{16}\right\rceil=5$。然而，由 $1$ 到 $81$ 的路徑不只一條，而任兩條不相同路徑不可填入相同數字，所以不可能達成題目所求。
:::

## 範例$2.4.$
設 $S$ 是 $\{1,2,...,2024\}$ 的任意一個 $68$ 元子集，證明：存在 $S$ 的三個互不相交的子集 $A,B,C$ 滿足 $|A| = |B| = |C|$，且 $\displaystyle \sum_{a \in A} a = \sum_{b \in B} b = \sum_{c \in C} c$.

:::spoiler `參考解答在這！！！`
:::success
考慮 $S$ 的所有三元子集，共有 $C^{68}_3 = 50116$ 個，其元素和的最小可能值為 $1 + 2 + 3 = 6$，最大可能值為 $2022 + 2023 + 2024 = 6069$。由鴿籠原理，至少有 $\lceil \frac{50116}{6064} \rceil = 9$ 個子集元素和相同，設其為 $A_1, A_2, \cdots, A_9$.
注意到這九個子集之間若有交集，則兩個子集最多交一個元素，以下分三種情況討論。
**(1)** 存在三個子集互不相交，則無須再證。
**(2)** 若九個子集兩兩之間交集不為空，則對於 $A_1$，其餘 $8$ 個子集與它恰有一個公共元素，由鴿籠原理，存在 $3$ 個子集與 $A_1$ 的公共元相同，不妨設其中兩個為 $A_2, A_3$，且他們與 $A_1$ 的公共元為 $a$，則 $A_1 \text{\\} \{a\}, A_2 \text{\\} \{a\},A_3 \text{\\} \{a\}$ 亦為 $S$ 的子集，他們兩兩的交為空集，且元素和相同。
**(3)** 若不存在三個互不相交的子集，且有兩個子集的交集為空，不妨設 $A_1 \bigcap A_2 = \phi$，則其他七個子集均至少與 $A_1, A_2$ 的其中一個交集非空，由鴿籠原理，$A_1, A_2$ 必有一個和其他四個子集有交集，不妨設 $A_1$ 與 $A_3, A_4, A_5, A_6$ 有公共元，再由鴿籠原理，這四個子集至少有兩個和 $A_1$ 有相同的公共元，不妨設 $A_3, A_4$ 和 $A_1$ 有相同的公共元 $a$，則$A_1 \text{\\} \{a\}, A_3 \text{\\} \{a\},A_4 \text{\\} \{a\}$ 亦為 $S$ 的子集，他們兩兩的交集為空集合，且元素和相同。
綜上，原命題成立。
:::

## 染色技巧
## 範例$3.2.$
能否用 $1 \times 2$ 的骨牌排滿缺失左上角及右下角的 $8 \times 8$ 棋盤？

:::spoiler `參考解答在這！！！`
:::success
不能！！！
:::

## 範例$3.3.$
有 $5\times7$ 方格紙，是否能運用 $L$ 形三格骨牌$(Tromino)$(如圖)將紙上每一格恰覆蓋三次？
若有，則畫出其中一種解法；若無，請說明原因。

:::spoiler `參考解答在這！！！`
::: success
若要將方格紙上的每一格都恰好被覆蓋三次，則共需要 ${(5\times7)\times 3 \over 3}=35$ 個 $L$ 形 $Tromino$.
然而，根據下圖可知，以下塗色的格子皆沒有辦法被同一 $Tromino$ 覆蓋，因此總共需要$(3\times4)\times3=36$ 個 $Tromino$ 才可將塗色格子覆蓋三次，與前述不符，故沒有辦法達成題目所求。
:::

## 範例$3.4.$
在 $8 \times 8$ 的棋盤左下角有個棋子，可以透過向上、右、或者向左下移動棋子，能否在任一格子僅走過一次的前提下，走遍所有的方格。
::: spoiler `參考解答在這！！！`
:::success
染三色 :+1:
:::

## 範例$4.1.$
某個委員會有 $n$ 個成員 $(n \ge 5)$ ，並且有 $n+1$ 個三人委員會，其中任兩個委員會皆不會有完全相同的成員。證明：存在兩個委員會恰好有一個成員相同。

## 範例$4.2.$
試將 $2024$ 分成若干個互不相等的正整數之和，並且使得這些正整數的乘積為最大，求此最大值。

## 範例$4.3.$
有 $2009$ 張卡片在桌子上排成一列，每張卡片有金色、黑色兩面。一開始所有卡片都是金色面朝上。兩位玩家輪流進行操作，每次操作選擇連續的 $50$ 張卡片，其中最左邊那張必須為金色面朝上，接著將他們全部翻面。最終無法進行操作的人落敗。請問誰存在必勝策略？
(2009 ISL C1)

## 範例$4.4.$
已知有三個委員會，對於任意兩個不同委員會的工作人員，第三個委員會中恰有 $10$ 個人認識他們，也恰有 $10$ 個人不認識他們。試求工作人員的總數。