連続して並ばない文字列は何通りできるか。 (同志社大) 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 (通り) 答 それぞれの場合の数を たす