想像してみてください、10羽のハトが自家製の鳩箱に飛び込んできましたが、あなたは9個しか作っていません。最後のハトはどこに行くのでしょうか?全体の鳩箱原理の背後にある物語は何ですか?
ロンドンの人口が人間の頭髪の最大本数を超えているため、鳩箱原理はロンドンの少なくとも二人が同じ本数の髪の毛を持っていることを要求します。この数学的原理は1624年から存在しています。
鳩箱原理
鳩箱原理は数学の最も基本的でありながら価値のある概念の一つです。1624年にさかのぼって記録されています。一般にはディリクレの箱原理またはディリクレの引き出し原理として知られています。(出典:Jeff 560)
最も単純な説明では、原理は10羽のハトが9つの鳩箱に集まると、少なくとも1つの鳩箱に2羽以上のハトが入ることを示しています。
定理では、X を穴あたりのハトの平均数とし、X が整数でない場合、少なくとも1つの鳩箱は許容される最大数のハトを含み、残りの鳩箱は最小数のハトを持つ可能性が高いです。(出典:Geeks For Geeks)
さらに説明すると、n 個の容器に n+1 個の物体を入れると、少なくとも1つの容器には2つ以上の物が入ります。鳩箱原理は結果が「失敗するには大きすぎる」ために有効であることを示すために使用されます。これは、任意の有意な数の対象に対して、境界または特定の属性数がある場合、少なくとも2つの対象が同じ属性を持つか共有することを意味します。この原理の応用は興味深く、驚きに満ち、考えさせられるものです。(出典:Stanford)
原理のいくつかの例
最初の例は、上記のように鳩箱原理を示しています:禿頭の人を除いたロンドンの人口は約750万人です。平均的な人の髪の毛の最大本数は約150,000本です。この原理により、約50人が同じ本数の髪の毛を持つことになります。(出典:Maths Careers)
次に、この記事を読んでいる2人以上の人が同じ誕生日を持つとしましょう。原理によれば、うるう年には366通りの誕生日が可能です。この文章の読者は367人以上です。したがって、読者のうち2人は同じ誕生日です。
別の例として、通常のトランプのデッキがあります。標準の52枚のトランプから5枚を選ぶと、その5枚のうち少なくとも2枚は同じスートになります。説明すると、通常のトランプには4つのスートがあります – クラブ、スペード、ハート、ダイヤモンド。5枚のカードはすべてこの4つのスートのいずれかに属します。したがって、2枚は同じスートになることが必然です。(出典: Mind Your Decisions)
この原理の実用的な応用はありますか?
鳩の巣原理は、データサイエンスで使用されるロスレス圧縮を証明するのに役立ちます。データ圧縮とは、実世界のデータから冗長性を単に除去することで圧縮できるという理論です。
これは、情報がネットワーク、DVD、USBメモリ、メールなどを介して転送されるかどうかにかかわらず、データ転送の形で今日の世界で使用されている重要な理論です。
ロスレス圧縮の考え方は、情報のビット列をより短いビット列に置き換えることです。ただし、短くしたビット列を復元すると、元のビット列の完全な情報が依然として明らかになります。(出典:Stanford)
鳩の巣原理は、ロスレス圧縮が可能であることを証明します。これは、データが高度に繰り返しである場合にのみ圧縮でき、2つの「鳩」(データの断片)が1つの「鳩の巣」またはビット列内の位置を占めることを意味します。(出典:Stanford)






