1. 概要
鳩の巣原理（ディリクレ引き出し原理とも呼ばれる）は、後で見るように、いくつかの驚くべきことを示すために使用できる、数学における単純でありながら強力なアイデアです。 この記事では、最初に鳩の巣原理とは何かを定義し、次にそれをどのように適用できるかを示すいくつかの例を示します。
次に、原則の一般化されたバージョンについて説明し、一般化されたバージョンを使用するいくつかの例を示します。 最後に、鳩の巣原理を利用した特に巧妙なアプリケーションをいくつか紹介します。
2. 基本的な鳩の巣原理
このセクションでは、最初に基本的な鳩の巣原理を定義し、それを証明します。 次に、この基本原理を使用する3つの例を示します。
2.1. 定義と証明
原理の最も基本的な形式は、鳩と鳩の穴を指します。 ハトのセットがハトの穴のセットに飛んでいると仮定します。 次に、鳩の穴よりも鳩の数が多い場合は、複数の鳩が入っている鳩の穴が少なくとも1つ必要です。
以下に示すのは、12個の鳩の穴の3つのグループです。 各グループには13の鳩（円で表されます）があるため、各グループには少なくとも2つの鳩がいる少なくとも1つの鳩の穴があります。
もちろん、この原則をハトやハトの穴以外にも適用できます。 正式には、鳩の巣原理を次のように述べることができます。ボックスがあり、これらのボックスに複数のオブジェクトが配置されている場合、2つ以上のオブジェクトを含むボックスが少なくとも1つあります。
アイデアはかなり明白でほとんど些細なように見えますが、それでもそれが真実でなければならないことを証明する必要があります。 証明は比較的簡単で、次のようになります。
矛盾して、これらのボックスにボックスまたはそれ以上のオブジェクトが配置されているが、2つ以上のオブジェクトを含むボックスがないとします。 これは、すべてのボックスに最大で1つのオブジェクトが含まれていることを意味します。
ただし、すべてのボックスに最大で1つのオブジェクトが含まれている場合、ボックス全体にオブジェクトを超えることはできません。 しかし、少なくともオブジェクトがボックスに配置されていると想定したため、これは矛盾しています。
次に、鳩の巣原理をどのように適用できるかの例をいくつか示します。 それぞれの例で、どのオブジェクトがハトに対応し、どのオブジェクトがハトの穴に対応するかを明確に説明します。
2.2. 最初の例
27個の英語の単語のグループがあるとします。 次に、同じ文字で始まるグループ内に少なくとも2つの単語が必要です。 この場合、27の英語の単語は鳩であり、鳩の穴は英語のアルファベットの特定の文字で始まる単語を格納するバケットと考えることができます。
この場合、26個のピジョンホール（英語のアルファベットの各文字に1個）がありますが、27個のピジョンがあるため、複数の単語が含まれるバケットが少なくとも1つ必要であることがすぐにわかります。 ただし、複数の単語を含むバケットは、同じ文字で始まる単語が少なくとも2つあることを意味します。
2.3. 2番目の例
367人のグループには、同じ誕生日の人が少なくとも2人いる必要があります。 ここでは、人を鳩と見なすことができ、特定の誕生日を迎えるすべての人が鳩の穴となる部屋を考えることができます。 誕生日の可能性は366しかないため、366の部屋があります。
しかし、366の部屋に367人を配置すると、少なくとも2人がいる部屋が少なくとも1つ必要であることがわかります。 これは、同じ誕生日の人が少なくとも2人いる必要があることを意味します。
2.4. 3番目の例
人が頭につけることができる髪の毛の最大数を知っているとしましょう。 この数にしましょう。 次に、複数のグループの場合、頭に同じ数の髪の毛がある人が少なくとも2人いる必要があります。
人は鳩を表し、頭に特定の数の髪の毛がある部屋は鳩の穴を表します。 部屋よりも人が多いので、少なくとも2人がいる部屋が少なくとも1つ必要です。
現在、人の頭の平均毛髪数は約10万本です。つまり、最大数はおそらく数十万本になります。 これは、たとえば30万人のグループでは、頭に同じ数の髪の毛を持つ人が少なくとも2人いることが保証されていることを意味します。
3. 一般化された鳩の巣原理
ここでは、鳩の巣原理の一般化されたバージョンを定義して証明します。 次に、この一般化されたバージョンを使用する3つの例を示します。
3.1. 定義と証明
オブジェクトの数がボックスの数の倍数を超える場合、さらに多くのことが言えます。 たとえば、10進数の21桁のセットには、同じ3桁が必要です。 これは、21個のオブジェクトを10個のボックスに入れる場合、少なくとも3個のオブジェクトを含むボックスが少なくとも1個必要であるためです。
この概念を一般化された鳩の巣原理として正式に表現することができます。 一般化された鳩の巣原理は、オブジェクトがボックスに配置される場合、少なくとも1つのオブジェクトを含むボックスが少なくとも1つ必要であると述べています。ここで、このステートメントを証明します。
オブジェクトがボックスに配置されているが、すべてのボックスには多くてもオブジェクトが含まれているとします。 その場合、オブジェクトの総数は最大でですが、この値は。未満です。 これは、がわかっているためです。式の代わりに式を使用すると、値が大きくなるはずの式が得られます。
このように、全部で物があるので矛盾が生じます。
次に、一般化された鳩の巣原理を適用する方法の例をいくつか示します。 それぞれの例で、オブジェクトに対応するものとボックスに対応するものを明確に説明します。
3.2. 最初の例
100人のグループには、少なくとも同じ月に生まれた人がいます。 ここに配置するオブジェクトは人であり、ボックスは特定の月に生まれた人がいる部屋として想像できます。 100人と12の部屋（1年の各月に1つ）があるので、少なくとも9人の部屋が必要です。
3.3. 2番目の例
同じスートのカードが少なくとも3枚選ばれることを保証するには、52枚のカードの標準デッキから少なくとも9枚のカードを選択する必要があります。 この場合、ボックスは特定のスーツでマークされていると考えることができ、デッキからカードを選択するときに、選択したカードと同じスーツのボックスにそれらを配置します。 一般化された鳩の巣原理は、カードが選択された場合、少なくとも1つのカードを含むボックスが少なくとも1つあることを示しています。
したがって、同じスーツのカードが少なくとも3枚選択されている必要があることがわかっている場合。 この条件が真になるために取ることができる最小の値は9であるため、少なくとも9枚のカードを選択する必要があります。
3.4. 3番目の例
可能な成績が5つある場合、少なくとも6人の生徒が同じ成績を取得できるようにするためにクラスで必要な生徒の最小数は26人です（例： A、B、C、D、およびF）。 各オブジェクトは人として、各ボックスは特定のグレードの人がいる部屋として考えることができます。 条件を満たすために必要な学生の最小数は、のような最小の整数に等しく、そのような最小の整数は26です。
以下に示すのは、この3番目の例の2つのインスタンスです。 どちらの場合も、5つの可能な成績を表す5つのボックスと、いくつかの成績が割り当てられた26人の生徒を表す26の赤い円があります。 どちらの場合も、少なくとも6つの赤い円を含むボックスが少なくとも1つあります。これは、同じ成績の生徒が少なくとも6人いることを意味します。
4. 鳩の巣原理の巧妙な応用
このセクションでは、もう少し洗練された鳩の巣原理のいくつかの興味深いアプリケーションについて説明します。
4.1. 最初の例
各整数が最大でであるような整数の中には、他の整数の1つを分割する整数が存在する必要があります。 それぞれの整数は、奇数の整数の2倍の累乗として書くことができます。 したがって、を考えてみましょう。ここで、は非負の整数であり、奇数です。 整数はすべて、。未満の奇数の正の整数です。
鳩の巣原理から、。未満の奇数の正の整数しかないため、2つの整数は等しくなければならないということになります。 したがって、整数などが存在する必要があります。 との一般的な値とします。
次に、それと。 したがって、ifが、を除算し、ifが、を除算します。
4.2. 2番目の例
1日に少なくとも1つのゲームを30日間プレイするが、合計で45ゲームを超えないスポーツチームがあるとします。 次に、チームが正確に14ゲームをプレイしなければならない連続した数日間の期間が必要です。 このステートメントを証明します。
30日の期間の3日目またはそれ以前にプレイされたゲームの数とします。 次に、が付いた、明確な正の整数の増加するシーケンスです。 さらに、は、である別個の正の整数の増加するシーケンスでもあります。
60個の正の整数はすべて59以下です。 鳩の巣原理は、これらの整数の2つが等しいことを示しています。 整数はすべて別個であり、整数もすべて別個であるため、インデックスとが必要です。
しかし、これは正確に14のゲームが毎日プレイされたことを意味します。
5. 結論
この記事では、いくつかの定義と例を通して鳩の巣原理を探求しました。
最初に、鳩の巣原理の最も基本的な形式とその証明について説明しました。 次に、この基本原理を利用した例をいくつか示しました。
次に、鳩の巣原理の一般化されたバージョンを紹介し、それも証明しました。 また、この一般化されたバージョンを利用するいくつかの例を見ました。
最後に、鳩の巣原理のさらに興味深い応用を見ました。 これらの最後の例は、鳩の巣原理と組み合わせてもう少し洗練されたものを使用すると、かなり印象的な結果を証明できることを示しています。
