ここ数年の話なのですが，何かを成し遂げたり，何かの節目だったりすると，
頑張った自分に対して，何かしらのご褒美を用意するようにしています。
今回は，半年間授業を頑張った自分へのご褒美として，
こんなものを買っちゃいました！
ヘルスメーターです！
むちゃくちゃ安かった上に，本体は B5 サイズと，その小柄なボディに惚れて即購入！
体脂肪を測ったりとか，高度な機能はまったくありませんが，
場所は取らないし，一番知りたい体重は教えてくれるし，
個人的にはなかなか気に入ってます！
とりあえず，目指すは現状維持！！（欲を言えば，2 kg 減）
————— ｷﾘﾄﾘｾﾝ 8X —————
ご褒美に浮かれてばかりじゃいられない，ってことで，
第 2 章の範囲で苦手な確率の問題を紹介ー！
[問題]
キー値の分布が 1 ～ 1,000,000 の範囲で一様にランダムであるデータ 5 個を，大きさ 10 のハッシュ表に登録する場合，衝突の起こる確率はおよそいくらか。ここで，ハッシュ値はキー値をハッシュ表の大きさで割った余りを用いる。
(ア) 0.2 (イ) 0.5 (ウ) 0.7 (エ) 0.9
この問題は，まず，衝突の起こらない確率について考え，
そこから以下の式を元に，衝突の起こる確率を求めて，問題を解いていきます。
1 – 衝突の起こらない確率 = 衝突の起こる確率 …(a)
ちなみに，ハッシュ値を求める場合，
必ず，衝突が起こるか起こらないかのどちらかの場合になるため，
衝突が起こる場合 + 衝突の起こらない場合 = すべての場合(= 1)
が成り立つことから，(a) の式を導くことができます。
なお，問題文の赤色の部分から，ハッシュ表のハッシュ値は，
キー値をハッシュ表の大きさ 10 で割った余りなので，
キー値 / 10 の 余り = 0 ～ 9 の 10 個の値のいずれか
ということが分かります。
続いて，5 つのデータにおける，衝突の起こらない確率ですが，
これは，それぞれの場合についての可能性を順番に考えていけば OK です。
・ 最初（1 つ目）のデータの場合
→ まだ，ハッシュ表にはデータが 1 つも格納されていないので，
最初のデータのハッシュ値は 0 ～ 9 のどの値でも構いません。
よって，衝突が起こらない可能性は 1（10 分 の10）となります。
・ 2 つ目のデータの場合
→ ハッシュ表には，すでに 1 つのデータが格納されているので，
2 つ目のデータのハッシュ値は，最初のデータのハッシュ値以外の
9 個の値のうちのいずれか，でなければなりません。
つまり，衝突が起こらない可能性は 0.9（10 分の 9）となります。
・ 3 つ目のデータの場合
→ 2 つ目のデータと同様に，すでに 2 つのデータがハッシュ表に格納されているので，
3 つ目のデータのハッシュ値は，8 個の値のうちのいずれか，になります。
したがって，衝突が起こらない可能性は 0.8（10 分の 8）です。
・ 4 つ目のデータ，5 つ目のデータの場合
→ 2 つめ以降にならって，それぞれの衝突の起こらない可能性を考えると，
4 つ目のデータの場合は 0.7（10 分の 7），
5 つ目のデータの場合は 0.6（10 分の 6）となります。
以上の可能性は，同時には起こらないので，
1 × 0.9 × 0.8 × 0.7 × 0.6 = 0.3024（衝突の起こらない確率）
となります。
これを (a) の式に当てはめると，1 – 0.3024 ≒ 0.7 となり，
正解は (ウ) であることが分かります。
