Evolton
方針
記録された和そのものではなく、 で割った余りだけを状態として見る。1回目で終了する場合を除くと、未終了の余りは または だけである。どちらの余りにいても、次に終了する確率は 、終了しない確率は で一定になるため、 回目で初めて終了する確率を等比的に求める。
解答
玉に書かれた数を で割った余りで分類する。余り は の1個、余り は の2個、余り は の2個である。したがって各回で余り が出る確率はそれぞれ である。
(1)
1回目で終了するのは、1回目に余り 、すなわち数字 が出た場合である。よって である。
2回目で終了するには、1回目では終了せず、2回目で余りの和が になればよい。1回目の余りが なら2回目は余り 、1回目の余りが なら2回目は余り である。したがって である。
(2)
1回目で終了しない確率は である。終了していないとき、現在の和の余りは または である。余りが のときは次に余り が出ると終了し、余りが のときは次に余り が出ると終了する。どちらの場合も終了する確率は であり、終了しない確率は である。
したがって のとき、1回目で終了せず、2回目から 回目までは終了せず、 回目で終了する確率は である。整理して を得る。
総評
難度5、目安時間16分。余り の状態だけを見れば、複雑な和を追う必要はない。採点上は、未終了状態では余りが または に限られ、そのどちらからでも次に終了する確率が で同じになることを説明するのが重要である。典型ミスは、数字 を引いたときだけでなく、累積和が3の倍数になる場合も終了する点を見落とすことである。