ザ計算力

MSNコミュニティ「物理とともに」において「どてらβ」さんによって出題された問題
『n(≦364)人の集団に対して、その中に自分と誕生日の月日が一致する他人が存在する人のみ挙手せよ、と要求したときに、挙手者数の期待値を求めよ。』
に対する私の解答を本件への返信として投稿する。
ただし、本件に対する返信として投稿されるメッセージは、「物理とともに」に投稿されたメッセージとは異なる。

正解を算出するだけなら、私の解法よりもシンプルな解法が存在する事を、複数の人から教えてもらったが、それらの解法には途中に論理の飛躍があり、それについて私が尋ねると、論理の飛躍を埋める方法は分からない、との事だった。
しかし、それらシンプルな解法は直感的に説得力が大きかったので、論理の飛躍を埋める方法は多分あるだろう、と思う。
したがって、このトピックは、解法の良さを紹介するためのものではなく、計算力の大きさを紹介するためのものだ。

出題時期は、私の手持ちの資料からは正確には特定できないが、この問題について2004年春に投稿されたメッセージのコピーが残っていたので、それ以前に出題されたと考えられる。
資料によると、2004年春に既に私は、アルゴリズムを案出して提示したが計算ミスで正解に至る事が出来ず、後で必ず解きます、と公言していたらしい。
実際に解いたのは2006年頃の様だ。
私は、最初REDwebSTARというニックネームで「物理とともに」に参加しており、途中からニックネームSourceCodeOf_HumanGenomeで参加する方式に切り替えた。
SourceCodeOf_HumanGenomeアカウントの開始時期は2005年05月11日だ、という資料も残っている。
また、REDwebSTAR時代に、この問題で「物理とともに」内に喧嘩が勃発していたらしい。
マイクロソフト社が2009年02月にMSNコミュニティサービスを終了したため、MSNコミュニティ「物理とともに」は、現在は存在しない。

---
最終更新日時2011年01月04日10:48JST

字が小さくて読みにくい時には、[Ctrl]ボタンを押した状態でマウスホイールを使うと拡大して読む事が出来ます。

年間の月日を1から365までの自然数で表す事にする。
また、集団の構成員には1からnまでの番号を振っておく。
さらに、構成員iの誕生日をa_iと書く事にする。
すると、各場合はn項数列a₁,a₂,・・・,a_nで表される。

数列の各項は独立に1から365までの任意の自然数を値として取るから、全ての場合の数は365ⁿであり、挙手者数の期待値は、
Σ_m=0ⁿ [(挙手者数がmである場合の数)/365ⁿ]×m

---
最終更新日時2011年01月22日09:59JST

誕生月日がjである様な人の人数をq_jと書く事にする。
1から365までの番号の付いた365個の部屋を用意し、全員に自分の誕生月日に対応する番号の部屋に入ってもらうと、手を挙げなかった人の人数は、人が1人だけ入っている部屋の個数に等しい。
つまり、手を挙げなかった人の人数はq_j=1であるようなjの個数だ。
全員の人数から手を挙げなかった人の人数を差し引けば挙手者数が求まるから、

挙手者数 = n - [q_j=1であるようなjの個数]
= n - Σ_j=1³⁶⁵　δ(q_j,1)

ただし、δはクロネッカーのデルタで、
x = y ならば δ(x,y) = 1,
x ≠ y ならば δ(x,y) = 0
という風に定義される。

因みに、
q_j = Σ_i=1ⁿ　δ(a_i,j)　
だから、この式を上記の挙手者数の式に代入して、
挙手者数 = n - Σ_j=1³⁶⁵　δ( Σ_i=1ⁿ δ(a_i,j) , 1 )　
と書く事が出来るが、この式は使わない。
---
最終更新日時2011年01月08日10:06JST

数列q₁,q₂,・・・,q₃₆₅を、n個の○の左および右および○と○の間に364枚の仕切り板を入れるパターンで図示できる。
左から数えてk-1番目の仕切り板とk番目の仕切り板の間にある○の個数がq_kだ。

｜｜｜○○｜｜○○○｜・・・・・｜○○○○○

この図だったら
q₁=0,q₂=0,q₃=0,q₄=2,q₅=0,q₆=3,・・・,q₃₆₅=5

この図法を私は、高校生の頃に大学入試のための受験勉強中に参考書で知った様に記憶している。
いわゆる受験テクニックも捨てたものではない。
---
更新日時2011/01/09/10:05JST

q_j≠0なるjを、小さい方から順にj(1),j(2),・・・,j(n')とし、
p(1)=q_j(1),p(2)=q_j(2),・・・,p(n')=q_j(n')
によって数列p(1),p(2),・・・,p(n')を定義する。
n'は、q_j≠0なるjの個数、つまり、年間の月日の内で誰かの誕生日に成っている月日の個数だ。

この事は、解答(その3)の図で言うと、左から順に仕切り板と仕切り板の間にある○の個数(0以外)をp(1),p(2),・・・,p(n')とする事に相当する。

因みに、
n = Σ_j=1^n' p(j)
が成り立つ。

このpを用いて書くと、解答(その2)の式は、
挙手者数 = n - Σ_j=1^n'　δ(p(j),1)

---
最終更新日時2011年01月17日10:11JST

本件「解答(その5)」の内容は、削除されました。
後で使うだろう、と思って書いたのですが、結局使わなかったからです。
---
最終更新日時2011年01月14日11:18JST

この後、まず、n';p(1),・・・,p(n')が与えられた時の図の個数を求める。
なぜならば、同一のn';p(1),・・・,p(n')に対応する場合の挙手者数は等しいからだ。
その次に、各々の図に対応する場合の数を求める。
すると、解答(その1)の考え方に従って、
(図の個数)×(各々の図に対応する場合の数)×(挙手者数)/(365ⁿ)
を全てのn';p(1),・・・,p(n')に渡って足し上げる事で、挙手者数の期待値を求める事が出来る。
---
最終更新日時2011/01/17/10:13JST

n';p(1),・・・,p(n')が与えられた場合の図の個数を求めたい。

n';p(1),・・・,p(n')が与えられた場合、仕切り板を挿入できる位置は、
　(第0隙)最も左の○の左、
　(第1隙)左から第p(1)番目の○と左から第p(1)+1番目の○の間、
　(第2隙)左から第p(1)+p(2)番目の○と左から第p(1)+p(2)+1番目の○の間、
　・・・
　(第n'-1隙)左から第p(1)+・・・+p(n'-1)番目の○と左から第p(1)+・・・+p(n'-1)+1番目の○の間、
　(第n'隙)最も右の○の右、
であり、この内で、第0隙と第n'隙には仕切り板が全く挿入されていなくてもよいが、それ以外の各隙には少なくとも1枚は仕切り板が挿入されていなくてはいけない。
さらに、仕切り板は全部で364枚なのだった。
しかし、これらの条件を満たしさえすれば、仕切り板の入れ方は任意なので、第j隙に挿入される仕切り板の枚数をk(j)とすると、求める図の個数は、条件を満たす数列：
k = (k(0),k(1),k(2),・・・,k(n'-1),k(n'))
の個数だ。

各jに対してk(j)が取り得る値の範囲を考える。
k(1)からk(n'-1)までが全て最小値1でk(n')=0の場合にk(0)は最大に成るから、
0≦k(0)≦364-(n'-1)
この範囲からk(0)の値が既に選ばれているなら、k(2)からk(n'-1)までが全て最小値1でk(n')=0の場合にk(1)は最大に成るから、
1≦k(1)≦364-k(0)-(n'-2)
以下同様にして、
1≦k(2)≦364-k(0)-k(1)-(n'-3)
・・・
1≦k(n'-1)≦364-k(0)-k(1)-・・・-k(n'-2)-0
この範囲から、k(0),k(1),・・・,k(n'-1)の値が既に選ばれているなら、k(n')の値は、
k(n') = 364-k(0)-k(1)-・・・-k(n'-2)-k(n'-1)
に決まってしまう。
数列k = (k(0),k(1),k(2),・・・,k(n'-1),k(n'))が満たすべき条件は以上だ。
したがって、その様な数列の個数は、
n'≧4では、Σ_k(0)=0^364-(n'-1) Σ_k(1)=1^{364-k(0)-(n'-2)} Σ_k(2)=1^{364-k(0)-k(1)-(n'-3)}・・・Σ_k(n'-1)=1^{364-k(0)-k(1)-・・・-k(n'-2)-0} 1
n'=3では、Σ_k(0)=0^364-(n'-1) Σ_k(1)=1^{364-k(0)-(n'-2)} Σ_k(2)=1^{364-k(0)-k(1)-(n'-3)} 1
n'=2では、Σ_k(0)=0^364-(n'-1) Σ_k(1)=1^{364-k(0)-(n'-2)} 1
n'=1では、Σ_k(0)=0^364-(n'-1) 1
で与えられる。
これはn'のみに依存し、p(1),・・・,p(n')には依存しない。

---
最終更新日時2011/01/18/09:32JST

解答(その7)のΣ和を計算するために、
N≧3では、σ(M,N) = Σ_i(1)=1^M Σ_i(2)=1^M-i(1)+1・・・Σ_i(N)=1^{M-i(1)-・・・-i(N-1)+(N-1)} 1
N=2では、σ(M,N) = Σ_i(1)=1^M Σ_i(2)=1^M-i(1)+1 1
N=1では、σ(M,N) = Σ_i(1)=1^M 1
N=0では、σ(M,N) = 1
と置いて、σ(M,N)に対する漸化式を立てたい。

このσ(M,N)を用いれば、n';p(1),・・・,p(n')が与えられた場合の図の個数は、
σ(364-(n'-1),n')+σ(364-(n'-2),n'-1)
と表せる事が、解答(その7)のΣ和をk(0)≠0の項とk(0)=0の項に分けて考える事によって、分かる。

σ(364-(n'-1),n')は、解答(その7)のΣ和の内のk(0)≠0の項に
k(0)=i(1),・・・,k(n'-1)=i(n')
という書き換えをすると得られる。
σ(364-(n'-2),n'-1)は、解答(その7)のΣ和の内のk(0)=0の項に
k(1)=i(1),・・・,k(n'-1)=i(n'-1)
という書き換えをすると得られる。
---
最終更新日時2011/01/23/09:43JST

解答(その8)より、N≧3では、
σ(M,N) = Σ_i(1)=1^M Σ_i(2)=1^M-i(1)+1・・・Σ_i(N)=1^{M-i(1)-・・・-i(N-1)+(N-1)} 1
= Σ_i(1)=1^M σ(M-i(1)+1,N-1)
だから、σ(M,N)に対する漸化式は、
σ(M,N) = Σ_i=1^M σ(M-i+1,N-1)

σ(M,2)を実際に計算してみると、
σ(M,2) = Σ_i(1)=1^M Σ_i(2)=1^M-i(1)+1 1
= Σ_i(1)=1^M [M-i(1)+1]
= M(M+1) - Σ_i(1)=1^M i(1)
= M(M+1) - (1/2)M(M+1)
= (1/2)M(M+1)
= (M+2-1)!/[2!(M-1)!]
この事から、一般項は
σ(M,N)= (M+N-1)!/[N!(M-1)!]
ではないか、と予想して、これを数学的帰納法で証明する。

σ(M,N)= (M+N-1)!/[N!(M-1)!]ならば、上で求めた漸化式によって、
σ(M,N+1)= Σ_i=1^M σ(M-i+1,N)
= Σ_i=1^M (M-i+1+N-1)!/[N!(M-i+1-1)!]
= Σ_i=1^M (M-i+N)!/[N!(M-i)!]
= Σ_i=1^M _M-i+NC_N
= Σ_j=0^M-1 _j+NC_N (j≡M-i)
= _M+NC_N+1 ∵数学公式
= (M+N+1-1)!/[(N+1)!(M-1)!]

故に、数学的帰納法によって、N≧2では、
σ(M,N)= (M+N-1)!/[N!(M-1)!]

N=1では、(M+N-1)!/[N!(M-1)!] = M!/(M-1)! = M
一方、解答(その8)のσ(M,1)の定義によってσ(M,1)= M
故に、N=1でも、σ(M,N)= (M+N-1)!/[N!(M-1)!]

N=0では、(M+N-1)!/[N!(M-1)!] = (M-1)!/(M-1)! = 1
一方、解答(その8)のσ(M,0)の定義によってσ(M,0)= 1
故に、N=0でも、σ(M,N)= (M+N-1)!/[N!(M-1)!]

以上によって、N=0,1,2,・・・に対して、
σ(M,N)= (M+N-1)!/[N!(M-1)!] = _M+N-1C_N
---
最終更新日時2010/12/15/16:02JST