Question

し　【難関大学志望】

最短経路の問題です！
こう言う問題が出たときどちらのほうが楽に解けると思いますか？
今までの自分は写真の一枚目のやり方で解いていました。今後どちらの方法でこう言う問題を解けばいいのでしょうか？
写真が見づらくてすみません！

342
台の図のように,道路が基盤の目のようになった街がある。
地点Aから地点Bまでの長さが最短の道を行くとき, 次
の場合は何通りの道順があるか。
(1)全部の道順
基本 例題31 最短経路の数
『類東北大)
(2) 地点Cを通る。
3) 地点Pは通らない。(4) 地点Pも地点Qも通らない。
によって得られる。右へ1区画進むことを→,上へ1区面進むこ
とを「で表すとき,例えば、右の反のような2つの最短経路は
黒の経路なら 11→→i1→→→
赤の経路なら - t1→ー
で表される。よって、AからBへの最短経路は, →5個、16個
の同じものを含む順列 で与えられる。
(2) A→C, C→Bと分けて考える。 積の法則 を利用。
(3)(Pを通らない)=(全道順)-(Pを通る)で計算。
(4) すべての道順の集合をし, Pを通る道順の集合をP. Qを遠る道頓の集台を0ょ、
と,求めるのは
指計> AからBへの最短経路は、右の図で 右進 または 上進 すること
イド-モルガンの注意
n(Pnの)=n(PUQ)=n(U)-n(PUQ)
つまり
(PもQも通らない=(全道順)-(PまたはQを通る)
(個数定理
ここで
n(PUQ)=n(P)+n(Q)-n(PnQ)
つまり
(PまたはQを通る)=(Pを通る)+(Qを通る)-(P とQを通る)
解答
右へ1区画進むことを一,上へ1区画進むことを1で表す。
(1)最短の道順は→5個,↑6個の順列で表されるから
く組合せで考えてもよい。
次ページの国参照。
11·10-9-8-7
-=462(通り)
5!6!
5.4-3-2-1
(2) AからCまでの道順, CからBまでの道順はそれぞれ
4AからCまでで
→1個、12個
CからBまでで
→4個、14個
3!
=3 (通り),
1!2!
8!
-=70 (通り)
4!4!
よって,求める道順は
3×70=210(通り)
(3) Pを通る道順は
5!
5!
2!3!
=10×10=100 (通り)
2!3!
よって,求める道順は
462-100=362 (通り)
3!
121 -35×3=105(通り)
4(Pを通らない)
=(全体)-(Pを通る)
(4)Qを通る道順は
7!
3!4!
PとQの両方を通る道順は
5!
3!
=10×3=30(通り)
PからQに至る最短の
道順は1通りである。
2!3!
1!2!
よって, PまたはQを通る道順は
100+105-30=175 (通り)
462-175=287 (通り)
ゆえに, 求める道順は

Pを遊る道順は C2XC;=10X10=100 (通り)
1の場所から、→5個が入る場所を選ぶと考えて
=462(通り)
C。
C
この11個の に が
人る場所を選ぶと、りの
分には、1が人た。
税えば、上のに→を入れ
ると
343
からBまでは
求める道職は
C通り
x.C=3X70=210 (通り)
CXC=10X10%=100 (通り)
462-100=362 (通り)
からじまではC遊り
よって、
となる。
)書き込んで求める
うな街路で、
イつて
ト

最短経路

Answer 1

✨ ベストアンサー ✨

Clover

階乗を使っていつもどおりといたらいいとおもいますよ！計算ミスも少ないと思いますし！

し　【難関大学志望】

解答ありがとうございます！
階乗のやり方でやってみようと思います！

Clover

頑張ってください！繰り返し同じ問題を解けば自分の物にちゃんとなります！🙌