Question

ももた

(1)と(2)で境界線を引く方向が違う((1)ではL,M (2)ではP,Q,R)なのはなんでですか？？

右図のような道路があるとき。
   二還 PからQまで,
|   大和で方が通り |
あるか調べてみましょう-   |
PからQまで最短四離で行
くには, 右に3区直, 上に2
民放汗ににのにりな
右に1区画進むことを
上に 1区進むことを†
と表すことにすると、決の図のの最短経刻を
1 で表すとそれぞれ右のようになります.

員層較 ニー
ビニ

@

 

 

 

 

 

 

    
 

 

 

 

 

最短経路の数を調べるかわりに
人記= 3個の並べ方

でこのべた
が何通りあるかを調べるのです.          人
これは
23)』
2 (り)

となります.  (同じものを含む碑)

くく” 解衝-ゝ

0 人 5Cま人
ar  =3 (通り )

ぁり, CからBまで行くには, 右図のような境晃
旭(点閑) を LL'/。 MM', NN のいずれか1 か所
すま/Gく8

4っCっ上づつ葉つっ B の経路は

3x1x1x=ちー63 (通り) ,

4

呈SU押
1   185 (通り)

有MNDET

3   69 。、更形
ET 18 (通り)

がって, Cを通る最拓経路は
6313518ニ216 (通り)

2 ペ1※

 

 

 

 

 

 

 

 

 

 

 

 

唱

をAっCは3通り
CっL, しっつじ はともにド1

通り
1
っBはgi

152 第5章 原列と組合せ
いらBま

⑫⑳ 識詳謗boとさのムツ ら
での最短経路の数を調べる・
APーPつBについて,

9!    =84G
ier21X1 84 (通り)
AつQーQつ Bについて,
8   っ4 _224G
Ti 224 (通り)
ARつR つっ Bについて,
2    DI本5
1X六50 (通り)
AつSつS*つBについで,
!   6! =と/。
1イー36 (通り)
AっエーっヤヤつBについて,
証 7 (通り)
したがって, Cを通ってもよいとしたときのAか
らBまでの最短経路の数は
84+224十350十36二7三701 (通り )
よって, Cを通らない最短経路の数は
701一216ニ485 (通り)

 

1X1X

 

で AからBまでの
を求め。 の

 

 

 

 

 

 

 

 

 

も     ko/
でいずれかでまたか
らない抽和をjl Rs
を Er  える
Qilol   B
RI
て
ET 国内
A         ゃHE

て2(④=z(の-z2)

Answer 1

✨ ベストアンサー ✨

gößt

その方が場合分けが少なくなるからです
(1)を考えると、横に区切った場合はL,Mの２つで場合分けできますが、縦に区切った場合はP,Q,Rの３つに増えます
(2)の場合は逆に横に区切ると４つになってしまいます

ももた

返信遅くなってごめんなさい…
ありがとうございます！
なんか分け方のコツとかあるんですか、？

gößt

コツというほどのコツはないですかねえ…
重複が出ないように分けられさえすれば、計算量が変わるだけで答えは出ますからあまり気にしなくてもいいかなと思います

ももた

ありがとうございます🙇‍♂️

gößt

いえいえ(｀・ω・´)