太郎さんは、生徒と共に修学旅行に行きます。ホテル泊まってシングルルームで休んでいたとき、「先生大変です。すぐ来てください。」と言う生徒の声に夢中で飛び出して、失敗しことがあります。実は、自動ロックのドアーでして、鍵を持たずに飛び出したのです。幸いフロントに言って、合い鍵を使って、助かったことがあります。

　さて、あるいたずら好きな子供が、幾つかの部屋の別々な鍵を、適当に各室に１個ずつ入れ、

自動ロックのドアーを閉めてしまいました。あいにく、合い鍵がないので、ドアーをこわさなければなりません。

その部屋に別の部屋の鍵があれば、そこはこわさずに開くことができます。全部の部屋を開けるのに、

こわさなければならないドアーの個数の期待値を求めなさい。

問題１：まず、部屋の数をｎとして、ｎ＝１，２，３，４の場合を考えてください。

問題２：部屋の数をｎとして、ｎ＝５のときの場合を考えてください。

＜発展＞一般のｎ部屋の場合、こわさなければならないドアーの個数の期待値を求めたいのですが、

太郎さんは、正直なところ、まだ、解答に至っていません。解けた人は教えてください。

＜SambaGREEN＞さんからの解答　６日午前０時３０分受信　７日更新　

第38回連続応募問題の解答です。

ｎ＝１のとき　１，ｎ＝２のとき　3/2　まではやりましたが，

風邪せいか，場合分けが混乱してきたので，いきなり，一般形で考えました。

したがって，結果は検証できていません。間違っていたらご指摘をお願いします。

部屋の数がｎのときの壊すドアの期待値をＸ(n)とし，

最初の１部屋は鍵を開けてはいるときの壊すドアの期待値をＹ(n)とする。

入った部屋にその部屋の鍵がある確率は１/ｎ

他の部屋の鍵がある確率は(ｎ-1)/ｎであるから，

Ｘ(n)＝１＋１/ｎ＊Ｘ(n-1)＋(ｎ-1)/ｎ＊Ｙ(n-1)・・・�@

ここで，Ｙ(n)について考える。

Ｙ(1)＝0，であり，ｎ≧２のとき

入った部屋以外のn-1部屋の鍵と，直前に壊した部屋の鍵が残っている事になる。

Ｙ(n)＝Ｘ(n)−１が成り立つから，�@式に代入して整理すると

Ｘ(n)＝Ｘ(n-1)＋１/ｎ

したがって，Ｘ(n)＝１＋1/2＋1/3＋・・・1/ｎ

＜四年寝太郎＞さんからの解答　６日午前１０時受信　７日更新　

以下説明のため、部屋を１号室、２号室、３号室、・・・と表し、１番目、２番目、３番目、・・・

と書いた場合は何番目に開けた部屋かを表すとする。

開けていない部屋の、どの部屋の鍵も持っていない場合にどの部屋を開ける

ことにしても期待値は変わらないから、小さい番号の部屋を開けることにする。

また説明のため、ｎ部屋の場合の壊さなければならないドアの個数の期待値をＰ(ｎ)と表すことにする。

問題１

ｎ＝１：１号室の鍵は部屋の中にあるから絶対に壊さなければならない。

Ｐ(１)＝１

ｎ＝２：１号室に２号室の部屋の鍵がある確率は１／２だから

Ｐ(２)＝１＋１／２＝３／２

ｎ＝３：１号室に２or３号室の鍵がなければ(１号室の鍵しかなければ)壊さなければならない残りのドアの

　　　　個数の期待値はｎ＝２の時と同じ。また、１号室に２or３号室の鍵があり、２番目の部屋に３番目

　　　　の部屋の鍵があれば３番目の部屋は壊さなくて良い。なければ(１号室の鍵しかなければ)３番目の

　　　　部屋は壊さなければならない。

Ｐ(３)＝１＋３／２＊１／３＋１＊１／２＊２／３＝１１／６

ｎ＝４：１号室に残りの部屋の鍵がない(１号室の鍵しかない)場合、壊さなければならない残りのドアの個数

　　　　の期待値はｎ＝３の時と同じ。残りの部屋の鍵があれば、２番目の部屋は壊さなくても良い。

　　　　また、２番目の部屋に残りの部屋の鍵がなければ(１号室の鍵しかなければ)、

　　　壊さなければならない残りのドアの個数の期待値はｎ＝２の時と同じ。　

　　　２番目の部屋に残りの部屋の鍵があれば３番目の部屋は壊さなくて良い。

３番目の部屋には残りの部屋の鍵がなければ(１号室の鍵しかなければ)４番目の部屋は壊さなければならない。

Ｐ(４)＝１＋１１／６＊１／４＋３／２＊３／４＊１／３

＋１＊３／４＊２／３＊１／２＝２５／１２

　　　　よって、Ｐ(５)＝１３７／６０

問題２

問題１の計算結果より、期待値は

n

Ｐ(ｎ)＝１＋ΣＰ(ｉ)／ｎ

i=1

n

＝Σ(１／ｉ)

i=1

問題２の別解？

問題を見て分かるように開け始めた部屋の鍵を見つけるまで、ドアを壊さな

いで次の部屋を開けることが出来る。これを一種の置換と見なせば、

n

Ｐ(ｎ)＝Σ (i-1)Ｃn-1 ＊ｉ／ｎ！

i=1

以上まで考えたのですが、やはり、一般解をｎで表せません。数列は難しいですね。また分かったらメール書きます。

＜ch3cooh＞さんからの解答　６日午後１時受信　７日更新　

一般解として、

部屋の名前を A, B, C, D... とし、各部屋の鍵を a, b, c, d... とします。

かぎは、各部屋に一つずつ完全ランダムに入っているとします。

また、鍵を壊す回数は出来るだけ減らすようにします。

その場合、どの部屋から壊し始めても、全く同じ確率でしか壊す回数を減らせません。

まず、A の部屋の鍵を壊すものとします。

1) Aの部屋の鍵が格納されている場合。

こうなる確率は 1/N です。 また、この後の部屋で壊さなければならない回数は f(N-1) です。

2) A以外の部屋の鍵が格納されている場合。

こうなる確率は、(N-1)/N です。

この場合、Aの部屋に格納されていた鍵の部屋を次に開けるものとします。

その場合、最初の部屋の分だけ壊さなくても良いので、全ての壊さなくてはならない確率は f(N-1)です。

つまり、この方法で部屋を開けていった場合、

f(N)= (1/N)*(f(N-1)+1)+((N-1)/N)*f(N-1)

= f(N-1)+ 1/N　　　　ただし、 f(N)= です。

さて、上記の方法よりも効率の良い部屋の開け方があるでしょうか？

これは、現在までに開けた部屋以外の鍵を見つけた場合でも、その鍵を使用する

よりも違う部屋の鍵を壊したほうが効率が良い方法があれば、違う方法が存在することになります。

厳密な証明は、分かりませんが、多分無さそうなので上記の方法がbestだと思います。

･･･ 高校とかの算数を忘れてしまったので、上記の式の一般解の式が思い出せません。

答え:

f(1)= 1

f(2)= 3/2

f(3)= 11/6

f(4)= 25/12

f(5)= 137/60

＜浜田＞さんからの解答　７日午後２時受信　８日更新　

ドアの破損数の問題の解答　いつものようにプログラムで解いてみました．今回はエクセルのマクロです．

　部屋１から部屋ｎまでに，それぞれ鍵１から鍵ｎを乱数により配布します．部屋１からドアを壊し始め，取り出した鍵から，新たにその鍵の部屋を開けていき，これを最後の部屋が開けられるまで続け，最終的な破損数を求めます．この試行を１万回繰り返し，期待値を求めます．この試行により，次の結果を得ました．

ｎ 期待値

1 1

2 1.4959(≒3/2)

3 1.833 (≒11/6)

4 2.0838(≒25/12)

5 2.2814(≒137/60)

6 2.4473(≒49/20)

7 2.594 (≒363/140)

試行回数を増やせば，もっと正確な値が得られるでしょう．しかしそれでは時間がかかるので，この辺が妥当な線ではないかと思います．

Sub door()

Randomize Timer

Dim n, j, jj, kagi(7), kk, door(7), hason, dame As Integer

Dim kaisuu, shikoukaisuu, kekka(7) As Long: shikoukaisuu = 10000

For j = 1 To 7: kekka(j) = 0: Next

Cells(1, 1).Value = "試行回数": Cells(2, 1).Value = "ｎ"

Cells(2, 2).Value = "期待値": Cells(2, 3).Value = "破損数"

For j = 1 To 7

Cells(2, j + 3) = "部屋" + Str(j): Cells(j + 2, 1).Value = j

Next

For kaisuu = 1 To shikoukaisuu: For n = 1 To 7

For j = 1 To n - 1: dame = 1

While dame = 1: kagi(j) = Int(Rnd * n) + 1: dame = 0: jj = 1

While dame = 0 And jj < j

dame = -(kagi(j) = kagi(jj)): jj = jj + 1

Wend: Wend

Next

kagi(n) = n: For j = 1 To n - 1: kagi(n) = kagi(n) + j - kagi(j): Next

For j = 1 To n: door(j) = 0: Next: hason = 0

For j = 1 To n

If door(j) = 0 Then

hason = hason + 1

kk = j: For jj = j To n: door(kk) = 1: kk = kagi(kk): Next

End If

Next

kekka(n) = kekka(n) + hason

Cells(1, 2).Value = kaisuu

Cells(n + 2, 2).Value = kekka(n) / kaisuu: Cells(n + 2, 3).Value = hason

For j = 1 To n: Cells(n + 2, j + 3).Value = kagi(j): Next

Next: Next

　End Sub

答だけを求めるプログラムも作ってみました．それぞれの部屋に順番に鍵を入れて，破損の回数を求めて期待値を求めるものです．

Sub door2()

Dim n, j, jj, j1, j2, j3, j4, j5, j6, kagi(7), kk, door(7), hason, dame As Integer

Dim wa(7), kaisuu(7), dummy, amari As Long

Dim kitaichi As String

For j = 1 To 7: wa(j) = 0: kaisuu(j) = 0: Next

Cells(1, 1).Value = "ｎ": Cells(1, 2).Value = "期待値"

Cells(1, 3).Value = "破損数"

For j = 1 To 7

Cells(1, j + 3) = "部屋" + Str(j): Cells(j + 1, 1).Value = j

Next

For n = 1 To 7

For j1 = 1 To n: kagi(1) = j1

If n = 1 Then

GoSub count

Else

For j2 = 1 To n

If j1 <> j2 Then

kagi(2) = j2

If n = 2 Then

GoSub count

Else

For j3 = 1 To n

If j1 <> j3 And j2 <> j3 Then

kagi(3) = j3

If n = 3 Then

GoSub count

Else

For j4 = 1 To n

If j1 <> j4 And j2 <> j4 And j3 <> j4 Then

kagi(4) = j4

If n = 4 Then

GoSub count

Else

For j5 = 1 To n

If j1 <> j5 And j2 <> j5 And j3 <> j5 And j4 <> j5 Then

kagi(5) = j5

If n = 5 Then

GoSub count

Else

For j6 = 1 To n

If j1 <> j6 And j2 <> j6 And j3 <> j6 And j4 <> j6 And j5 <> j6 Then

kagi(6) = j6

If n = 7 Then

kagi(7) = 7

For j = 1 To 7 - 1

kagi(7) = kagi(7) + j - kagi(j)

Next

End If

GoSub count

End If

Next

End If

End If

Next

End If

End If

Next

End If

End If

Next

End If

End If

Next

End If

Next

Next

End

count:

kaisuu(n) = kaisuu(n) + 1

For j = 1 To n: door(j) = 0: Next: hason = 0

For j = 1 To n

If door(j) = 0 Then

hason = hason + 1

kk = j: For jj = j To n: door(kk) = 1: kk = kagi(kk): Next

End If

Next

wa(n) = wa(n) + hason

GoSub yakubun: Cells(n + 1, 2).Value = kitaichi

Cells(n + 1, 3).Value = hason

For j = 1 To n: Cells(n + 1, j + 3).Value = kagi(j): Next

Return

yakubun:

x = kaisuu(n): y = wa(n)

If x < y Then dummy = x: x = y: y = dummy

While y > 0: amari = x Mod y: x = y: y = amari: Wend

bumbo = kaisuu(n) / x: bunshi = wa(n) / x

kitaichi = Str(bunshi)

If bumbo > 1 Then kitaichi = kitaichi + " / " + Str(bumbo)

Return

End Sub

ちなみにこの問題は，数学セミナー９７年９月号エレガントな解答をもとむの金庫の問題とほぼ同様です．その問題では金庫には別の鍵を入れるとなっていました．今回のプログラムはそのときに作ったものとは別の発想で作りました．

＜Ｊｕｎ＞さんからの解答　７日１９時受信　８日更新

さてドア-の破損数ですが、部屋数ｎとしたときのこわさなければならないドア-の個数

の期待値をｆ（ｎ）とするならば、

ｆ（ｎ）＝１＋１／２＋１／３＋１／４＋・・・１／ｎ

となりませんか？

これから時間が許せば、レポ−トします。

＜水の流れ：コメント＞　今回こんなに多くの方からの解答ありがとうございます。

嬉しいかぎりです。また、身近な生活からの作問していきます。　「数学セミナー９７年９月号エレガントな解答をもとむの金庫の問題とほぼ同様です　」と、ご指摘頂きましたが、知りませんでした。類似問題が出ていたのですね。