kadai78

平成２２年４月１８日

[流れ星]

　　　　　第２３９回数学的な応募問題解答

　　　　　　＜解答募集期間：３月28日～４月18日

［自然対数と確率］

確率の問題を見ていると、その結果に驚く場合があります。次の問題を考えてください。

問題１：一つのサイコロを繰り返し振って、出た目の和が６を超えるまで振り続ける。
サイコロを振る回数の期待値を求めよ。

問題２：１からnまでの自然数を一つずつ書いたカードが計n枚あって、そこから無作為に1枚抜き取っては元に戻す。抜き取ったカードに書かれた数の和がnを超えるまで繰り返すとき、カードを抜き取る回数の期待値をEnとする。

　　　　ｎを無限大にしたとこのEnの極限値を求めよ。

NO1「uchinyan」 03/28 16時44分受信

「uchinyan」 03/29 11時03分受信更新4/18

第２３９回数学的な応募問題

［自然対数と確率］

以下では，

　k 回目に出る数を a(k)，k 回目までの a(k) の和を S(k)，その確率を p(k,S(k))，

　特に，k 回目で初めて S(k) > n となる確率を P(k)

とします。

明らかに，少なくとも k = n+1 で必ず題意を満たすので，期待値 En は，

En = Σ[k=1,n+1]{k * P(k)}

です。

問題１：

n = 6 の場合です。まずは，地道に考えてみます。

１回目：

S(1) = a(1) = 1 ～ 6 なので，P(1) = 0 です。

２回目：

S(1) = 1 のとき，OK は a(2) = 6 で 1/6 * 1/6

S(1) = 2 のとき，OK は a(2) = 5, 6 で 1/6 * 2/6

S(1) = 3 のとき，OK は a(2) = 4, 5, 6 で 1/6 * 3/6

S(1) = 4 のとき，OK は a(2) = 3, 4, 5, 6 で 1/6 * 4/6

S(1) = 5 のとき，OK は a(2) = 2, 3, 4, 5, 6 で 1/6 * 5/6

S(1) = 6 のとき，OK は a(2) = 1, 2, 3, 4, 5, 6 で 1/6 * 6/6

そこで，

P(2) = 1/6 * (1/6 + 2/6 + 3/6 + 4/6 + 5/6 + 6/6) = 1/6 * 21/6 = 21/6^2

なお，後で使うので，NG の場合の確率も求めておくと，

p(2,1) = 0, p(2,2) = 1/6 * 1/6 = 1/6^2, p(2,3) = 1/6 * 2/6 = 2/6^2,

p(2,4) = 1/6 * 3/6 = 3/6^2, p(2,5) = 1/6 * 4/6 = 4/6^2, p(2,6) = 1/6 * 5/6 = 5/6^2

３回目：

S(2) = 1 は，p(2,1) = 0 より，あり得ません。

S(2) = 2 のとき，OK は a(3) = 5, 6 で 1/6^2 * 2/6

S(2) = 3 のとき，OK は a(3) = 4, 5, 6 で 2/6^2 * 3/6

S(2) = 4 のとき，OK は a(3) = 3, 4, 5, 6 で 3/6^2 * 4/6

S(2) = 5 のとき，OK は a(3) = 2, 3, 4, 5, 6 で 4/6^2 * 5/6

S(2) = 6 のとき，OK は a(3) = 1, 2, 3, 4, 5, 6 で 5/6^2 * 6/6

そこで，

P(3) = 1/6^2 * 2/6 + 2/6^2 * 3/6 + 3/6^2 * 4/6 + 4/6^2 * 5/6 + 5/6^2 * 6/6 = 70/6^3

NG の場合の確率は，

p(3,1) = 0, p(3,2) = 0, p(3,3) = 1/6^2 * 1/6 = 1/6^3,

p(3,4) = 1/6^2 * 1/6 + 2/6^2 * 1/6 = 3/6^3,

p(3,5) = 1/6^2 * 1/6 + 2/6^2 * 1/6 + 3/6^2 * 1/6 = 6/6^3,

p(3,6) = 1/6^2 * 1/6 + 2/6^2 * 1/6 + 3/6^2 * 1/6 + 4/6^2 * 1/6 = 10/6^3

４回目：

S(3) = 1 は，p(3,1) = 0 より，あり得ません。

S(3) = 2 は，p(3,2) = 0 より，あり得ません。

S(3) = 3 のとき，OK は a(4) = 4, 5, 6 で 1/6^3 * 3/6

S(3) = 4 のとき，OK は a(4) = 3, 4, 5, 6 で 3/6^3 * 4/6

S(3) = 5 のとき，OK は a(4) = 2, 3, 4, 5, 6 で 6/6^3 * 5/6

S(3) = 6 のとき，OK は a(4) = 1, 2, 3, 4, 5, 6 で 10/6^3 * 6/6

そこで，

P(4) = 1/6^3 * 3/6 + 3/6^3 * 4/6 + 6/6^3 * 5/6 + 10/6^3 * 6/6 = 105/6^4

NG の場合の確率は，

p(4,1) = 0, p(4,2) = 0, p(4,3) = 0, p(4,4) = 1/6^3 * 1/6 = 1/6^4,

p(4,5) = 1/6^3 * 1/6 + 3/6^3 * 1/6 = 4/6^4,

p(4,6) = 1/6^3 * 1/6 + 3/6^3 * 1/6 + 6/6^3 * 1/6 = 10/6^4

５回目：

S(4) = 1 は，p(4,1) = 0 より，あり得ません。

S(4) = 2 は，p(4,2) = 0 より，あり得ません。

S(4) = 3 は，p(4,3) = 0 より，あり得ません。

S(4) = 4 のとき，OK は a(5) = 3, 4, 5, 6 で 1/6^4 * 4/6

S(4) = 5 のとき，OK は a(5) = 2, 3, 4, 5, 6 で 4/6^4 * 5/6

S(4) = 6 のとき，OK は a(5) = 1, 2, 3, 4, 5, 6 で 10/6^4 * 6/6

そこで，

P(5) = 1/6^4 * 4/6 + 4/6^4 * 5/6 + 10/6^4 * 6/6 = 84/6^5

NG の場合の確率は，

p(5,1) = 0, p(5,2) = 0, p(5,3) = 0, p(5,4) = 0, p(5,5) = 1/6^4 * 1/6 = 1/6^5,

p(5,6) = 1/6^4 * 1/6 + 4/6^4 * 1/6 = 5/6^5

６回目：

S(5) = 1 は，p(5,1) = 0 より，あり得ません。

S(5) = 2 は，p(5,2) = 0 より，あり得ません。

S(5) = 3 は，p(5,3) = 0 より，あり得ません。

S(5) = 4 は，p(5,4) = 0 より，あり得ません。

S(5) = 5 のとき，OK は a(6) = 2, 3, 4, 5, 6 で 1/6^5 * 5/6

S(5) = 6 のとき，OK は a(6) = 1, 2, 3, 4, 5, 6 で 5/6^5 * 6/6

そこで，

P(6) = 1/6^5 * 5/6 + 5/6^5 * 6/6 = 35/6^6

NG の場合の確率は，

p(6,1) = 0, p(6,2) = 0, p(6,3) = 0, p(6,4) = 0, p(6,5) = 0, p(6,6) = 1/6^5 * 1/6 = 1/6^6

７回目：

S(6) = 1 は，p(6,1) = 0 より，あり得ません。

S(6) = 2 は，p(6,2) = 0 より，あり得ません。

S(6) = 3 は，p(6,3) = 0 より，あり得ません。

S(6) = 4 は，p(6,4) = 0 より，あり得ません。

S(6) = 5 は，p(6,5) = 0 より，あり得ません。

S(6) = 6 のとき，OK は a(6) = 1, 2, 3, 4, 5, 6 で 1/6^6 * 6/6

そこで，

P(6) = 1/6^6 * 6/6 = 6/6^7

NG の場合の確率は，

p(6,1) = 0, p(6,2) = 0, p(6,3) = 0, p(6,4) = 0, p(6,5) = 0, p(6,6) = 0

以上ですべてです。そこで，期待値 E6 は，

E6 = 1 * 0 + 2 * 21/6^2 + 3 * 70/6^3 + 4 * 105/6^4 + 5 * 84/6^5 + 6 * 35/6^6 + 7 * 6/6^7

= (2 * 21 * 6^4 + 3 * 70 * 6^3 + 4 * 105 * 6^2 + 5 * 84 * 6 + 6 * 35 + 7)/6^6

= (54432 + 45360 + 15120 + 2520 + 210 + 7)/6^6

= 117649/46656

= 2.5216...

となります。

問題２：

最初に述べたように，明らかに，少なくとも k = n+1 で必ず題意を満たし，

また，k = 1 では S(1) = a(1) <= n で題意を満たさない，P(1) = 0，なので，

2 <= k <= n+1 として，k 回目の状況を考えることになります。

これはさらに，明らかに，p(k-1,k-2) = 0 なので，

S(k-1) = m として，k-1 <= m <= n の場合を考えることになります。

このとき，

a(1) + a(2) + ... + a(k-1) = m, 1 <= a(1), a(2), ..., a(k-1) <= n

ですが，a(i) = b(i) + 1 とおくと，

b(1) + b(2) + ... + b(k-1) = m-k+1, 0 <= b(1), b(2), ..., b(k-1) <= n-1

で，0 <= m-k+1 <= n-k+1 <= n-1 なので，こういう状況の b(i)，そして a(i)，の場合の数は，

m-k+1 個のボールを k-1 個の箱に分ける場合の数と同じで，(m-1)C(k-2) 通りです。

そこで，p(k-1,m) = (m-1)C(k-2)/n^(k-1) になります。これより，

S(k-1) = m のとき，OK は a(k) = n-m+1 ～ n で p(k-1,m) * m/n = m * (m-1)C(k-2) * 1/n^k

P(k) = Σ[m=k-1,n]{m * (m-1)C(k-2) * 1/n^k} = 1/n^k * Σ[m=k-1,n]{m * (m-1)C(k-2)}

これは，前回，第２３８回，の問題の(1)の私の解答で現れた，

p(k) = Σ[m=k-1,n]{(m-1)C(k-2)/n^(k-2) * 1/n * m/n}

と，全く同じ式で，全く同じ式変形で計算できます！　一応，再現しておきます。

P(k) = 1/n^k * Σ[m=k-1,n]{m * (m-1)C(k-2)}

= 1/n^k * Σ[m=k-1,n]{m * (m-1)!/(m-k+1)!(k-2)!}

= 1/n^k * Σ[m=k-1,n]{(k-1) * m!/(m-k+1)!(k-1)!}

= (k-1)/n^k * Σ[m=k-1,n]{mC(m-(k-1))}

= (k-1)/n^k * Σ[i=0,n-k+1]{(i+k-1)Ci}

= (k-1)/n^k * ((k-1)C0 + kC1 + (k+1)C2 + (k+2)C3 + ... + (n-1)C(n-k) + nC(n-k+1))

= (k-1)/n^k * (kC0 + kC1 + (k+1)C2 + (k+2)C3 + ... + (n-1)C(n-k) + nC(n-k+1))

ここで，二項係数の性質

(p-1)C(q-1) + (p-1)Cq = (p-1)!/(p-q)!(q-1)! + (p-1)!/(p-q-1)!q! = p!/(p-q)!q! = pCq

を繰り返し用いて，

= (k-1)/n^k * ((k+1)C1 + (k+1)C2 + (k+2)C3 + ... + (n-1)C(n-k) + nC(n-k+1))

= (k-1)/n^k * ((k+2)C2 + (k+2)C3 + ... + (n-1)C(n-k) + nC(n-k+1))

= (k-1)/n^k * ((k+3)C3 + ... + (n-1)C(n-k) + nC(n-k+1))

= ...

= (k-1)/n^k * ((n-1)C(n-k-1) + (n-1)C(n-k) + nC(n-k+1))

= (k-1)/n^k * (nC(n-k) + nC(n-k+1))

= (k-1)/n^k * (n+1)C(n-k+1)

= ((k-1) * (n+1)Ck)/n^k

つまり，k = 2, 3, ..., n に対して，

P(k) = ((k-1) * (n+1)Ck)/n^k

また，k = 1 では，

P(1) = 0

でした。上記の結果は，これを含んでいますね。

これより，期待値 En も，前回，第２３８回，の問題の(2)と全く同じになります。

一応，再度，計算しておくと，

En = Σ[k=1,n+1]{k * P(k)} = Σ[k=2,n+1]{k * P(k)}

= Σ[k=2,n+1]{k * ((k-1) * (n+1)Ck)/n^k}

= Σ[k=1,n]{k(k+1) * (n+1)C(k+1) * 1/n^(k+1)}

= Σ[k=1,n]{k(k+1) * (n+1)!/(k+1)!(n-k)! * 1/n^(k+1)}

= (n+1)/n * Σ[k=1,n]{(n-1)!/(k-1)!(n-k)! * 1/n^(k-1)}

= (n+1)/n * Σ[k=0,n-1]{(n-1)!/k!(n-k-1)! * 1/n^k}

= (n+1)/n * Σ[k=0,n-1]{(n-1)Ck * 1/n^k}

ここで，二項定理より，

(1 + x)^(n-1) = Σ[k=0,n-1]{(n-1)Ck * x^k}

なので，x = 1/n として，

(1 + 1/n)^(n-1) = Σ[k=0,n-1]{(n-1)Ck * 1/n^k}

そこで，

En = (n+1)/n * (1 + 1/n)^(n-1) = (1 + 1/n)^n

これより，

lim[n->∞]{En} = lim[n->∞]{(1 + 1/n)^n} = e = 2.71828...

になります。

(別解)

この問題，S(k) に注目して，次のように考えれば，P(k) は，もっと簡単に求まります。

(これも，前回，第２３８回，の問題との関連を示唆しています。)

P(k) は，k 回目に初めて S(k) が n を超える確率です。

この状況は。

　S(1) < S(2) < ... < S(k-1) <= n < S(k)

ですが，

　S(1) < S(2) < ... < S(k-1) <= n, S(k) = S(k-1) + a(k), a(k) は 1 ～ n のいずれか

の場合から

　S(1) < S(2) < ... < S(k-1) < S(k) <= n

の場合を引いたもの，と同じです。

そこで，まず，

　S(1) < S(2) < ... < S(k-1) <= n, S(k) = S(k-1) + a(k), a(k) は 1 ～ n のいずれか

k 回目の a(k) は 1 ～ n の n 通り

k-1 回目までは 1 ～ n から k-1 枚を選び小さい順に並べればよく nC(k-1) 通り

なので，n * nC(k-1) 通り。

次に，

　S(1) < S(2) < ... < S(k-1) < S(k) <= n

1 ～ n から k 枚を選び小さい順に並べればよく nCk 通り。

前者から後者を引くと，

n * nC(k-1) - nCk

= n * n!/(n-k+1)!(k-1)! - n!/(n-k)!k!

= n!/(n-k+1)!k! * (nk - (n-k+1))

= n!/(n-k+1)!k! * (n+1)(k-1)

= (k-1) * (n+1)!/(n+1-k)!k!

= (k-1) * (n+1)Ck 通り

そこで，求める確率 P(k) は，

P(k) = ((k-1) * (n+1)Ck)/n^k

になります。

(考察)

前回，第２３８回，の問題とは，次のように考えれば対応が付くようです。

前回の問題は，

　1 ～ n までの数が書かれたカードの中から 1 枚を選び，その数を記録して元に戻す，

　を繰り返し，取り出したカードの数が直前の数以下ならば終了する

というものでした。

これは，i 回目に取り出したカードの数を c(i) とすると，k 回目で終了するのは，

　c(1) < c(2) < ... < c(k-1), c(k) <= c(k-1)

です。そこで，終了しないためには c(k) が狭義に単調増加しなければならず，

1 <= c(k) <= n なので，多くとも n+1 回行うと終了します。

一方で，今回の問題では，この c(i) に対応するのが S(i) で，

　S(1) < S(2) < ... < S(k-1) <= n < S(k)

となっています。一見，終了条件が違いますが，

　c(k-1) に対して k 回目で終了する c(k) は c(k-1) 通り

　S(k-1) に対して k 回目で終了する S(k) は n - (n - S(k-1)) = S(k-1) 通り

と，場合の数としては同じになっています。

この対応のおかげで，同じ結果が得られるものと思われます。

(感想)

一見違う前回，第２３８回，の問題と，計算式まで含めて同じになったのは驚きでしが，

(考察)のように考えれば，自然な一致だと思われます。

しかし，こんな所にも e が現れるのは不思議です。

前回同様，興味深い問題でした。

NO2「ｽﾓｰｸﾏﾝ」　03/31 00時59分受信

「ｽﾓｰｸﾏﾝ」　03/31 19時06分受信

「ｽﾓｰｸﾏﾝ」　04/04 11時58分受信

「ｽﾓｰｸﾏﾝ」　04/06 18時37分受信更新4/18

問題１：一つのサイコロを繰り返し振って、出た目の和が６を超えるまで振り続ける。
サイコロを振る回数の期待値を求めよ。

６回で６になる場合...1,1,1,1,1,1 だけ...1/6^6...期待値は x7...7/6^6
５回で６...1,1,1,1,1...6-5=1...5H1=5C1=5...5/6^5...x6...30/6^5
４回で６...1,1,1,1...6-4=2...4H2=5C2=10...10/6^4...x5...50/6^4
３回で６...1,1,1...6-3=3...3H3=5C3=10...10/6^3...x4...40/6^3
２回で６...1,1...6-2=4...2H4=5C4=5...5/6^2...x3...15/6^2
１回で６...1/6...x2...2/6

５回で５...1,1,1,1,1 だけ...1/6^5...期待値は x(5/6)*6...30/6^6
４回で５...4H1=4C1=4...4/6^4...x(5/6)*5...100/6^5
３回で５...3H2=4C2=6...6/6^3...x(5/6)*4...120/6^4
２回で５...2H3=4C1=4...4/6^2...x(5/6)*3...60/6^3
１回で５...1/6...x(5/6)*2...10/6^2

４回で4...1,1,1,1 だけ...1/6^4...期待値は x(4/6)*5...20/6^5
３回で４...3H1=3C1=3...3/6^3...x(4/6)*4...48/6^4
２回で４...2H2=3C2=3...3/6^2...x(4/6)*3...36/6^3
１回で４...1/6...x(4/6)*2...8/6^2

３回で３...1,1,1 だけ...1/6^3...期待値は x(3/6)*4...12/6^4
２回で３...2H1=2C1=2...2/6^2...x(3/6)*3...18/6^3
１回で３...1/6...x(3/6)*2...6/6^2

２回で２...1,1 だけ...1/6^2...期待値は x(2/6)*3...6/6^3
１回で２...1/6...x(2/6)*2...4/6^2

１回で１...1 だけ...1/6...期待値は x(1/6)*2....2/6^2

合計
=(7+30*6+50*6^2+40*6^3+15*6^4+2*6^5+30+100*6+120*6^2+60*6^3+10*6^4+20*6+48*6^2+36*6^3+8*6^4+12*6^2+18*6^3+6*6^4+6*6^3+4*6^4+2*6^4)/6^6
=117649/46656
=2.5216263...

巧い方法があるのかなぁ...疲労困憊...^^;

NO3「再出発」　 04/12 01時32分受信

「再出発」　 04/15 23時22分受信更新4/18

寄せられた解答です。

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。