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 (通り)

場合の数

Answer 1

✨ ベストアンサー ✨

すけ

点A、Bを通るときは既に求めてあるので、
点A、Bを通らないときを考えています。

点Pから点A、Bに行くには、経路がない部分を通り過ぎる前に右に2マス以上進む必要があります。
経路がない部分を通り過ぎる前に、右に1マスだけ進んだときは必ず点Cを通ります。
そして、経路がない部分を通り過ぎる前に右に進まなかった場合は必ず点Eを通ります。
そして、点Pから右に進み続けて点A、Bを通らないときは必ず点Dを通ります。

よって、点C～Eをその位置に取れば、点Pから点Qまで行くときに必ず点A～Eのどこかを通ります。
それぞれを通る場合を計算し、その和を求めれば良いということになります。

yaku

回答いただきありがとうございます。
点C、Eを取るところまでは納得できたのですが、
Dを取るときに例えばDの隣の点やその隣の点を取って考えるのはなぜできないのか教えていただきたいです🙇🏻‍♀️

すけ

例えば点Dを解説にある点の位置から1つ右にズラしたとすると、点A～Eを通らずにQまで行ける道ができてしまいます。(解説にある点Dを通る道)
このような事態を避けるため、点Dはそこにいる必要があります。

すけ

他に質問がなければ解決済みにしてください。

yaku

遅くなり申し訳ないです。
理解できました。ご丁寧にありがとうございます。