A町、B町、C町、D町が図のように道でつながっている。A町からD町まで行き、帰りは行きに使った道を使わずにA町まで戻る経路は何通りあるか。

1. 問題の内容

A町、B町、C町、D町が図のように道でつながっている。A町からD町まで行き、帰りは行きに使った道を使わずにA町まで戻る経路は何通りあるか。

2. 解き方の手順

A町からD町への行き方を数え、それぞれの行き方に対して、帰りの経路が何通りあるかを考える。

* A町からD町への行き方：

* A→B→C→D（最短経路）の行き方は、(A→Bの道) x (B→Cの道) x (C→Dの道) で計算できる。

* A→Bは3通り

* B→Cは2通り

* C→Dは3通り

* したがって、A→B→C→Dは $3 \times 2 \times 3 = 18$ 通り

* それぞれの行き方に対する帰りの経路：

D町からA町への帰りの経路は、行きに使った道を使わないため、D→C、C→B、B→Aのそれぞれで、行きに使った道以外の道を選ぶ必要がある。

*　A→B→C→Dの経路を行きに使った場合、D→C、C→B、B→Aのそれぞれで、行きに使った道以外の道を選ぶので。

* D→Cは2通り

* C→Bは1通り

* B→Aは2通り

* したがって、$2 \times 1 \times 2 = 4$ 通り

* 往復の経路の総数：

行きが18通り、それぞれに対して帰りが4通りなので、$18 \times 4 = 72$通り

3. 最終的な答え

72通り