4山口大学 2011年 数学 第4問解答・解説

図の座標化 東西の道は6本、南北の道は10本なので、交差点を $(i,j)$（西端から東へ $i=0,1,\ldots,9$、南端から北へ $j=0,1,\ldots,5$）と表す。図から $$A=(0,0),\qquad B=(9,5),\qquad C=(5,3)$$ である。南へ進めず、同じ区間を戻れないため、各東西の道上では東または西の一方向に進み、その後に北へ進む。北へ進んだ後は別の東西の道に移るので、そこでの東西の向きは改めて選べる。

(1) 南端から2段目までの5本の東西の道それぞれについて、次に北へ進む交差点の列番号を選ぶ。各選択は $0$ から $9$ までの10通りであり、どの列からでも同じ道上を一方向に進めばその列に到達できる。5回の北進を終えて最北の道に出た後は、Bまで東へ進む方法がただ1通りである。従って $$\boxed{10^5=100000\text{通り}}.$$

(2) Cは $(5,3)$ である。第3回の北進後にいる列を $c_3$、その次の東西の道を進んでから第4回の北進をする列を $c_4$ とする。これらはそれぞれ $0,1,\ldots,9$ のいずれかであり、この道順がCを通るのは、東西の道上で列 $c_3$ から列 $c_4$ まで一方向に進む部分が列5を含むとき、すなわち5が $c_3,c_4$ の間（端を含む）にあるときである。

$(c_3,c_4)$ の全100通りから、両方とも $0$ から $4$ の25通りと、両方とも $6$ から $9$ の16通りを除く。従ってCを通る組は $$100-5^2-4^2=59\text{通り}.$$ 他の3回の列選択はそれぞれ10通りずつ独立にできるから $$\boxed{59\cdot10^3=59000\text{通り}}.$$

(3) 北への移動は5区間である。全16区間なので東西の移動は11区間となる。東を $E$ 区間、西を $W$ 区間とすると、東西方向の変位は $9$ だから $$E+W=11,\qquad E-W=9,$$ 従って $E=10, W=1$ である。

西へ進む1区間を含む東西の道を、南端から数えて $r$ 番目（南端の道を $r=0$ とする）とする。$r=0$ では西へ出られず、$r=5$ では西へ進んだ後にBへ行く東向きの移動を同じ道上に加えると戻りになるため、可能なのは $r=1,2,3,4$ である。西へ進む直前までの東向き区間数を $a$ とおくと、境界から出ないため $1\le a\le9$ である。

固定した $r,a$ について、西向きの道より前にある $r$ 本の東西の道に $a$ 個の東向き区間を配る方法は、空の道も許すので $$\displaystyle \binom{a+r-1}{r-1}$$ 通りである（$a$ 個を順に並べ、$r-1$ 本の仕切りを入れる）。西向きの道より後にある $5-r$ 本の道には $10-a$ 個を配るため $$\displaystyle \binom{(10-a)+(5-r)-1}{(5-r)-1}=\binom{14-a-r}{4-r}$$ 通りである。どの配り方も、西向きの直前の列が $1\le a\le9$ を満たす $a$、西進後の列が $a-1$ であり、残りは東向きに最終列9まで進むので、境界を越えない。従って求める数は $$\displaystyle \sum\limits _{r=1}^{4}\sum\limits _{a=1}^{9}\binom{a+r-1}{r-1}\binom{14-a-r}{4-r}.$$ 各 $r$ の小計は $$\displaystyle \begin{array}{c|c} r & \displaystyle\sum\limits _{a=1}^{9}\binom{a+r-1}{r-1}\binom{14-a-r}{4-r}\\ \hline 1&714\\2&924\\3&924\\4&714 \end{array}$$ となるから、合計は $$\boxed{714+924+924+714=3276\text{通り}}.$$