Evolton
方針
(1) は袋Aの取り出し順を固定し、袋Bの取り出し順を4文字の順列として見る。数字が一致した回数は順列の固定点数なので、固定点がちょうど1個、2個、3個、4個の場合を、残りの完全不一致の並べ方まで含めて数える。期待値は各回の一致を表す指示変数の和として求める。(2)は、残り3枚のときの一致確率が 、残り2枚のときの一致確率が 、残り1枚では必ず一致することを使い、待ち時間の和として を表す。
解答
(1)
袋Aの取り出し順を固定してよい。このとき袋Bの取り出し順は の順列であり、同じ回に同じ数字が出る回数 は、その順列の固定点の個数である。全体は 通りである。
固定点がちょうど1個の順列を数える。固定する位置は 通りで、残り3個は固定点をもたないように並べる。3個の完全不一致の並べ方は の2通りであるから、 通りである。
固定点がちょうど2個の順列では、固定する2位置を選ぶと、残り2個は互いに入れ替わるしかない。したがって 通りである。固定点がちょうど3個なら残り1個も固定されてしまうので、これは0通りである。固定点が4個は恒等順列の1通りである。
よって である。
期待値は指示変数で求めると速い。 回目に数字が一致すれば1、一致しなければ0となる変数を とすると である。各回で袋Bの該当カードがその位置に来る確率は だから である。したがって である。
(2)
最初は3枚ずつ残っている。1回の操作で一致する確率は 、一致しない確率は である。カードが初めて取り除かれるのが 回目であるには、最初の 回が不一致で、 回目が一致すればよい。よって である。
次に を求める。すべてのカードが取り除かれるには、まず残り3枚の状態で初めて一致するまで待ち、次に残り2枚の状態で初めて一致するまで待ち、最後に残り1枚の状態で1回操作する。最後の1枚は必ず一致する。
残り3枚で初めて一致するまでの回数を とすると、その確率は である。残り2枚で初めて一致するまでの回数を とすると、その確率は である。全体で 回目にすべて取り除かれるには である。したがって のときである。 と置き直すとであり、等比数列の和から となる。よって
総評
難度7、目安時間31分。(1)は順列の固定点を数える問題で、固定点が3個だけという場合が存在しない理由を明記するとよい。期待値は分布から計算してもよいが、各回の一致確率を足す方が短く確実である。(2)は「残り枚数が変わるたびに一致確率が変わる」点が核心で、残り3枚・2枚・1枚の待ち時間を分けて書くと、 の和の範囲と の例外を落としにくい。