、ウ、ホ・レ。シ・ク、、マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、爨マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ 、ウ、ホ・レ。シ・ク、livedoor ・ッ・・テ・ラ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、瀝ivedoor ・ッ・・テ・ラ

フワシ。

・ミ。シ・ケ・ヌ・」・ム・鬣ノ・テ・ッ・ケ

。。ネキ、ホチ羣カヘ、隍遙「366ソヘスク、゙、、ネ。「テツタクニ、ャーテラ、ケ、・レ・「、ャノャ、コ。ハウホホィ1、ヌ。ヒツクコ゚、ケ、。」

。。、ヌ、マホ网ィ、ミ20ソヘスク、゙、テ、ソセケ遉マ、ノ、ヲ、タ、、ヲ、ォ。ゥ
。。テツタクニ、マ365トフ、熙ォ、鬣鬣・タ・爨ヒチェ、ミ、、、ホ、ヌ。「トセエカナェ、ヒ、マテツタクニ、ャーテラ、ケ、・レ・「、ャツクコ゚、ケ、ウホホィ、マ、ネ、ニ、籠网、、隍ヲ、ヒエカ、ク、。」、キ、ォ、キ。「シツコン、ヒ、マケ筅、ウホホィ、ヌテツタクニ、ャーテラ、ケ、・レ・「、ャツクコ゚、ケ、。」、ウ、、・ミ。シ・ケ・ヌ・」・ム・鬣ノ・テ・ッ・ケ、ネクニ、ヨ。」

[トヘ]
qクト、ホ・ワ。シ・、nクト、ホ・ミ・ア・ト、ヒ・鬣・タ・爨ヒナ熙イニ、、ソ、ネイセト熙ケ、。」
、ウ、ホ、ネ、ュ。「2クトーハセ螟ホ・ワ。シ・、ャニ、・ミ・ア・ト、ャセッ、ハ、ッ、ネ、筅メ、ネ、トツクコ゚、ケ、ウホホィ、Pcoll、ネ、ケ、、ネ。「シ。、ホ、隍ヲ、ヒ、ハ、。」

P_{coll}~\ge~1~-~e^{-\frac{q(q-1)}{2n}}

、゙、ソ。「1。蚋。蠅(2n)、ヌ、「、、ミ。「P_{coll}~\ge~0.316~\times~\frac{q(q-1)}{2n}

ニテ、ヒ。「q=「蚣、ホ、ネ、ュ、マ。「P_{coll}~\ge~0.3

[セレフタ]スクケ轆a1,。ト,an}、ォ、駝クト、ホ(a1,。ト,aSUB{n})、チェ、、タ、ネ、ュ。「スナハ」、ャ、メ、ネ、ト、ヌ、筅「、ウホホィ、Pcoll、ネ、キ。「、ス、ホテヘ、オ皃皃ソ、、。」

。。、゙、ソ。「スクケ轆a1,。ト,an}、ォ、駝クト、ホ(a1,。ト,aSUB{n})、チェ、、タ、ネ、ュ。「、ケ、ル、ニーロ、ハ、セケ遉ネ、マ。「。ヨ(a_2~\not{=}~a_1)~\wedge~(a_3~\not{=}~a_2~\wedge~a_3~\not{=}~a_1)~\wedge~\cdots~\wedge~(a_k~\not{=}~a_{k-1}~\wedge~~\cdots~\wedge~a_k~\not{=}~a_2~\wedge~a_k~\not{=}~a_1)。ラ、ャタョ、ホゥ、ト、ネ、ュ、ヌ、「、。」、ウ、ホ、ネ、ュ、ホウホホィ、q、ネ、ケ、、ネ。「シ。、ホ、隍ヲ、ヒ、ハ、。」

q=1~\cdot~\frac{n-1}{n}~\cdot~\frac{n-2}{n}~\cdots~\frac{n-k+1}{n}
=(1-\frac{1}{n})~\cdot~(1-\frac{2}{n})~\cdots~(1-\frac{k-1}{n})
=\prod_{i=1}^{k-1}~(1-\frac{i}{n})。。「ォ(*)

。。Pcoll、ネq、ホエリキク、マシ。、ホ、隍ヲ、ヒ、ハ、。」

P_{coll}~=~1-q

。。、ネ、ウ、、ヌ。「、ケ、ル、ニ、ホシツソx。0、ヒツミ、キ、ニ。「1+x~\leq~e^x、ャタョ、ホゥ、ト。」、ウ、ホx、ヒx=-\frac{i}{n}、ツ衄、ケ、、ネ。「シ。、ャタョ、ホゥ、ト。」

1-\frac{i}{n}~\le~e^{-~\frac{i}{n}}

。。、ウ、、ホi=1。チk-1、゙、ヌ、ホセハユ、ウン、アササ、ケ、、ネ。「シ。、ホ、隍ヲ、ヒ、ハ、。」

\prod_{i=1}^{k-1}~(1-\frac{i}{n})~\le~\prod_{i=1}^{k-1}~e^{-~\frac{i}{n}}

。。(*)、隍遙「シ。、ャタョ、ホゥ、チ。「ナクウォ、キ、ニ、、、ッ、ネシ。、ホ、隍ヲ、ヒ、ハ、。」

q~\le~\prod_{i=1}^{k-1}~e^{-~\frac{i}{n}}
=~e^{\sum_{i=1}^{k-1}~\frac{i}{n}}
=~e^{\frac{-k(k-1)}{2n}}。。「ォ(**)

。。k~\ge~\frac{1+\sqrt{1+8n~\log{2}}}{2}、ヌ、「、、ミ。「(**)、ヒ、隍q~\le~\frac{1}{2}、ヌ、「、。」。。「「

ホ罍ァ40ソヘ、ホ・ッ・鬣ケ、ヌニア、クテツタクニ、ホ・レ・「、ャツクコ゚、ケ、ウホホィ、キラササ、キ、ニ、゚、。」、ス、ヲ、ケ、、ネ。「シ。、ホ、隍ヲ、ヒ、ハ、。」

1-1~\cdot~\frac{364}{365}~\cdot~\frac{363}{365}~\cdots~\cdot~\frac{326}{365}~=~0.88

。。、隍テ、ニ。「88%、ヌテツタクニ、ャセラニヘ、ケ、、隍ヲ、ハ・レ・「、ャツクコ゚、ケ、、ネ、、、ヲ、ウ、ネ、ヌ、「、。」チロチ、キ、ニ、、、ソ、隍熙篦遉ュ、、ウホホィ、ヌ、マ、ハ、、、タ、、ヲ、ォ。ゥ。。、ウ、ヲ、キ、ニチロチ、キ、ニ、、、ソウホホィ、ネソウリナェ、ハウホホィ、ャーロ、ハ、テ、ニ、、、、ホ、ヌ。「・ミ。シ・ケ・ヌ・」・ム・鬣ノ・テ・ッ・ケ、ネクニ、ミ、、スーハ、ヌ、「、。」

・ミ。シ・ケ・ヌ・」・ム・鬣ノ・テ・ッ・ケ、ネ・マ・テ・キ・蠕ラニヘ

[キマ]
・マ・テ・キ・蠹ヘ、ャヲハ・モ・テ・ネ、ホセケ遑「H、2ヲハ/2イキラササ、ケ、、ネ。「0.3ーハセ螟ホウホホィ、ヌセラニヘ・レ・「、ャオ皃゙、。」

[セレフタ]y=H(x)、ヒ、ェ、、、ニ。「x、・ワ。シ・、ホソ。「y、・ミ・ア・ト、ホソ、ネサラ、ィ、ミ、隍、。」

[フ臂ヌ、ーユ、ホ・モ・テ・ネホ、ォ、40・モ・テ・ネ、ホ・マ・テ・キ・蠹ヘ、オ皃皃・マ・テ・キ・蟠リソ、ケヘ、ィ、。」qクト、ホ・モ・テ・ネホ、・鬣・タ・爨ヒチェ、モ。「・マ・テ・キ・蠹ヘ、オ皃癸「セラニヘ、クォ、ト、ア、ソ、、。」セラニヘ、ャクォ、ト、ォ、、隍ヲ、ハウホホィ、1/2ーハセ螟ネ、ケ、、ソ、皃ヒ。「ノャヘラ、ハ・モ・テ・ネホ、ホクトソq、オ皃皃陦」

[イナ]

Pcoll=1/2、ネ、ケ、、ネ。「シ。、ホ、隍ヲ、ヒ、ハ、。」

\frac{1}{2}~=~0.316~\times~\frac{q(q-1)}{40}

20=0.316~\cdot~q(q-1)

q~\approx~1.24~\times~106

サイケヘハクク・

  • ・シ・゚
  • 。リクスツ蟆ナケ讀ホエチテソヘ。ル
  • 。リーナケ賚マタニフ遑ル。ハ・キ・螂ラ・・・ャ。シ。ヲ・ク・罕ム・。ヒ
  • 。リーナケ賚マタニフ遑。[ツ2ネヌ]。ル