Question

れい

(3)です。どうして最短距離がC,F,Q,Kのいずれか一点を通るって分かるんですか？

を考える。
右の図1のような碁盤の目の街路があり, 点Aから点Bまでの最短経路
(1) すべての経路は アイウ 通りある。 そのうち点Pを通る経路はエオカ
通りある。
また, a 地点を通らない経路は キクケ通りある。
(2) P Q R をすべて通る経路は コサ通りある。
また、点P、Qをともに通り, 点 R を通らない経路はシス 通りある。
(3) 点Q,R,Sのどの点も通らない経路について考える。
点Q,R, S のどの点も通らないとき、図2の点C, t ,Kのうち、
いずれか1点を通り,かつ, 1点だけを通る。
次の⑩~⑥のうちから一つ選べ。
に当てはまるものを
①E
OD
②F 3 G 4 H ⑤ I 6 J
ここで,点Cを通る経路はソタ 通りあり, 点K を通る経路は
チツ通りある。
セ
A
を通る経路についても考えることにより,Q,R,
さらに,点
Sのどの点も通らない経路はテト 通りある。
SELECT
90 60
P
図1
R
SQ
a*
D
EFR
図2
GS Q
HI
B
B
J ・K
(配点 15 )
<公式・解法集 38

2! 2121
P,Qをともに通り, R を通らない経路は,Qから R を通すB
経路が1通りであるから
02.106
シス
x281=3(通り)
3! 4!
2! 2!2!
(3) 点Aから点Bまで最短経路で進
むとき、 右の図の点線上の4点C, F,
Q, K のうちのいずれか1点を通り,
O
かつ1点だけを通る。 したがって
Q, R, S のどの点も通らないとき、
C, F (②), K のうちいずれか1点 2
を通り、かつ1点だけを通る。
ここで, Cを通るのはA→C→Bと
進む経路であるから
7! x1 = 21 (通り)
2!5!
Kを通るのはA→K→Bと進む経路であるから
7!
5!2!
チツ
×1= 21 (通り)
A
6 !
2!4! ×1×1×1=15 (通り)
よって, Q, R, Sのどの点も通らない経路は
テト
21+21+15=57 (通り)
(p を満たさない場合の数)
C
E
= (すべての場合の
IG
D
F
IS
|H I
R
12
また, Q, R, S を通らず,F を通るのはA→E→F→D→Bと進む経
路であるから D
J
Point
条件を満たす最短経路の総数を求めるには、集合の考え方を利用する。
例えば、条件かがあるとき
B
K
318
TAI2