Question

高校生

(3)矢印の位置とかは、考えなくていいのですか？どう考えれば、解説にあるような場合分けになるのか教えてください。

B.
A
右の図において, P地点からQ地点に達する最短経路
について考えよう。
(1) P地点から, A地点を通り, Q 地点に達する最短
経路はアイウ通りある。
(2) P地点から, B地点を通り, Q地点に達する最短
経路はエオ通りある
P
(3) P地点からQ地点に達する最短経路は全部でカキク 通りある。
0
(解説
右下の図のように, 点 B', B", C, D, E を定める。
5!
(1) P地点からA地点に達する最短経路は
=5 (通り) E
4!1!
6!
C B
[B
A地点からQ地点に達する最短経路は
-20 (通り)
3!3!
B
LA
よって, P地点から, A地点を通り, Q地点に達する最短
P
経路は
5×20=100 (通り)
4!
(2) P地点からB' 地点に達する最短経路は
=4(通り)
3!1!
B'地点からB地点, B地点からB地点に達する最短経路はそれぞれ
5!
B地点からQ地点に達する最短経路は
-=10(通り)
3!2!
よって, P地点から, B地点を通り, Q地点に達する最短経路は
4x1x1×10=40 (通り)
1通
(3) P地点から, C地点を通り, Q地点に達する最短経路は
4! 7!
=28(通り)
1!3! 6!1!
6!
P地点から, D地点を通り, Q地点に達する最短経路は
=15(通り)
2!4!
P地点から, E地点を通り, Q 地点に達する最短経路は
ゆえに, P地点からQ地点に達する最短経路は全部で
100 +40 +28 +15+1=184 (通り)
トークルーム
小間アート
この回答にコメントする
Q&A
マイページ
閉じる

Answer 1

✨ Jawaban Terbaik ✨

和

「矢印の位置」がよくわからないのですが、
すべての最短経路は
・A〜Eのどれかは必ず通る
・A〜Eは、2点以上は通らない
ので、この5パターンを足し合わせればよいのです

斜めの切り方は他にもありますが、
これが自然な切り方の一つです
(1)(2)を活かす意味も込んでいます

高校生

解答ありがとうございます！
どうやって斜めの線を考えればいいのですか？他の問題でも、解けるようにしたいので、やり方教えて欲しいです。

高校生

解決しました！

高校生

ありがとうございます！

和

おおまかには、進行方向P→Qに対して
大体垂直の方向に斜めに引けば
ある程度うまくいきます

ここではECとBADは一直線上にはありませんが
それもどうでもよいことです

細かくは、「斜め線と格子の交点」について、
・すべての道が、交点のどれかしらを通る
・交点の1点だけを通る（複数を通らない）
ように引けば、なんでもいいです