京都大学 2005年度後期・文系数学後期第5問解答・解説

問題

整数格子の街路で、4点 $(2, 2), (2, 4), (4, 2), (4, 4)$ は通れない。 $(0, 0)$ と $(5, 5)$ を結ぶ最短経路は何通りあるか。

出典：京都大学 2005年度後期日程第2次学力試験後期・文系後期第5問

最短経路は右へ5回、上へ5回だけ進む。各格子点までの経路数を、左の点と下の点までの経路数の和で求め、障害点の値は0とする。

各格子点 $(x, y)$ までの最短経路数を $N (x, y)$ とする。障害点では $N (x, y) = 0$ 、それ以外では

N (x, y) = N (x - 1, y) + N (x, y - 1)

である。ただし座標軸上では、障害物に達する前の値を1とする。この規則で順に計算すると次の表を得る。 $\times$ は障害点を表す。

y \ x 543210 01111111654321 26 \times 4 \times 31 31488441 414 \times 8 \times 51 5281414661

したがって $(5, 5)$ までの最短経路は

28 通り

である。