方針
最初にA室にいた3人だけを印付きとして追跡する。各移動後の印付き人数をで表すと、1回目の移動後は必ずになる。2回目後の可能な状態と確率を表にし、そこから3回目でA室の印付き人数が0になる確率を掛けて合計する。
解答
最初の日にA室にいた3人を印付きの人として追跡する。各移動後の印付き人数を で表す。
1回目の移動では、A室から1人がB室へ移る。最初はA室の3人全員が印付きなので、1回目の移動後は必ず になる。
次に2回目の移動後を考える。状態から、A室の印付きがB室へ移る確率は、移らない確率はである。また、B室にいる1人の印付きは、A室へ移る、C室へ移る、B室に残る、の3通りが同じ確率で起こる。C室には印付きがいない。
したがって2回目後の状態と確率はである。
3回目の移動後にA室の印付き人数が0になるには、2回目後にA室の印付き人数が1でなければならない。したがって関係する状態は だけである。
状態からA室の印付きが0になるには、A室の1人の印付きがB室へ選ばれ、同時にB室からA室へ移る人が印付きでない必要がある。この確率は である。
状態からA室の印付きが0になるには、A室の1人の印付きがB室へ選ばれ、同時にB室からA室へ移る人が印付きでない必要がある。B室には印付きが2人、印付きでない人が1人いるので、この確率は である。
よって求める確率はである。
別解
解法2
方針
3回目にA室の印つき人数を0にできる、2回後の二つの状態だけを追う。それぞれの到達確率と、そこから3回目に成功する条件付き確率を掛ける。
解答
最初の日にA室にいた3人だけを印つきとして追跡する。1回目の移動後の印つき人数は、必ずとなる。
3回目の移動でA室の印つき人数を0にするには、2回目終了時の状態がでなければならない。2回目にA室の印つきが選ばれる確率は 。また、B室の1人の印つきがC室へ移る場合とB室に残る場合はそれぞれ確率 だから状態 からは、A室の印つきが選ばれ、かつB室からA室へ移る人が印なしであればよい。その条件付き確率は状態 から同じことが起こる条件付き確率は従って求める確率は
総評
難度8、計算量7。目安時間は32分。3人を個別に完全列挙しようとすると依存関係が複雑になるため、印付き人数の状態で追うのが有効である。2回目後の状態を表にしてから、3回目でA室が0人になる可能性だけを拾うと計算量が抑えられる。B室からA室へ移る人が印付きかどうかが最後の分岐の要点である。
