横浜国立大学 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問

方針

解法1（位置別の通り数を更新する方法）

$x$ 座標だけを見れば、Lは $- 1$ 、Rは $+ 1$ の移動である。区間 $[ℓ, u]$ から出ず、 $k$ 回後に位置 $j$ にいる通り数を $A_{k} (j)$ とし、 $A_{k + 1} (j) = A_{k} (j - 1) + A_{k} (j + 1)$ で更新する。必要な4区間の総数を比較して、下端・上端への到達条件を包除する。

解法2（反射法と短い区間の強制移動を使う方法）

(2)は全 $2^{8}$ 通りから、下側の境界 $- 3$ または上側の境界 $4$ に到達する経路を反射法で引く。(3)では下側境界を $- 2$ に変えた数も同様に求める。幅2以下の区間にとどまる経路は、偶数回目の選択または強制交互移動として直接数える。

解答

解法1（位置別の通り数を更新する方法）

(1)

$x_{4} = 0$ となるにはLとRが2回ずつ必要である。そのうち途中で正にならないものは

LLRR, LRLR

だから

2 通り .

(2)

$A_{k} (j)$ を、時刻 $k$ まで常に $- 2 ≦ x ≦ 3$ を保ち、 $x_{k} = j$ となる通り数とする。区間外を0と約束すれば

A_{k + 1} (j) = A_{k} (j - 1) + A_{k} (j + 1), A_{0} (0) = 1.

更新表は次の通りである。

k \ j 012345678 - 2 0010309028 - 1 0103090280 01020601906110103010033020010401404730001040140

よって

28 + 61 + 47 = 136 通り .

(3)

同じ更新により、全時刻で $[- 1, 3]$ 、 $[- 2, 0]$ 、 $[- 1, 0]$ にとどまる8歩の総数は、それぞれ $81, 16, 1$ と得られる。 $m = - 2, M ≦ 3$ は、 $[- 2, 3]$ にとどまるものから $- 2$ に一度も達しないものを引けばよい。したがって

136 - 81 = 55 通り .

(4)

(3)の55通りから $M ≦ 0$ のものを除く。 $- 2 ≦ x ≦ 0$ にとどまり、かつ $- 2$ に到達するものは

16 - 1 = 15

通りである。よって

55 - 15 = 40 通り .

解法2（反射法と短い区間の強制移動を使う方法）

(1)

4歩で原点へ戻り、途中で正にならない列は

LLRR, LRLR

のみである。よって

2 通り .

(2)

全経路は $2^{8} = 256$ 通りである。 $- 3$ に達する経路を、初めて $- 3$ に達したところで反射して数えると74通り、 $4$ に達する経路は46通りとなる。具体的には

74 = {1 + 8 + 28} + {28 + 8 + 1},

46 = {28 + 8 + 1} + 8 + 1.

8歩以内に $- 3$ と $4$ の両方へ達することはできない。したがって

256 - 74 - 46 = 136 通り .

(3)

$[- 1, 3]$ にとどまる経路を数える。 $- 2$ に達する経路は、同じ反射法で

{1 + 8 + 28 + 56} + {28 + 8 + 1} = 130

通りである。 $4$ に達するものは46通りであり、両方へ達するものは $LLRRRRRR$ の1通りだけである。よって

# {[- 1, 3] にとどまる} = 256 - 130 - 46 + 1 = 81.

したがって $- 2$ に到達し、かつ $3$ を超えないものは

136 - 81 = 55 通り .

(4)

$[- 2, 0]$ では奇数回後の位置は必ず $- 1$ である。2,4,6,8回目には $- 2$ と0のどちらへ行くかを選べるので

2^{4} = 16

通り。 $[- 1, 0]$ では移動がLRLR $\dots$ と一意なので1通りである。よって $m = - 2, M ≦ 0$ は15通りであり、

55 - 15 = 40 通り .

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

問題

方針

解法1（位置別の通り数を更新する方法）

解法2（反射法と短い区間の強制移動を使う方法）

解答

解法1（位置別の通り数を更新する方法）

(1)

(2)

(3)

(4)

解法2（反射法と短い区間の強制移動を使う方法）

(1)

(2)

(3)

(4)

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