鳩の巣原理（PHP）とは

 

ＰＨＰの問題はあまり関係ない？？

今日

あ、いい質問です。めちゃくちゃ関係あります。

むしろ、誕生日の問題は**「鳩の巣原理（PHP：Pigeonhole Principle）」**の確率バージョンです。

ごっちゃになりやすいので整理します。

1. 鳩の巣原理（PHP）とは

n個の巣に、n+1羽の鳩が入れば、必ずどこかの巣には2羽以上入る

誕生日で言うと：

• 巣 = 365日
• 鳩 = 人

366人いれば、100%同じ誕生日の人が2人いる。

これは数学の定理。絶対に覆らない。PHPは**「最悪ケースでいつ必ず起きるか」**を保証する話。

2. 誕生日のパラドックスとは

366人いなくても、もっと少ない人数で、高い確率で同じ誕生日が起きるよ

• 366人いれば確率100%（鳩の巣原理）
• 23人いれば確率50%（誕生日パラドックス）
• 50人いれば確率97%

PHPは**「いつ100%になるか」を教える。
誕生日問題は「何人で50%になるか」**を教える。

3. 関係を図にすると

Code

人数 ──────────►0人 ─── 23人 ─── 50人 ─── 366人      │        │         │      50%      97%       100%  ← 同じ誕生日がいる確率

つまり、

PHPは「天井」を決める。
誕生日の問題は「天井に至るまでの登り方」を決める。

なので、

「PHPの問題はあまり関係ない？」

に対する答えは、

**「いや、PHPが土台。PHPがなければ、誕生日の問題はそもそも存在しない」**です。

PHPが「いつかは必ず同じ誕生日が被る」ことを保証してくれているから、「じゃあ、何人で50%になる？」という次の確率の問題が生まれる。

日常生活や身近な例

この原理は当たり前のように思えますが、少し応用すると面白い事実が証明できます。

• 「髪の毛の本数が完全に同じ人」がどこかにいる
  人間の髪の毛の本数は、多くてもおよそ15万本（巣の数）と言われています。一方で、東京都の人口は約1400万人（鳩の数）です。人口（鳩）のほうが髪の毛の本数の最大値（巣）よりも圧倒的に多いため、「東京都内には、髪の毛の本数が1本単位で完全に一致する人が、少なくとも2人以上存在する」ことが数学的に証明されます。
• 手袋のペア
  暗闇の中で、引き出しから左右の区別がない黒と茶色の手袋を取り出すとします。3枚（鳩）取り出せば、色は2種類（巣）しかないので、絶対に同じ色のペア（2枚）が手に入ります。

コンピュータの世界（IT）での使われ方

あなたが先ほど質問されていた「不正アクセス」やセキュリティの分野、データ圧縮の技術でも、この鳩の巣原理が裏で大きく関わっています。

• データの「ハッシュ衝突」（セキュリティ）
  パスワードなどを暗号化（ハッシュ化）して管理する際、無限にあるデータ（鳩）を、決められた固定の長さの暗号データ（巣）に変換します。鳩の巣原理から、「理論上、異なる2つのデータが同じ暗号データに変換されてしまう確率が必ず存在する」ことになります。これを「ハッシュ衝突」と呼び、サイバー攻撃者はこの仕組みを突いてシステムを破ろうとすることがあります。
• データ圧縮の限界
  「どんなデータでも絶対にサイズを小さくできる魔法の圧縮ソフト」は作れません。なぜなら、もしすべてのデータを小さくできるとしたら、元の大きなデータ（鳩）に対して、圧縮後の小さなデータ（巣）の数が足りなくなり、解凍したときに別のファイルになってしまう（1つの巣に2つのデータが重なる）からです。

当たり前すぎるルールですが、数え切れないほどの組み合わせを整理したり、限界を証明したりするときに非常に重宝される大原則です。

鳩の巣原理について、知りたいきっかけは何でしたか？

• 数学やプログラミングの勉強で出てきましたか？
• それとも、先ほどの暗号やセキュリティの話に関連して気になりましたか？