# 第三天作業

## 第一題
請算出"庭院深深深幾許"同字不相鄰排列的方法數。
:::spoiler `參考解答在這！！！`
:::success
既然題目所求為同字不相鄰，而只有 **「深」** 才有相鄰的可能。
我們不妨先將**庭**、**院**、**幾**、**許**排好，共有 $4!$ 種可能。
以上四字共有 $5$ 個間隔(包含最左邊與最右邊)，一個間隔最多只能放一個**深**，
而從 $5$ 個間隔中挑出 $3$ 個間隔的方法數為 $C^5_3$
故總方法數為 $4! \times C^5_3 = 240$ 種。
:::

## 第二題
在有 $n\times n$ 格的正方形方格紙上，能否在每一格上寫上 $1, 2$ 或 $3$ 使得每行、每列及兩條對角線上的各數之和都互不相等？

:::spoiler `參考解答在這！！！`
:::success
在任一行、列、對角線上，必有 $n$ 個數字，而由 $1, 2, 3$ 組成的 $n$ 個數的數字和有$n, n+1, n+2, \cdots, 3n$，一共有 $(3n - n) + 1 = 2n+1$ 種可能。
然而，方格紙上共有 $n$ 行、$n$ 列及 $2$ 條對角線，一共 $2n+2$ 個數字和。
由於 $2n+2 > 2n+1$ ，由鴿籠原理可知，此 $2n+2$ 個數字和必有至少 $2$ 個數字和相等。
:::

## 第三題
若集合 $\displaystyle N = \{1, 2, \cdots , 10\}$ 的三個子集 $\displaystyle A,B,C$ 滿足：
$\displaystyle |A \bigcap B| = |B \bigcap C| = |C \bigcap A| = 2$，且 $A \bigcap B \bigcap C = \emptyset$ (空集合)，
則稱 $\displaystyle (A, B, C)$ 為 $N$ 的“有序子集列”。請問 $N$ 的所有有序子集列總個數為？

:::spoiler `參考解答在這！！！`
:::success
畫圖可知：$C^{10}_2~C^{8}_2~C^{6}_2 \times 4^4 = 23040$
(圖待補)
:::

## 第四題
數字華容道是一款適合小朋友的遊戲，透過滑動數字塊，使方塊的排序恢復原位。
今有一道數字華容道的題目如下圖，則考慮這是否為一道合理的題目。
若是，請給出解法；若否，則說明理由。
:::spoiler `參考解答在這！！！`
:::success
將題目中的數字由左到右再由上而下形成一個數列，則會得到 $1, 2, 3, 4, 5, 6, 8, 7$
同樣的，歸回原位後的數列為 $1, 2, 3, 4, 5, 6, 7, 8$
每進行一次移動，則數列中的**逆序數對**或增加兩組、或減少兩組、或不增不減。
然而，題目所給的數列中只有一組**逆序數對**，因此無法恢復原為，是一道不合理的題目。
:::spoiler **逆序數對**是什麼？？？
所謂逆序數對，代表的是數列中的兩項，其項數遞增，數值卻減少，
如 $1, 2, 3, 5, 4$ 中的 $5, 4$ 就是一組逆序數對
:::

## 第五題
復旦銀行內有一個金庫，金庫上有 $N$ 道鎖。銀行有 $15$ 名董事。為了使董事們能夠相互監督，鑰匙的分配符合以下規則：
若有任意 $7$ 個董事在場，則他們的鑰匙必不足以將金庫打開；然而，當 $8$ 名董事同時到場時，他們所有人手握的鑰匙就一定可以將金庫打開。試問$N$ 至少為多少？

:::spoiler `參考解答在這！！！`
::: success
假設 $M$ 為符合題目條件的 $N$ 的最小值。將 $M$ 道鎖編號為 $1,2,\cdots,M$，董事們的編號為 $a_1,a_2,\cdots,a_{15}$
將任意 $7$ 名董事對應到一道鎖，即此七人無法開啟這道鎖，其餘八人皆可開啟，則共有 $C^{15}_7 = 6435$ 個組合，故有 $M=6435$。
以下由反證法證明$~6435~$為鎖數量下界：
若 $M < 6435$，由鴿籠原理可知，至少會有兩個 $7$ 人董事組合無法開啟同一道鎖，假設此道鎖為第 $1$ 道鎖。
注意到：任兩個組合並不會有完全相同的人，因此兩種組合的聯集至少有 $8$ 人。
因此，對於第 $1$ 道鎖，至少有一個 $8$ 人組合無法開鎖，與題目矛盾。故可知 $M=6435$，且可知每人身上皆有 $C^{15}_7 - C^{14}_6 = C^{14}_7 = 3432$ 把鑰匙，~~真是個瘋狂的數量 What a crazy quantity~~。
:::

## 第六題
六十六個人互相通信：每一個人和其他人都互相寫信。在他們的信上的有討論四種不同的話題。
每一對筆友只寫一種話題。證明至少有三個人他們筆談的是同一話題。

:::spoiler `參考解答在這！！！`
:::success
可以將這 $66$ 人看成 $66$ 個不同的點 $A_1, A_2, \cdots ,A_{66}$，其中兩兩之間都有連邊（完全圖），並用紅、橙、黃、綠四色將邊塗色。我們須說明在這樣的條件下，必存在同色的三角形。
由鴿籠原理知 $A_1$ 至少連出 $\lceil \frac{65}{4} \rceil = 17$ 個同色的邊，不妨設其連出了 $17$ 條紅邊，連接 $A_2, A_3, \cdots, A_{18}$。若 $A_2, A_3, \cdots, A_{18}$ 之間存在紅邊，則他們與 $A_1$ 連的邊形成同色三角形。否則，若這十七個點之間不存在紅邊，則他們只能以橙、黃、綠三色的邊相連接，此時由鴿籠原理，$\lceil \frac{17}{3} \rceil = 6$，不妨設 $A_2$ 與 $A_3, A_4, A_5, A_6, A_7, A_8$ 連接的邊為橙邊，若 $A_3, A_4, A_5, A_6, A_7, A_8$ 之間存在橙邊，則他們與 $A_2$ 形成同色三角形；否則，若此六個點之間不存在橙邊，則他們只能用黃、綠兩色的邊相連接，此時由範例 $2.2.$，他們之中必定存在同色三角形。 Q.E.D.
:::

## 第七題
是否能用「馬步」在每個格子僅經過一次的前提下遍歷 $4 \times 8$ 方格？
(馬步即先向左（或右）走1格，再向上（或下）走2格；或先向左（或右）走2格，再向上（或下）走1格)
:::spoiler `參考解答在這！！！`
:::success
以棋子遍歷
$<$ **顯然的塗色法** $>$
將相鄰的格子塗成黑白異色，如圖(1)。則每走一次馬步，必有 黑 -> 白 或 白 -> 黑。若起始點位於黑格，則黑格在奇數步會走到，白格在偶數步會走到；反之亦然。
$<$ **另一種塗色法** $>$
將四排中的第一排與第四排塗成紅色，第二、三排為藍色。
則位於紅色的棋子下一步必然走到藍色，顯然棋子位於藍色時亦須走到紅色( 否則走過的紅藍格數量不相等，必無法遍歷完成。)

綜合上述，若棋子第一步位於紅格內，則棋子只有在奇數步會走到紅格，但黑白塗色告訴我們：紅格範圍內有黑白兩種塗色，因此在一次的遍歷中，棋子並無法同時按照黑白塗色和紅藍塗色的方法行走，因此此題答案為 **「否」**

:::

## 第八題
某市有 $n$ 所中學，第 $i$ 所中學派出 $c_i$ 名學生 $(1 \le c_i \le 40)$ 到體育館看球賽，其中 $\displaystyle \sum^{n}_{i=1}c_i=2024$，看台上每排有 $202$ 個座位。現要求同校的學生坐在同一排。試問：最少需要安排多少排，才能使所有學生一定能夠坐下？
:::spoiler `參考解答在這！！！`
:::success
很自然地想到，若要排數最多，則每排需浪費盡可能多的座位。
注意到，$202 \div 34 = 5 \cdots 32$，$2024 \div 34 = 59 \cdots 18$，
故當有 $59$ 所學校派出 $34$ 人時，需要 $12$ 排才能坐下。

接著說明 $12$ 排必定能使所有學生坐下：
若使前十排坐下盡可能多的學生，排完後最多只剩九所學校的學生。
否則，假設還剩十所學校的學生，第一所沒辦法在第一排坐下、第二所無法在第二排坐下...第十所無法在第十排坐下，意即，若欲使他們能夠坐下，每排都會有至少 $203$ 人，即總人數至少為 $203 \times 10 = 2030$ 人，與題設矛盾。
而一排一定能坐五個學校，故共有 $12$ 排時，剩下九個學校的學生一定能坐下。
:::

## 第九題
將集合 $S = \{1, 2, \cdots , n\}$ 劃分為兩個子集 $A, B$，其中 $A \bigcup B = S, A \bigcap B = \phi$，若存在一種劃分方式，使得任一子集中任 $22$ 個元素的和（元素不必不同）不屬於該子集，求 $n$ 的最大可能值。

:::spoiler `參考解答在這！！！`
:::success
**Answer:** $n$ 的最大值為 $504$.
**Solution:**
首先說明 $n = 504$ 是可行的：
\begin{align}
\{1, 2, \cdots, 21, &484, 486, \cdots, 504\} \\
\{22, 23, &\cdots, 483 \}
\end{align}

滿足條件。

接著證明 $n$ 不能大於 $504$：
若$n$ 大於 $504$，此時不妨設 $1 \in A$，則 $22 \notin A \implies 22 \in B$.
由 $22 \in B$ 有 $484 \notin B \implies 484 \in A$.
因為 $~1 \in A, 484 \in A~$ 且 $~~21 \times 23 + 1 \times 1 = 484,~~~~ 21 \times 1 + 1 \times 484 = 505$，
得知 $23, 505$ 都屬於 $B$，但是 $21 \times 23 + 1 \times 22 = 505$，矛盾。
:::

## 第十題
令 $m$ 與 $n$ 為大於 $1$ 的正整數。在 $m \times n$ 方格紙上的每一格都有一枚背面向上的硬幣。每一步，我們一次進行以下動作：
（1）選擇一個 $2 \times 2$ 的區域；
（2）將該區域左上角與右下角的硬幣翻面；
（3）將該區域左下角與右上角的硬幣擇一翻面。
試求所有 $(m, n)$ ，使得我們能透過有限步將硬幣全部翻成正面。
(2024 Taiwan TST Round 1 Mock Exam P5)