Question

yaku

この問題の(3)で、解答のように点C、D、Eをどのような思考回路でとったのか分かりません。
詳しく教えていただきたいです。

○ 36 最短経路の数
0
右の図において, P地点から Q地点に達する最短経路について
考えよう。
(0) アイウ通りある。
(1) P地点から, A地点を通り,Q地点に達する最短経路は
(2) P地点から,B地点を通り, Q地点に達する最短経路は
[エオ] 通りある。
(3) P地点からQ地点に達する最短経路は全部でカキク通りある。出
H
it
制限時間15分
P
B
A
p.51 5
33 E=T=2,303

36. 《最短経路の数》
解答 (アイウ) 100
- ((思考の流れ)) -
右に1つ進むことを→上に1つ進むことを↑で表すと,
例えば,P地点から A地点までの最短経路の数は,→4
個,↑1個を1列に並べる順列の総数に等しい。
(2) B地点を通る経路は、 右の図のB'地
点, B" 地点を必ず通る。
よって, PB', B'′ → B, BB'',
(オ) 40 (カキク) 184
解答編
=20 (通り)
=
= 10 (通り)
P
B'→Qの4つに分けて考える。
B'
右下の図のように, 点 B', B'', C,D,Eを定める。
(1) P地点から A地点に達する E
最短経路は
5!
=5(通り)
4!1!
A地点から Q 地点に達する
6!
最短経路は
3!3!
よって, P地点から, A地点を
通り,Q 地点に達する最短経路は5×20=100 (通り)
(2) P地点からB'地点に達する最短経路は
4!
=4 (通り)
3!1!
B'地点からB地点, B地点から B' 地点に達する最短経
路はそれぞれ
1通り
B地点から Q 地点に達する最短経路は
5!
3!2!
よって, P地点から, B地点を通り, Q地点に達する最
短経路は
4x1x1×10=40 (通り)
(3) P地点から, C地点を通り, Q地点に達する最短経路
4! 7!
1!3! 6!1!
は
=28(通り)
×
P地点から, D地点を通り, Q地点に達する最短経路は
6!
= 15 (通り)
2!4!
Be
C B
B'
-17
B"
A
D
B"
A
P地点から, E地点を通り, Q地点に達する最短経路は
1通り
ゆえに, P地点から Q地点に達する最短経路は全部で
100 + 40 + 28 + 15+1=184 (通り)

場合の数