方針
移動は常に右または下なので,一度通り過ぎた数字へ戻ることはない。したがって,ある数字 が終了時までに丸で囲まれる確率を,各位置から出発したときの再帰確率として後ろから求める。(1) は2に到達できる経路が初手2または初手1から2だけであることを使う。(2)(3) は目標を5または11に固定し,終点では目標なら1,別の終了数字なら0として,平均を順に計算する。
解答
(1)
数字2が丸で囲まれるには,最初に2を選ぶか,最初に1を選び,次の操作で2を選ぶしかない。右または下にしか移動しないので,それ以外の位置から2へ移動することはできない。
1の位置から選べる数字は の7個である。したがって である。
(2)
数字 に石がある状態から始めて,終了時までに5が丸で囲まれる確率を とする。終了数字である5に着けば であり,5以外の終了数字9,11,12に着けばその後は5に行けないので確率は0である。
後ろから順に計算する。4からは5または9を選ぶので である。3からは4,5,8を選ぶので である。2からは3,4,5,7,11を選ぶので である。最後に1からは2,3,4,5,6,10,12を選ぶので である。
したがって,初めの選択が12個の数字から等確率であることよりである。
(3)
同様に,数字 に石がある状態から始めて,終了時までに11が丸で囲まれる確率を とする。まず である。
10からは11または12を選ぶので である。7からは8,9,11を選ぶので である。6からは7,8,9,10,12を選ぶので である。2からは3,4,5,7,11を選ぶので であり,1からは2,3,4,5,6,10,12を選ぶので である。
よってである。
別解
解法2(各マスへの到達確率を前向きに伝播する)
方針
各マスへの到達確率を初手 と直前位置からの流入の和で表し,番号順に計算する。
解答
(1)
数字 が終了時までに丸で囲まれる確率を とする。 の移動候補数を とすれば, を番号順に計算できる。まず , だから である。
(2) 5へ流入する位置を順に計算すると ,, である。よって である。
(3) 同様に ,, だから, である。したがって である。
総評
難度5、計算量5。想定時間は18分程度。終了時に石が置かれている数字だけではなく,終了時までに丸で囲まれている確率を聞いている点が最大の注意点である。右または下にしか進まないため,再帰確率を終点側から計算すれば安定する。各位置から選べる候補数が場所ごとに異なるので,例にある6の候補を基準に,右方向と下方向を漏れなく数えることが重要である。 前向き伝播の別解は全 を同じ表で管理でき,終点確率の和が1になることまで検算できる。