Evolton

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

nを自然数とする。xy平面上を動く点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,…,nに対して、Pがk回移動した後のx座標をxkとおく。

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

次の問いに答えよ。

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

以下、n=8とする。x1,…,x8の最大値をMとし、x1,…,x8の最小値をmとする。

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

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

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

難易度5/ 10計算量5/ 10目安18分

場合の数 状態分類、数え上げ、余事象、計算整理

方針

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

解答

(1)
x4=0 となるにはLとRが2回ずつ必要である。
そのうち途中で正にならないものはLLRR,LRLRだから2通り.(2)
Ak(j) を、時刻 k まで常に
−2≦x≦3 を保ち、xk=j となる通り数とする。
区間外を0と約束すればAk+1(j)=Ak(j−1)+Ak(j+1),A0(0)=1.更新表は次の通りである。k\j−2−10123000100010101002102010303030143060405090100469019014070280330148280610470よって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(反射法と短い区間の強制移動を使う方法)

方針

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

解答

(1)
4歩で原点へ戻り、途中で正にならない列はLLRR,LRLRのみである。よって2通り.(2)
全経路は 28=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のどちらへ行くかを選べるので24=16通り。[−1,0] では移動がLRLR⋯と一意なので1通りである。
よって m=−2, M≦0 は15通りであり、55−15=40通り.

総評

難度5、計算量5、目安18分。2次元の図に惑わされず、
x 座標だけの ±1 移動へ落とす。
状態更新では区間外を0とし、端点から余計に流入させない。
(3)は下端 −2 への到達、(4)はさらに上端側への到達を差で数える。
反射法でも2つの境界到達事象の重なりを必ず確認する。

大学別の過去問PDF

問題編・解答編セット/買い切り

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る横国の場合の数の問題で問題集を作る

出典: 横浜国立大学 令和4年度一般選抜前期 数学 第2問(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。