横浜国立大学 2022年度理系数学第2問解答・解説

問題

$n$ を自然数とする。 $x y$ 平面上を動く点 $P$ があり、1回の移動で次の(L)、(R)のいずれかによって、 $P$ は移動する。

⎩ ⎨ ⎧ 点 P が (x, y) にあるとき、 (L) (x - 1, y - 1) に移動する (R) (x + 1, y - 1) に移動する

はじめ $P$ は原点 $(0, 0)$ にあり、この移動を $n$ 回繰り返す。このとき、 $k = 1, 2, \dots, n$ に対して、 $P$ が $k$ 回移動した後の $x$ 座標を $x_{k}$ とおく。

例えば $n = 2$ のとき、 $P$ は「(L),(R)」の順に従って移動すると、 $(- 1, - 1), (0, - 2)$ の順に移動する。また $P$ の移動の仕方は、「(L),(L)」、「(L),(R)」、「(R),(L)」、「(R),(R)」のそれぞれに従って移動する4通りある。さらに、 $x_{2} ≦ 0$ をみたす $P$ の移動の仕方は、「(L),(L)」、「(L),(R)」、「(R),(L)」のそれぞれに従って移動する3通りある。

次の問いに答えよ。

(1) $n = 4$ のとき、 $x_{k} ≦ 0$ （ $k = 1, 2, 3$ ）かつ $x_{4} = 0$ をみたす $P$ の移動の仕方は何通りあるか。

以下、 $n = 8$ とする。 $x_{1}, \dots, x_{8}$ の最大値を $M$ とし、 $x_{1}, \dots, x_{8}$ の最小値を $m$ とする。

(2) $- 2 ≦ m ≦ M ≦ 3$ をみたす $P$ の移動の仕方は何通りあるか。

(3) $m = - 2$ かつ $M ≦ 3$ をみたす $P$ の移動の仕方は何通りあるか。

(4) $m = - 2$ かつ $1 ≦ M ≦ 3$ をみたす $P$ の移動の仕方は何通りあるか。

出典：横浜国立大学 2022年度前期理系第2問

方針

移動は $x$ 座標だけを見ると、Lで $- 1$ 、Rで $+ 1$ する1次元の移動である。(1)は短いので直接列挙する。(2)以降は、時刻 $k$ に位置 $j$ にいて、指定範囲から出ていない移動の通り数を表で更新する。(3)(4)は、範囲に入る総数から、下端や上端に到達しない場合を引く。

解答

(1)

$x_{4} = 0$ となるには、LとRが2回ずつ現れる必要がある。さらに $x_{1}, x_{2}, x_{3} ≦ 0$ を満たすものを調べると

LLRR, LRLR

の2通りである。

(2)

$A_{k} (j)$ を、 $k$ 回移動した後に $x$ 座標が $j$ であり、それまで常に $- 2 ≦ x ≦ 3$ を満たす移動の通り数とする。 $A_{0} (0) = 1$ から始め、範囲外を0として

A_{k + 1} (j) = A_{k} (j - 1) + A_{k} (j + 1)

で更新する。 $j = - 2, - 1, 0, 1, 2, 3$ の順に並べると、 $k = 8$ で

(28, 0, 61, 0, 47, 0)

となる。したがって求める通り数は

28 + 61 + 47 = 136

である。

(3)

(2)の136通りのうち、 $m = - 2$ となるものを数える。 $- 2$ に一度も到達しないものは、常に $- 1 ≦ x ≦ 3$ を満たす移動である。同じ更新を範囲 $- 1 ≦ x ≦ 3$ で行うと、8回後の通り数の合計は81である。よって

136 - 81 = 55

通りである。

(4)

(3)の55通りから、 $M ≦ 0$ であるものを除けばよい。 $- 2 ≦ x ≦ 0$ を満たす移動は16通りであり、そのうち $- 2$ に到達しない、すなわち $- 1 ≦ x ≦ 0$ を満たす移動は1通りである。したがって $m = - 2$ かつ $M ≦ 0$ であるものは15通りである。よって求める通り数は

55 - 15 = 40

である。

横浜国立大学 2022年度理系数学 第2問

問題

方針

解答

(1)

(2)

(3)

(4)

横浜国立大学 2022年度
理系数学第2問