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

=問題=

從甲地到乙地有 $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{ 種}$$

（解答終了）