方針
頂点を反時計回りに と番号づけ, とみなす。表を ,裏を の移動として,合計移動量を4で割った余りで到達頂点を決める。(1)は表裏同確率なので,各回数について表の回数ごとに二項分布で数える。(2)は表の確率を ,裏の確率を とし,2回後・3回後の各頂点確率を明示して差をとる。 から を使う。
解答
(1)
頂点を反時計回りに と並べ,それぞれ と番号づける。表が出たら ,裏が出たら だけ動くと考え,最後に4で割った余りで頂点を読む。
2回繰り返すと,移動量は のいずれかである。したがって に戻るのは表裏が1回ずつ出た場合, に行くのは2回とも同じ面が出た場合である。よって である。
3回繰り返すと,移動量は奇数なので にはいない。表が2回または裏が3回なら ,表が3回または裏が2回なら であり,対称性から である。
4回繰り返すと,移動量は偶数なので にはいない。表の回数を とすると移動量は である。 では移動量が4の倍数なので にいる。 では移動量が なので にいる。したがってである。
(2)
裏の出る確率を とおく。仮定より である。
2回後は, にいるのが表裏が1回ずつの場合, にいるのが2回とも同じ面の場合であるから である。したがって である。よって2回後は, にある確率が最大である。
3回後は にいる確率は0である。 にいるのは,表が2回で移動量 となる場合,または表が0回で移動量 となる場合である。よって である。一方, にいるのは,表が3回で移動量 となる場合,または表が1回で移動量 となる場合である。よって である。
差をとるとである。したがって3回後は, にある確率が最大である。
到達頂点は「表の回数-裏の回数」を4で割った余りだけで決まる。
別解
解法2
方針
時刻 の確率ベクトルを とし、各頂点へ隣接する2頂点から流入する確率で漸化式を立てる。(1)は で4回更新する。(2)は一般の について2回後と3回後を更新し、最大確率との差を因数分解する。
解答
(1)
表の確率を 、裏の確率を とする。頂点を反時計回りに と並べると、確率ベクトルはと更新される。初期値は である。
を代入して順に更新するとである。
(2)
一般の ではここでだから、2回後は頂点 の確率が最大である。
さらに1回更新するとよってしたがって3回後は頂点 の確率が最大である。
総評
難度4,計算量4。頂点を4で割った余りとして管理すると,図に頼らず処理できる。4回後は移動量が偶数なので だけを見ればよいが, はすべて , は に対応する点に注意する。(2)は を と読み替え,確率の差を , に因数分解できれば明快に示せる。目安時間は18分前後。