去程與回程的線路安排問題

=問題=

從甲地到乙地有 $12$ 條道路，其中有 $5$ 條雙向道， $4$ 條由甲地到乙地的單行道， $3$ 條由乙地到甲地的單行道。求從甲地到乙地再回到甲地，且去程與回程走不同的路，共有多少種路線安排？

=解答=

$(1^\circ)$ 符號化與道路分類

首先，我們將這 $12$ 條道路在「去程」與「回程」時的可用性，進行精簡的符號化分類：

• $A$（雙向道）：共 $5$ 條。（去程、回程皆可通）
• $B$（甲 $\rightarrow$ 乙 單行道）：共 $4$ 條。（僅去程可通）
• $C$（乙 $\rightarrow$ 甲 單行道）：共 $3$ 條。（僅回程可通）

這時，我們可以很清晰地列出「去程」與「回程」的可選路徑範圍：

• 去程只能選擇：$A$ 或 $B$
• 回程只能選擇：$A$ 或 $C$

$(2^\circ)$ 分類討論

由於題目規定「去程與回程走不同的路」，我們依據「去程選什麼路 $\rightarrow$ 回程選什麼路」的決策順序，將所有可能的情境拆解為以下四種互斥的走法：

【第一類：$A \rightarrow A$】去程走雙向，回程也走雙向

• 去程：有 $5$ 條雙向道 $A$ 可以選擇。
• 回程：因為去程已經走過其中 $1$ 條雙向道，且去回不能重複，所以回程可選的雙向道只剩下 $5 - 1 = 4$ 條。
• 此類走法：根據乘法原理，共有

$$5 \times 4 = 20 \text{ 種}$$

【第二類：$A \rightarrow C$】去程走雙向，回程走單行

• 去程：有 $5$ 條雙向道 $A$ 可以選擇。
• 回程：回程選擇的是乙 $\rightarrow$ 甲的單行道 $C$（共 $3$ 條）。因為去程走的是 $A$，回程走的是 $C$，兩者完全沒有交集，所以不需要扣除任何路徑。
• 此類走法：根據乘法原理，共有$$5 \times 3 = 15 \text{ 種}$$

【第三類：$B \rightarrow A$】去程走單行，回程走雙向

• 去程：選擇甲 $\rightarrow$ 乙的單行道 $B$（共 $4$ 條）。
• 回程：選擇雙向道 $A$（共 $5$ 條）。因為去程完全沒有走過雙向道 $A$，所以回程的 $5$ 條雙向道皆可自由挑選，不需扣除。
• 此類走法：根據乘法原理，共有$$4 \times 5 = 20 \text{ 種}$$

【第四類：$B \rightarrow C$】去程走單行，回程也走單行

• 去程：選擇單行道 $B$（共 $4$ 條）。
• 回程：選擇單行道 $C$（共 $3$ 條）。去程與回程所選的道路集合完全互斥。
• 此類走法：根據乘法原理，共有$$4 \times 3 = 12 \text{ 種}$$

$(3^\circ)$ 匯整結果

上述四種情境彼此互斥，由加法原理，我們將四種情境的所有可能走法相加，即為最終所有的線路安排總數：

$$20 + 15 + 20 + 12 = 67 \text{ 種}$$

（解答終了）

已知集合差集關係，求參數$a$值

=題目= 

已知 $a$ 為整數， $A = \{ 5, 7, a^2+4a+7 \}, B = \{ 7, 3, 2 \}$，且 $A - B = \{ 5 \}$，試求實數 $a$ 的值。

=答案=

$a = 0, -4, -2$

=詳解=

由於集合的寫法允許元素重複出現，所以集合 $A$ 雖然寫成$\{ 5, 7, a^2 + 4a + 7 \}$看起來是3個元素，但可能重複，也就是說，帶有未知數 $a$ 的式子 $a^2 + 4a + 7$ 可能是5，也可能是7，也可能不是5也不是7。

所以我們分成以下3種情形進行討論。

情形1：$a^2 + 4a +7 = 5$

此時有 $a^2 + 4a + 4 = 2$，因式分解得 $(a + 2)^2 = 2$，解出 $a = -2 \pm \sqrt{2}$。但這與題目條件「已知 $a$ 為整數」矛盾，因為無論是 $-2 + \sqrt{2}$ 還是 $-2 - \sqrt{2}$都不是整數。所以此情形不成立。

情形2：$a^2 + 4a +7 = 7$

此時有 $a^2 + 4a = 0$，因式分解得 $a(a + 4) = 0$，解出 $a = 0, -4$。

接著再細分2個子情形繼續討論。

    情形2.1：$a = 0$

    此時 $A = \{ 5, 7, 7 \} = \{ 5, 7 \}$，然後 $A \cap B = {7}$，確實有 $A - B = \{ 5 \}$，滿足題目條件。

    情形2.2：$a = -4$

    此時 $A = \{ 5, 7, 7 \} = \{ 5, 7 \}$，然後 $A \cap B = {7}$，確實有 $A - B = \{ 5 \}$，滿足題目條件。

情形3：$a^2 + 4a +7 \ne 5$，且$\ne 7$

此時集合 $A$ 確實有3個元素。因為 $A - B = \{ 5 \}$，所以表示 $A$ 中的3個元素中，除了5之外，另外2個元素必然也是 $B$ 的元素。所以 $a^2 + 4a + 7 \in B$。

此時又要再細分2個子情形繼續討論。

    情形3.1：$a^2 + 4a + 7 = 3$

    此時有 $a^2 + 4a +4 = 0$，因式分解得 $(a + 2)^2 = 0$，解出 $a = -2$。

    情形3.2：$a^2 + 4a + 7 = 2$

    此時有 $a^2 + 4a + 4 = -1$，因式分解得 $(a + 2)^2 = -1$，此方程式無解。

綜上所述，$a = 0, -4, -2$

一道排列組合的問題（2020，印度理工學院，Main, 5 Sep II）

 ==問題== 

某份試卷分為3節，每節都有5道試題，考生只需在全卷中選擇5道試題作答，但規定每節都至少要選擇1題作答，請問作答方法數為

(a) 3000        (b) 1500        (c) 2255        (d) 2250

（原文）

There are 3 sections in a question paper and each section contains 5 questions. A candidate has to answer a total of 5 questions, choosing at least one question from each section. Then the number of ways, in which the candidate can choose the questions, is

(a) 3000        (b) 1500        (c) 2255        (d) 2250

==解答==

首先假定考卷所分的3節分別為A, B, C，而其中各節所含的題目又可以編號為A1, A2, ..., A5, B1, B2, ..., B5, C1, C2, ..., C5。

我們可以寫出幾種可能的作答方式，如：

A1, A3, B4, B5, C1,

A1, B5, C1, C3, C5.

等等。在處理排列組合問題時，我們必須搞題目問的是什麼，要能夠在心中明確寫出幾個題目所求的具體結果。

暫且先忽略具體選的是哪幾題，只注意所選的題目是從哪裡選出、以及選了多少題，那麼所有作答方式可分為兩大類：

(甲) 某節選3題、某節選1題、某節選1題；

(乙) 某節選2題、某節選2題、某節選1題。

對於(甲)而言，顯然又可再細分3類：

A選3題，B選1題，C選1題

B選3題，A選1題，C選1題

C選3題，A選1題，B選1題

（先處理哪部分選3題比較好做）因此能計算出(甲)的方法數一共有$C^5_3 \times C^5_1 \times C^5_1 \times 3 = 750$種方法。

對於(乙)而言，顯然又可再細分3類：

A選1題，B選2題，C選2題

B選1題，A選2題，C選2題

C選1題，A選2題，B選2題

（先處理哪部分選1題比較好做）因此能計算出(甲)的方法數一共有$C^5_1 \times C^5_2 \times C^5_2 \times 3 = 1500$種方法。

綜上所述，所求方法數為$750 + 1500 = 2250$種，選(d)。

（解答終了）

110年學測試辦考試，數學單選5，壽司

==問題== 

甲、乙、丙三人到旋轉壽司餐廳用餐。餐廳現有10種壽司，每種壽司僅剩2盤。假設每種壽司每個人至多只能拿1盤，用完餐後發現每種壽司都至少有人拿了1盤。試問三人拿取壽司的組合共有幾種？

(1) $2^{10}$    (2) $5^{10}$    (3) $6^{10}$    (4) $7^{10}$    (5) $8^{10}$

==解答==

假設壽司種類為$a_1, a_2, \cdots, a_{10}$。

單以第1種壽司$a_1$而論，根據題目條件，被拿取的可能盤數為1或2。如果是被拿1盤，那麼就是甲、乙、丙三人之中一人所取，因此有${3 \choose 1} = 3$種可能；如果是被拿2盤，那麼就是甲、乙、丙三人之中的兩人所取，因此有${3 \choose 2} = 3$種可能。由加法原理知，$a_1$壽司的分配方法一共有$3+3=6$種可能。

對於其他壽司$a_2$、$a_3$、...、$a_{10}$討論的方法也都相同，所以各別亦都是6種可能性。

從$a_1$開始逐步分配，直到$a_{10}$分完為止，依據乘法原理，一共有$\underbrace{6 \times 6 \times \cdots \times 6}_{10{\text 個}} = 6^{10}$種方法。所以選(3)。

（解答終了）

2020-03-12，數碼個數問題

==問題==

從0寫到9999，請問一共寫了多少個5？

（譬如從0寫到20，會寫出0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20，其中5和15各別寫了1次5，所以從0寫到20一共寫了1+1=2次5。）

==引導==

我們先按位數多寡分類，然後再按出現5的個數細分。

一位數，恰出現1個5，有          個數，共寫了          次5。

二位數，恰出現1個5，☐5，有          個數，共寫了          次5。

                                        5☐，有          個數，共寫了          次5。

                恰出現2個5，55，有          個數，共寫了          次5。

三位數，恰出現1個5，☐☐5，有          個數，共寫了          次5。

                                        ☐5☐，有          個數，共寫了          次5。

                                        5☐☐，有          個數，共寫了          次5。

                恰出現2個5，55☐，有          個數，共寫了          次5。

                                        5☐5，有          個數，共寫了          次5。

                                        ☐55，有          個數，共寫了          次5。

                恰出現3個5，555，有          個數，共寫了          次5。

四位數的情況不多寫了，留給讀者自己完成。

==答案==

4000個

==另解==

\begin{eqnarray*} &&{4 \choose 1} \times 1 \times 9 \times 9 \times 9 \color{red}{\bf \times 1} + {4 \choose 2} \times 1 \times 1 \times 9 \times 9 \color{red}{\bf \times 2}+ {4 \choose 3} \times 1 \times 1 \times 1 \times 9 \color{red}{\bf \times 3} + {4 \choose 4} \times 1 \times 1 \times 1 \times 1 \color{red}{\bf \times 4} \\ &=& 2916 + 972 + 108 + 4 \\ &=& 4000 {\text{個}} \end{eqnarray*}

2018-01-18：103學測，選填F，平面拼鋪問題

=問題=

一個房間的地面是由12個正方形所組成，如圖。

今想用長方形瓷磚舖滿地面，已知每一塊長方形瓷磚可以覆蓋兩個相鄰的正方形，即

或。

則用6塊瓷磚舖滿房間地面的方法有多少種？

[103，學測，選填F]

=解法=

定義

為第I型磁磚；

為第II型磁磚。

觀察所要鋪設的區域，設左下角的兩塊為A和B，如圖所示。

A和B覆蓋的情況有2種可能，如圖所示。

如果是

那麼只要考慮上半部即可。

假定使用了$x$個第I型、$y$個第II型。那麼由橫向的個數可得方程式
$$
2x+y=5.
$$
討論此方程式的整數解有：$(x, y) = (0, 5), (1, 3), (2, 1)$。

對於$(x, y) = (0, 5)$，此時的拼貼方式有$\frac{5!}{5!}=1$種。如圖所示。

對於$(x, y) = (1, 3)$，此時的拼貼方式有$\frac{4!}{3!}=4$種。如圖所示。

對於$(x, y) = (2, 1)$，此時的拼貼方式有$\frac{3!}{2!}=3$種。如圖所示。

綜合上述，如果A和B係由第I型磁磚所覆蓋，那麼總共有$1+4+3=8$種拼鋪方法。

如果是

那麼左半部必定是如下拼鋪

此時只要討論右半部即可。

假定使用了$x$個第I型、$y$個第II型。那麼由橫向的個數可得方程式
$$
2x+y=3.
$$
討論此方程式的整數解有：$(x, y) = (0, 3), (1, 1)$。

對於$(x, y) = (0, 3)$，此時的拼貼方式有$\frac{3!}{3!}=1$種。如圖所示。

對於$(x, y) = (1, 1)$，此時的拼貼方式有$2!=2$種。如圖所示。

綜合上述，如果A和B係由第II型磁磚所覆蓋，那麼總共有$1+2=3$種拼鋪方法。

我們必須要留心，以上所列舉出的拼鋪方式，是否有滿足題目所限定的「用6塊瓷磚」。而我們的答案是沒問題的。

所以本題答案為$8+3=11$種。