以上から、
図1と図2は碁盤の目状の道路とし、す
(1) 図1において, 点Aから点Bに行
●く最短経路は全部で何通りあるか。
また、このうち次の条件を満たすもの
は何通りあるか。
(ア) 点Cを通る。
(イ) 点Cと点Dの両方を通る。
(ウ) 点Cまたは点Dを通る。
31 べて等間隔であるとする。
12!
6!6!
A
(1) 右に1区画進むことを,上に1区画進むことを↑で表すと, |
点Aから点Bに行く最短経路の総数は, 6個のと6個の
を1列に並べる順列の総数に等しいから
=924 (通り)
4!
8!
(7) 点Cを通る最短経路は
2!2! 4!4!
点Cと点Dの両方を通る最短経路は
4!
4!
4!
×
2!2!
2!2!
2!2!
×
点Cと点Dのどちらも通らない。
(2) 図2において,点Aから点Bに行く最短経路は全部で何通りあるか。ただし、斜線の部分
は通れないものとする。
九州大
=216 (通り)
8!
4!
×
4!4! 2!2!
(2) 交差点を通過する経路の数を記入
していくと、右の図のようになる。
よって 求める最短経路の数は
132通り
=420 (通り)
(ウ) 点Dを通る最短経路は
よって、点Cまたは点Dを通る最短経路は
420+420-216624 (通り)
点CとDのどちらも通らない最短経路は
924-624=300 (通り)
A
D
=420(通り)
1 42
14 42
45 14 28
14
4259
1 2 3
B
1 1
1
•B132
132
90
48
20
6
'5
4
A
図2
B
← として求めてもよ
←A→C, C → B
←A→C, C→D,
D→B
←A → D, D→B
← (Cを通る)+(Dを通る)
(CとDを通る)
←(全体) (CまたはD
を通る)
← (1) も同様の方法で求
められる。