◆東京都 しんちー さんからの解答。
簡単のため、メモった文字列は
AAA…AAABB…BB
であるとしてよい。
また求める値を I とおく。
なお、和の k の範囲は 0 から2000 までであるとしてよい。
後の都合で P(k) の代わりに N(k) を使う。
シャッフルした後のカードの並びの総数は
2000C1001 であり、これを N とおく。
すると
| I = | 2000 Σ k=0 | (2000-k)N(k) |
だから両辺を N で割って
| I/N = | 2000 Σ k=0 | 2000/N×N(k) | - | 2000 Σ k=0 | k×N(k)/N |
すなわち
I/N = 2000/N×N-E(k) = 2000-E(k)
よって
I = N×(2000-E(k))
以下 E(k) (= 確率変数 k の期待値) を求める。
まず本問において、A が何枚一致したかの枚数を X で表わす。
すると
P(X=n) = (1001Cn × 999C1001-n)/2000C1001であり、X は超幾何分布に従う。
E(X) = 1001 × 1001/2000
である。ここで、
k = X + {999 - (1001-X)} = 2X-2
であるから
E(k) = E(2X-2)
= 2E(X)-2
= 10012/1000 - 2
= (1000 +1)2/1000 -2
= (10002 + 2×1000 +1)/1000 -2
= 1000 + 1/1000
したがって求める I は
I = N × {2000 - (1000 + 1/1000)}
= N × (1000 - 1/1000)
= 2000C1001 × 999999/1000
= 999999/1000 × (2000×1999×…×1000)/(1001×1000×…×1)
= (999999×2000)/(1000×1001) × (1999×…×1000)/(1000×…×1)
= (999×2) × 1999C1000
ここで 1999C1000 が整数であることを認めれば、(証明終)
注意：
超幾何分布というのは
A をM個、B をN-M個 (つまりあわせてN個) 袋にいれてn個取り出したときに含まれている A の個数 x が従う分布で、確率は
P(x) = {MCx×N-MCn-x}/NCn
で与えられます。
この時 x の期待値は
E(x) = n × M/N … (*)
となります。
直観的には当たり前。
なぜなら世の中に男が60%、女が40%いるとすれば100人適当に選ぶと男60人、女40人になると考えられるから。
(*) については Combination の性質と二項定理を使えば示せます。
(感想)
地道に計算をやろうとおもったら煩雑だったので、
・何らかの確率分布の期待値を使う。
・その分布はおそらく超幾何分布である。
を方針としてやりました。
なので根本にあるこれらが間違っていたらアウトですね。
個人的にはこの分野は好きなのですが。
あと、これは1999が素数だからうまくいくのか、が気になるところです。
◆東京都 建築家 さんからの解答。
まず最初に、999枚あるAのうちr枚上とそろっていたとすると、A,Bの枚数は変わらないので
Bは(r+2)枚が上とそろっていることとなる。
k=r+(r+2)枚がそろった場合は
P(k)=P(2r+2)=1001Cr+2×999Cr 通りである。これより
| 2000 k=0 | P(k) ＝ | 999 r=0 | P(2r+2) ＝ Σ1001Cr+2×999Cr |
となる。
一方例えば1999枚のうちA,Bがそれぞれ999,1000枚ずつあったとしたら、その並べ方は
| 999 k=0 | 1000Ck+1 × 999Ck ＝ | 1999! 1000!×999! | ≡ 0 (mod 1999) |
で1999で割れる。 同様に2000枚のうちA,Bがそれぞれ999,1001枚ずつあるなら
| 2000 k=0 | P(k) ＝ | 999 k=0 | 1001Ck+2 × 999Ck ＝ | 2000! 1001!×999! | ≡ 0 (mod 1999) |
とこれも1999で割れる。
そこで問題は (mod 1999で計算する。)
| 1999 k=0 | (2000-k)P(k) |
| ＝ | 2000 k=0 | { | (2000-k)P(k) }-(2000-1)P(2000) |
| ≡ | 2000 k=0 | {(1-(2r+2))P(2r+2) }-1999 |
| ≡ | 2000 k=0 | 3×P(k) - | 999 r=0 | {(2r+4)1001Cr+2×999 Cr} |
| ≡ | 999 r=0 | {(2r+4)× | 1001 r+2 |
1000Ck+1×999Ck} |
| ≡2002 | 999 r=0 | {1000Cr+1×999Cr} |
| ≡ ０ (mod 1999) ■ |