方針
頂点の隣接関係を明示し、時刻1では の2通りと の3通りを組み合わせて6配置を図示する。そのうち衝突2配置を除き、残る4配置を「同じ正方形上」と「異なる正方形」に分類する。以後に現れる非衝突配置は2種類にまとめられ、同じ正方形型からの遷移確率は 、異なる正方形型からは となる。最後は1歩後まで生存する確率が最大でも であることを使う。
解答
(1)
時刻1で は のいずれかへ、 は のいずれかへ移る。よって6配置はである。これらを図示すると次のようになる。
(2)
時刻1の6配置はそれぞれ確率 である。 は衝突するので除く。残るうちは2点が同じ正方形上にあり、 だけは異なる正方形にいる。よって時刻1の各非衝突配置から、時刻2での非衝突配置を数える。したがって(3)
時刻 まで衝突していない到達可能な配置は、偶数時刻では奇数時刻ではである。いずれの時刻でも、前4配置が 型、後2配置が 型である。
代表配置を1つずつ調べると、次の遷移表を得る。図形の左右対称性により、同じ型の他の配置でも同じである。したがって(4)時刻0ではまだ衝突していないので である。上の不等式を繰り返して
別解
解法2
方針
非衝突配置を同じ正方形上の型 と異なる正方形の型 にまとめ、確率ベクトル を使う。代表配置の全移動を数えて2行2列の遷移行列を作る。初期ベクトルから の値を計算し、列ごとの生存確率の最大値 を使って全確率を評価する。
解答
(1)
時刻1の配置はの6通りである。うち は時刻1で衝突する。
(2)
非衝突4配置のうち、同じ正方形上にあるものが3個、異なる正方形にあるものが1個なので同じ正方形型の代表 からは6通り中、次の同じ正方形型が3通り、異なる正方形型が1通りである。異なる正方形型の代表 からは4通り中、それぞれ2通り、1通りである。よって遷移行列はしたがって(3)
同じ分類はすべての時刻で保たれるためすなわち(4)
行列の第1列の和は 、第2列の和は である。これは、現在が同じ正方形型なら次の1歩でも衝突しない確率が 、異なる正方形型なら であることを意味する。したがって条件付き生存確率は常に 以下であり、 から
総評
難度8、目安時間30分。図の欠落は状態分類そのものを分かりにくくするため、初期配置と時刻1の全6配置を実図で示した。非衝突で到達可能な配置は、偶数時刻と奇数時刻で頂点集合が入れ替わるが、各時刻とも「同じ正方形型4配置・異なる正方形型2配置」に整理できる。漸化式の係数には次の1歩で衝突する場合を含めない。 は直接列挙と行列計算の両方で検算でき、(4)は各型の1歩生存確率 の最大値を使う。