鳩の巣原理とは？
はとのすげんり
「原理」の用語まとめを見る鳩の巣原理とは、n+1個のものをn個の箱に入れると、少なくとも1つの箱に2個以上入ることが必ず成り立つという数学の基本原理です。
鳩の巣原理（はとのすげんり）は、組合せ論・離散数学における最も基本的な定理の一つです。「n個の巣箱にn+1羽以上の鳩を入れると、少なくとも1つの巣箱には必ず2羽以上の鳩が入る」という事実をモデルにしており、英語では「Pigeonhole Principle」と呼ばれます。ドイツの数学者ディリクレが提唱したことから「ディリクレの引き出し原理」とも呼ばれます。
この原理は一見すると当然のことのように思えますが、複雑な問題を解くための強力な論証ツールになります。例えば、「東京都の人口は23区内の道路交差点の数より多いため、同じ交差点を1度以上通る人が必ず存在する」といった推論が可能です。
代表的な応用例としては次のものがあります。
- グラフ理論における辺の存在証明
- 数列の中に同じ余りを持つ数が必ず存在することの証明
- 暗号理論における衝突（ハッシュの重複）の必然性の説明
- 誕生日のパラドックス（23人いれば同じ誕生日の人が存在する確率が5割超）の説明
この原理の重要な点は「少なくとも1つは必ず重複する」という存在の保証を、具体的な構成なしに行えることです。数学的証明や情報科学・暗号理論など幅広い分野で応用されています。
使い方・例文
「366人以上いれば、必ず同じ誕生日の人が存在すると証明するのに鳩の巣原理が使われる。」のように、数学の証明問題で登場します。
この用語をシェア
最終更新: