Question

ぴひょ

最短経路の数 書き込みで求める
(2)について○を付けたマスのところの数がそのひとつ下のコマの数と一緒になるのは何故ですか？

以上から、
図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) も同様の方法で求
められる。

A
10
O
66
図 2
$
3 4
/
22
13
F
B
65
64
141
7.9

Answer 1

✨ ベストアンサー ✨

名前なににしyo

例えば、質問者さんの図でいう丸付近の4の部分ですが
そこまで4通りであったのに、上に行く行き方は1通りに減りませんよね。上に行くのは、横と違い、下からのみですから、同じ数になります。

ぴひょ

なるほど！理解出来ました。ありがとうございます。