Evolton

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

下図のように、2つの正方形 ABCD と CDEF を辺 CD で共有するように並べた図形を考える。

問題の図

2点 P,Q が6個の頂点 A,B,C,D,E,F を次の規則に従って移動する。

(a)
時刻0では、点 P は頂点 A に、点 Q は頂点 C にいる。

(b)
点 P,Q は時刻が1増えるごとに独立に、今いる頂点と辺で結ばれている頂点へ等確率で移動する。

時刻 n まで2点が同時に同じ頂点にいることが一度もない確率を pn とする。また、時刻 n まで一度も同じ頂点におらず、かつ時刻 n に2点がともに同じ正方形上にいる確率を an とし、
bn=pn−an
と定める。

(1)
時刻1での点 P,Q の可能な配置を、すべて図示せよ。

(2)
a1, b1, a2, b2 を求めよ。

(3)
an+1,bn+1 を an,bn で表せ。

(4)
pn≦(34)n を示せ。

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

確率、数列 状態分類、確率漸化式、数学的帰納法、不等式評価

方針

頂点の隣接関係を明示し、時刻1では P の2通りと Q の3通りを組み合わせて6配置を図示する。そのうち衝突2配置を除き、残る4配置を「同じ正方形上」と「異なる正方形」に分類する。以後に現れる非衝突配置は2種類にまとめられ、同じ正方形型からの遷移確率は (1/2,1/6)、異なる正方形型からは (1/2,1/4) となる。最後は1歩後まで生存する確率が最大でも 3/4 であることを使う。

解答

(1)

時刻1で P は B,D のいずれかへ、Q は B,D,F のいずれかへ移る。よって6配置は(B,B), (B,D), (B,F), (D,B), (D,D), (D,F)である。これらを図示すると次のようになる。

(2)

時刻1の6配置はそれぞれ確率 1/6 である。(B,B),(D,D) は衝突するので除く。残るうち(B,D), (D,B), (D,F)は2点が同じ正方形上にあり、(B,F) だけは異なる正方形にいる。よってa1=12,b1=16.時刻1の各非衝突配置から、時刻2での非衝突配置を数える。時刻1の配置全移動数a2 型b2 型(B,D)631(D,B)631(D,F)631(B,F)421したがってa2=3⋅16⋅36+16⋅24=13,b2=3⋅16⋅16+16⋅14=18.(3)

時刻 n まで衝突していない到達可能な配置は、偶数時刻では(A,C),(C,A),(C,E),(E,C),(A,E),(E,A),奇数時刻では(B,D),(D,B),(D,F),(F,D),(B,F),(F,B)である。いずれの時刻でも、前4配置が an 型、後2配置が bn 型である。

代表配置を1つずつ調べると、次の遷移表を得る。現在の型全移動数an+1 型bn+1 型an 型631bn 型421図形の左右対称性により、同じ型の他の配置でも同じである。したがってan+1=12an+12bn,bn+1=16an+14bn.(4)pn+1=an+1+bn+1=23an+34bn≦34(an+bn)=34pn.時刻0ではまだ衝突していないので p0=1 である。上の不等式を繰り返してpn≦(34)np0=(34)n.

別解

解法2

方針

非衝突配置を同じ正方形上の型 A と異なる正方形の型 B にまとめ、確率ベクトル vn=(an,bn)T を使う。代表配置の全移動を数えて2行2列の遷移行列を作る。初期ベクトルから n=2 の値を計算し、列ごとの生存確率の最大値 3/4 を使って全確率を評価する。

解答

(1)

時刻1の配置は(B,B), (B,D), (B,F), (D,B), (D,D), (D,F)の6通りである。うち (B,B),(D,D) は時刻1で衝突する。

(2)

非衝突4配置のうち、同じ正方形上にあるものが3個、異なる正方形にあるものが1個なのでv1=(a1b1)=(1/21/6).同じ正方形型の代表 (B,D) からは6通り中、次の同じ正方形型が3通り、異なる正方形型が1通りである。異なる正方形型の代表 (B,F) からは4通り中、それぞれ2通り、1通りである。よって遷移行列はM=(1/21/21/61/4).したがってv2=Mv1=(1/31/8).(3)

同じ分類はすべての時刻で保たれるため(an+1bn+1)=(1/21/21/61/4)(anbn).すなわちan+1=12an+12bn,bn+1=16an+14bn.(4)

行列の第1列の和は 2/3、第2列の和は 3/4 である。これは、現在が同じ正方形型なら次の1歩でも衝突しない確率が 2/3、異なる正方形型なら 3/4 であることを意味する。したがって条件付き生存確率は常に 3/4 以下であり、pn+1≦34pn.p0=1 からpn≦(34)n.

総評

難度8、目安時間30分。図の欠落は状態分類そのものを分かりにくくするため、初期配置と時刻1の全6配置を実図で示した。非衝突で到達可能な配置は、偶数時刻と奇数時刻で頂点集合が入れ替わるが、各時刻とも「同じ正方形型4配置・異なる正方形型2配置」に整理できる。漸化式の係数には次の1歩で衝突する場合を含めない。a2=1/3,b2=1/8 は直接列挙と行列計算の両方で検算でき、(4)は各型の1歩生存確率 2/3,3/4 の最大値を使う。

Evolton Pro

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

冊子PDFで見る名大の確率の問題で問題集を作る

出典: 名古屋大学 2018年度 前期日程 数学(文理共通)(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。