Evolton
方針
各時点の 君の得点は「表の回数 裏の回数」であり、 君の得点はその反対である。したがって 君が常に多い条件は、各途中時点で表の累計が裏の累計より大きいことと同値になる。(1)(2)は表裏の回数を決めるだけでよく、(3)は最初に表を出した後、途中で同点に戻らない列を反射法で数える。
解答
(1)
3回の試行で表が 回、裏が 回出たとする。 君の得点は であり、 である。よって 、 であり、場合の数は である。
(2) 回後に表が 回、裏が 回出たとする。このとき であるから、 である。したがって のとき、場合の数は である。 のときは となるので、そのような列は存在せず 通りである。
(3)
条件付きで考える。 回後に 君の得点が 点であるから、以下では とする。表の総数を 裏の総数を とおく。全体の場合の数は である。
途中時点で 君の得点が 君の得点より多いことは、 君の得点が正、すなわち表の累計が裏の累計より多いことと同値である。したがって、各途中時点で を満たす列を数えればよい。
この条件を満たす列は最初が必ず表である。最初の表を取り除いた残り 個の並びには、表が 個、裏が 個ある。残りの並びを左から読んだとき、途中で初めて表裏の累計差が になるものを不適とする。この不適な並びは、初めて になったところまで表と裏を入れ替える反射によって、表が 個、裏が 個ある並びと一対一に対応する。
したがって適する列の数は である。これを整理するとまた であるから、求める確率はよって である。
得点差を格子路として見る
別解
解法2
方針
表を 、裏を とする道を考える。(3)では循環補題を使い、終点の高さが である各列の巡回開始位置のうち、部分和が常に正になる開始位置の割合を直接求める。
解答
(1)
3回後の得点が1であるには、表2回・裏1回である。裏の位置を選べばよいので(2)
表を 回、裏を 回とするとよって であり、場合の数は(3)
とする。表を 、裏を と書けば、
各列の総和は循環補題によれば、総和が である長さ の
列を、開始位置を指定した巡回列として数えると、
各巡回軌道の 個の開始位置のうち、途中の部分和がすべて正となる
開始位置はちょうど 個である。これは、部分和が最小値を更新した直後を
開始位置に取ると正の道が得られ、その更新回数を総上昇量で数えることで分かる。
したがって、終点が であるという条件の下で、途中の得点が常に正である割合は 君の得点は常に 君の得点の反対符号なので、
君が常に 君より多い条件は、まさにこの部分和が常に正という条件である。
よって求める確率は
総評
難度は10段階中6、計算量は10段階中4。(1)(2)は表と裏の回数を連立方程式で決めればよいが、(3)では「 の得点が より多い」を「表の累計が裏の累計より常に多い」に直すところが核心である。条件付き確率なので、分母は 回後の得点が である全列数にする。想定時間は10分程度で、反射法の対応を言葉で書くと、公式暗記に見えず減点されにくい。