C.Ordinary Beauty(300)
問題
数列 (a_1, a_2, ... , a_n) の美しさを隣接2項の差の絶対値がdであるものの個数と定義する。
1<= a_i <= n である a_i を m 個並べた時の nm 個のすべての数列全体を考えたときの美しさの平均値を求めよ。
この問題で求められていることはすべての数列に対する平均値ですが、見方を変えると、nm個の数列からランダムに1つ選んだときの期待値が求められている問題と考えることができます。
期待値とは以下のように定義されます。
「期待値とはある試行を行ったとき，その結果として得られる数値の平均値のことである.すなわち，試行によって得られる数値 が
であり、それぞれの値をとる確率が
とすると、
の期待値は、期待値 =
となる」*1
さて、問題の構造を理解するために以下のいくつかの小問題を考えます。
小問題1（サイコロ）
サイコロを1回投げて出る目は 1～6 の6通りあります。この6通りのすべての目の和の平均を求めよ。
サイコロを1回投げた時の目は 1 ,2 ,3, 4, 5, 6 であるから、6通りの目の和は 21 で平均は 21/6 = 7/2 となります。
これはサイコロを投げた時の期待値を求めていることと同値と考えることができます。(1~6のどの目も同様に確からしい確率で出るという前提です)
すなわち、
1 * 1/6 + 2 * 1/6 + 3 * 1/6 + 4 * 1/6 + 5 * 1/6 + 6 * 1/6
= (1 + 2 + 3 + 4 + 5 + 6)/6
=7/2
です。なぜ期待値が求められていることと同値と考えることができるのでしょうか。
この結果を見てみると、実は計算式を次のように解釈することができるのです。
「１点から６点までが、すべて同様に確からしい確率で獲得する可能性があるので、 『仮にすべての目が均等に１回ずつ出た』と想定したときの平均値を出しても 同様の結果になるのではないか」*2
このように考えると、すべての組み合わせを考えたときに、それぞれの組み合わせが選ばれる確率がすべて同様に確からしい場合、
すべての組み合わせの和の平均 = すべての組み合わせからランダムに1つ選んだ時の期待値
は同じとみなすことができそうです。すると元の問題文の「nm 個のすべての数列全体を考えたときの美しさの平均値」は「nm個の数列全体からランダムに1つ選んだ時の期待値」と同じといえます。このように考えると元の問題は期待値を求める問題と考えることができそうです。
小問題2（m = 2）
数列 (a_1, a_2, ... , a_n) の美しさを隣接2項の差の絶対値がdであるものの個数と定義する。
1<= a_i <= n である a_i を 2 個並べた時の n2 個のすべて数列全体を考えたときの美しさの平均値を求めよ。
美しい時は1、そうでないときは0の結果を得るととらえたほうが期待値と考えやすくなる気がします。
さて の2項を考えた時
(i)d=0の場合
美しくなる数列の選び方は(1, 1), (2, 2), (3, 3),...,(n, n) のn通り。
(ii)d≠0の場合
美しくなる数列の選び方は(1, 1+d), (2, 2+d), (3, 3+d),...,(n-d, n), (1+d, 1), (2+d, 2), (3+d, 3), ... ,(n, n-d) の2(n-d) 通り。
です。よって求める期待値は
(i) d=0の場合
1 * n/n2 + 0 * (1 - n/n2) = 1/n
(ii) d≠0の場合
1 * 2*(n-d)/n2 + 0 * (1 - 2*(n-d)/n2) = 2*(n-d)/n2
となります。
さて、小問題2では m=2 の場合について考えましたが、一般の場合について考えてみます。
小問題3（サイコロｍ回）
サイコロを1回投げて出る目は 1～6 の6通りあります。m回サイコロを投げた時、出る目の組み合わせは全部で6m通りあります。6m通りの出る目の総和の平均を求めよ。
この問題を解くために「期待値の線形性」が重要な役割を持ちます。「期待値の線形性」とは「和の期待値は期待値の和に等しい」ことを示しています。式で示すと以下のようになります。
確率変数 X,Y と期待値に関して以下が成立する。
これを用いると、サイコロ1回投げた時の期待値は7/2でしたから、m回投げた時の期待値は Σ [1->m] (7/2) より 7*m/2 となります。これで元の問題を解く準備が整いました。
問題
数列 (a_1, a_2, ... , a_n) の美しさを隣接2項の差の絶対値がdであるものの個数と定義する。
1<= a_i <= n である a_i を m 個並べた時の nm 個のすべての数列全体を考えたときの美しさの平均値を求めよ。
小問題2で m = 2 の場合について考えました。a_i が ｍ項ある時の項の間は全部でm-1個あります。よって期待値の線形性よりa_1, a_2 で求めた期待値をm-1倍すれば求めることができます。よって答えは
(i) d=0の場合
1/n * (m-1) = (m-1)/n
(ii) d≠0の場合
2*(n-d)/n2 * (m-1) = 2 * (n-d) * (m-1)/ n2
となります。元の問題を解くためのポイントは、
- 期待値が求められていることに気づく
- 隣接2項間については、それぞれのa_i, a_(i+1) を別々に捉える
- 期待値の線形性を理解する
ということになるでしょうか。
