北海道大学 1999年 文系 第4問 解説

方針・初手

東または北にしか進まないので、各経路は「東へ何回、北へ何回進むか」の並べ方に帰着する。(2) は特定の交点 $A,B$ をともに通る経路数を積で数え、(3) は通行止め区間 $a$ を通る経路数を全体から引く。

解法1

図の道路の交点に座標を入れ、$S=(0,0),\ G=(5,4)$ とする。

(1)

$S$ から $G$ へ行くには、東へ $5$ 回、北へ $4$ 回進めばよい。

したがって経路数は、$9$ 回の移動のうち北へ進む $4$ 回の位置を選ぶ組合せの数だから

$$ {}_9\mathrm{C}_{4}=126 $$

通りである。

(2)

図2より

$$ A=(3,3),\qquad B=(4,3) $$

とおける。

$S$ から $A$ へ行くには東へ $3$ 回、北へ $3$ 回進むので

$$ {}_6\mathrm{C}_{3}=20 $$

通り。

$A$ から $B$ へは東へ $1$ 回進むだけなので $1$ 通り。

$B$ から $G$ へは東へ $1$ 回、北へ $1$ 回進むので

$$ {}_2\mathrm{C}_{1}=2 $$

通り。

よって、$A$ と $B$ をともに通る経路数は

$$ 20\cdot 1\cdot 2=40 $$

通りである。

(3)

図3の $a$ は、交点 $(1,1)$ から $(1,2)$ へ向かう縦の道路部分である。

したがって、通行止め区間 $a$ を通る経路数を数えて全体から引けばよい。

$S$ から $(1,1)$ へ行く経路数は、東へ $1$ 回、北へ $1$ 回だから

$$ {}_2\mathrm{C}_{1}=2 $$

通り。

そのあと区間 $a$ を通る方法は $1$ 通り。

さらに $(1,2)$ から $G=(5,4)$ へ行くには、東へ $4$ 回、北へ $2$ 回進むので

$$ {}_6\mathrm{C}_{2}=15 $$

通り。

よって区間 $a$ を通る経路数は

$$ 2\cdot 1\cdot 15=30 $$

通り。

したがって、求める経路数は

$$ 126-30=96 $$

通りである。

解説

格子点経路は、各部分区間ごとに独立に数えて掛け合わせるのが基本である。通行止めが「点」ではなく「道路の1区間」であることを読み違えると、(3) の個数を誤るのでそこが注意点になる。

答え

(1) $126$ 通り

(2) $40$ 通り

(3) $96$ 通り