Question

@??

解説では必ず通る点をA.B.Cとしているのですがそのような点はどのようにして決めたら良いのでしょうか？

連続して並ばない文字列は何通りできるか。
(同志社大)
18 Lv.★★★
解答は38ページ
xy 平面上にx=k(kは整数) またはy=l(は整数)で定義される碁盤の
目のような街路がある。4点 (2, 2), (2, 4), (4, 2), (4, 4)に障害物があっ
て通れないとき, (0, 0) と (5, 5)を結ぶ最短経路は何通りあるか。(京都大)

象者
大2と
点
『習
18経路の問題 Lv.★★★
19
排反事象で分ける(必ず通る点で分ける), 余事象を考える, 直接数え上げる。
Process
考え方
本間のように複雑な経路の場合は, 以下の手法を組み合わせて考える。
し
て
で
解答
(1, 5)を A, (3, 3)を B, (5, 1)をC
とおく。また, (5, 5) を Gとお
G
A
5
く。
4
(i)Aを通りOからGへ最
短距離で移動する場合の数は
6C.×1=6(通り)
(i)Cを通り0からGへ最
B
排反事象で分ける
3
2
に
+C
縦·横の並びの組合
を考える
1
短距離で移動する場合の数は
5 x
4
0
1
2 3
4
6C×1=6(通り)
(道)Bを通りOからGへ最短距離で移動する場合を考える。
(2, 2) を通ってよいものとしたとき, OからBへ最短距
離で移動する場合の数は&Ca 通りであり, (2, 2)を通り, O
からBへ最短距離で移動する場合の数は4Ca×。C通りであ
10
る。
必ず通る点に着目して
したがって,(2, 2) を通らずにOからBへ最短距離で移積の法則
動する場合の数は
6Cs-4C2×2C1==8(通り)
BからGへ最短距離で移動する場合の数は:Ci 通りであ
るから, Bを通り OからGへ最短距離で移動する場合の数
る
41
は
8×:Ci= 16 (通り)
(i)~(m)より,求める場合の数は
6+6+16= 28 (通り) 答
それぞれの場合の数を
たす

Answer 1

カモナス

　できるだけ場合分けが少なくなるように点を置きましょう。
　Bは3,4 4,3の出口のどちらもカバーしているので、Bは3,3で確定ですが、Aは2,5、Cは5,2でもOKです。

@??

Bについてなのですが、4.2を出た後5.2に行く可能性もないでしょうか？

カモナス

4,2は障害物がありますよね？

@??

なるほど！何度もすみません、3.5ではダメな理由はありますか？