Evolton

名古屋大学 2000年度 前期日程 第2次学力試験理系数学 第3問

図のように,平面上に点A0, A1, A2, ⋯⋯
およびB0, B1, B2, ⋯⋯が並んでいる.
点PはA0から出発し,次の規則に従いこれらの点の上を移動する.

PがAnにいるときには1秒後にAn+1またはBnに,
一方BnにいるときにはBn+1またはAnに移動する.
ただし,前にいた点には戻らない.
また,Pが移動しうる点が複数あるときには,
それぞれの点へ等確率で移動する.
PがAnへ到る行き方がan通り,
Bnへ到る行き方がbn通りあるとする.

(1) a3,b3を求めよ.

(2) an,bnを求めよ.

(3) 一方,点QはA8からPと同時に出発し,
1秒ごとに順次A8→A7→A6→⋯⋯→A0と移動し,
その後はA0にとどまる.
PとQが出会う確率を求めよ.

問題の図

難易度8/ 10計算量7/ 10目安30分

数列、確率 漸化式の変形、状態分類、確率漸化式

方針

行き方の数では、An に入る直前が An−1 である場合と、Bn−1→Bn→An と進む場合に分ける。戻れない条件により、Bn→An の直前は必ず Bn−1 になる。同様に Bn についても漸化式が立つ。出会う確率は時刻 t に Q が A8−t にいることから、可能な時刻が 4,5 だけに絞られる。時刻4は一直線に進む1通り、時刻5は戻れない条件で確率の異なる6通りを列挙して合計する。

解答

(1)
まず行き方の数を調べる。An に到る最後の部分は、次の2種類に分けられる。

1つは An−1→An と進む場合である。もう1つは Bn→An と進む場合であるが、直前の点に戻ることはできないので、この直前は An ではなく Bn−1 でなければならない。したがってこの場合の最後の部分は Bn−1→Bn→An である。よって an=an−1+bn−1 である。同様に bn=bn−1+an−1 である。

初めに A0 にいるので A0 への行き方は1通りである。また B0 へは A0→B0 の1通りで到るから a0=b0=1 である。したがって a1=b1=2,a2=b2=4,a3=b3=8 である。よって a3=8,b3=8 である。

(2)
上の漸化式で、a0=b0=1 である。もし an−1=bn−1=2n−1 なら an=an−1+bn−1=2n,bn=bn−1+an−1=2n である。よって数学的帰納法により an=bn=2n である。

(3)
点 Q は時刻 t に A8−t にいる。ただし 0≦t≦8 とする。点 P は1秒で添字を高々1だけ増やすので、P と Q が出会うには 8−t≦t が必要である。また P が A8−t にいるには、時刻 t までの横方向の移動回数が 8−t であり、残りの縦方向の移動回数は t−(8−t)=2t−8 である。A 側に戻っているためには縦移動回数は偶数である。これらを合わせると、実際に出会える時刻は t=4,5 だけである。

時刻4で出会うには A0→A1→A2→A3→A4 と進むしかない。各時刻で2通りの選択があるので、その確率は (12)4=116 である。

時刻5で出会うには A3 にいる必要がある。可能な経路とその確率は次の通りである。経路確率A0A1A2B2B3A31/16A0A1B1B2B3A31/16A0B0B1B2B3A31/16A0A1B1B2A2A31/8A0B0B1B2A2A31/8A0B0B1A1A2A31/8である。確率が 1/8 になる経路があるのは、途中で直前の点へ戻れず、次の移動が強制される箇所があるためである。したがって時刻5で出会う確率は 3⋅116+3⋅18=916 である。

時刻4と時刻5の出会いは同時には起こらない。よって求める確率は 116+916=58 である。

別解

解法2(状態確率表で出会いを追う)

方針

行き方の数は対称な2変数漸化式を行列で解く。
出会いについては「直前の点」と「現在の点」を状態に含め、
戻れないため選択が1通りになる場合も反映した確率表を時刻5まで作る。

解答

(1)
最後に水平に進む場合と、反対側から縦に移る場合を分けると(anbn)=(1111)(an−1bn−1).a0=b0=1 だからa3=b3=8.(2)
(1,1) は上の行列で2倍される。初期ベクトルも (1,1) なので(anbn)=2n(11).したがってan=bn=2n.(3)
時刻 t の Q は A8−t にいる。添字の増加回数と上下移動の偶奇から、
出会えるのは t=4 の A4 と、t=5 の A3 だけである。

戻り禁止を含めて状態確率を順に更新すると、必要な成分はtPr⁡(P=A8−t)該当点4116A45916A3となる。実際、A4 へは4回連続で上段を進む1経路だけで確率 1/16。
A3 へは、確率 1/16 の3経路と、途中の移動が強制されて確率 1/8 となる3経路があり、3⋅116+3⋅18=916.2事象は排反なのでPr⁡(出会う)=116+916=58.

総評

難度8、計算量7。図の欠落していた梯子状の点配置を復元した。行き方の数と各経路の確率は同じではなく、戻り禁止で移動が強制される状態を区別する必要がある。時刻4と5の排反な出会いを状態表と経路列挙で照合した。 2つの解法は着眼点を分け、必要性・十分性、端点、等号条件を省略せず記述した。

Evolton Pro

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

冊子PDFで見る名大の数列の問題で問題集を作る

出典: 名古屋大学 2000年度 前期 理系 第3問。問題文はHTML表示のために再入力・数式組版しています。