京都大学 1992年度後期・文理共通数学後期文系第3問・理系第2問解答・解説

問題

一辺の長さが $n$ の立方体 $A B C D - P QR S$ がある．ただし，2つの正方形 $A B C D$ ， $P QR S$ は立方体の向かい合った面で $A P$ ， $B Q$ ， $C R$ ， $D S$ は，それぞれ，立方体の辺である．
立方体の各面は一辺の長さ1の正方形に碁盤目(ごばんめ)状に区切られているとする．そこで，頂点 $A$ から頂点 $R$ へ碁盤目上の辺をたどっていくときの最短径路を考える．

(1) 辺 $B C$ 上の点を通過する最短径路は全部で何通りあるか．

(2) 頂点 $A$ から頂点 $R$ への最短径路は全部で何通りあるか．

出典：京都大学 1992年度後期日程第2次学力試験後期・文理共通後期文系第3問・理系第2問

方針

格子路を $x, y, z$ 各方向の単位移動の語として表す。表面上に留まるには、第3種類目の方向が初めて現れるまでに、先の2方向の一方が $n$ 回完了している必要がある。(1)は指定辺へ初めて到達する位置で分け、(2)は最後に現れる方向を選んで数える。

解答

座標を

A = (0, 0, 0), B = (n, 0, 0), C = (n, n, 0), R = (n, n, n)

とする。最短経路は正の $x, y, z$ 方向の移動を各 $n$ 回行う長さ $3 n$ の経路である。

(1)

辺 $B C$ を通るには、最初の $z$ 方向移動より前に $x$ 方向移動を $n$ 回終える必要がある。 $n$ 回目の $x$ 移動の前に $y$ 移動が $j$ 回あるとすると、そこまでの並べ方は

_{n + j - 1} C_{j}

通り、その後の $n - j$ 回の $y$ 移動と $n$ 回の $z$ 移動の並べ方は

_{2 n - j} C_{n}

通りである。よって

j = 0 \sum n_{n + j - 1} C_{j}_{2 n - j} C_{n} =_{3 n} C_{n}

通りである。最後の等式は積を「 $n$ 個の $x$ の最後の位置」で分類するVandermonde型の数え上げである。

(2)

3方向のうち最後に初めて現れる方向を選ぶ方法は3通りである。例えば $z$ が最後とする。最初の $z$ より前には $x, y$ がともに現れ、どちらか一方はすでに $n$ 回現れている。

$x$ が $n$ 回、 $y$ が $j$ 回 $(1 ≦ j ≦ n)$ 現れてから最初の $z$ が現れる経路数は

_{n + j} C_{j}_{2 n - j - 1} C_{n - 1} .

$x, y$ を入れ替えたものを2倍し、両方が $n$ 回の場合の重複 $_{2 n} C_{n}$ を引く。ここで

j = 0 \sum n_{n + j} C_{j}_{2 n - j - 1} C_{n - 1} =_{3 n} C_{n}

であり、 $j = 0$ の項は $_{2 n - 1} C_{n - 1} = \frac{1}{2}_{2 n} C_{n}$ である。従って最後の方向を固定した個数は

2 (_{3 n} C_{n} - \frac{1}{2}_{2 n} C_{n}) -_{2 n} C_{n} = 2 (_{3 n} C_{n} -_{2 n} C_{n}) .

求める総数は

6 (_{3 n} C_{n} -_{2 n} C_{n}) .

京都大学 1992年度後期・文理共通数学 後期 文系第3問・理系第2問

問題

方針

解答

(1)

(2)

京都大学 1992年度
後期・文理共通数学後期文系第3問・理系第2問