鳩小屋の原則

$穴の中のハト。ここでは、 m$ $= 9 個$ の穴に $n = 10$ 羽のハトがいます。10 は 9 より大きいので、鳩の巣原理によれば、少なくとも 1 つの穴には 2 羽以上のハトがいます。（左上の穴には 2 羽のハトがいます。）

数学では、鳩の巣原理は、 $n個の物を$ $m 個の$ 容器に入れ、 $n > m$ である場合、少なくとも 1 つの容器には 1 個以上の物が入っている必要があると述べています。 ^{[ 1 ]}例えば、3 個の手袋のうち、少なくとも 2 個は右利き用、または少なくとも 2 個は左利き用でなければなりません。なぜなら、物は 3 つありますが、それらを入れることができる利き手のカテゴリは 2 つしかないからです。この一見自明な主張は、一種の計数論証であり、予期せぬ結果を示すために使用できます。たとえば、ロンドンの人口が人間の頭に生えることができる最大毛髪数より 1 単位以上多い場合、この原理は、ロンドンには頭髪数が同じ人が少なくとも 2 人いる必要があることを要求します。

鳩の巣原理は、1622年にジャン・ルレションの著書に早くも登場しているが、^{[ 2 ]} 1834年にペーター・グスタフ・ルジューヌ・ディリクレが「引き出し原理」または「棚原理」という名称でこの原理を扱ったことから、一般にディリクレの箱原理またはディリクレの引き出し原理と呼ばれている。 ^[³^]

この原理にはいくつかの一般化があり、さまざまな方法で表現できます。より定量化されたバージョンでは、自然数 $k$ と $m$ に対して、 $n = km + 1個のオブジェクトが$ $m$ 個の集合に分配される場合、鳩の巣原理は、少なくとも 1 つの集合には少なくとも $k + 1$ 個のオブジェクトが含まれると主張します。^{[ 4 ]}任意の $n$ と $m$ に対して、これは次のように一般化されます。 $k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil$ 、どこ $\lfloor \cdots \rfloor$ そして $\lceil \cdots \rceil$ それぞれ床関数と天井関数を表す。

この原理の最も直接的な適用例は有限集合（鳩や箱など）ですが、一対一対応させることができない無限集合にも適用されます。そのためには、鳩の巣原理の正式な記述、「定義域よりも値域が小さい単射関数は存在しない」が必要です。シーゲルの補題のような高度な数学的証明は、このより一般的な概念に基づいています。

語源

ディリクレは、ドイツ語のSchubfachまたはフランス語のtiroirのいずれかを使用して、フランス語とフランス語の両方で著作を出版しました。これらの用語の厳密な本来の意味は、英語のdrawerに相当し、つまり、それを収納するキャビネットに出し入れできる、上部が開いた箱のことです。（ディリクレは、真珠を引き出しに分配することについて書いています。）これらの用語は、手紙や書類を保管するための机、キャビネット、または壁の小さな空きスペースという意味でpigeonholeに変化し、比喩的には、鳩を飼育する構造に由来しています。

仕切り棚のある家具は、郵便局の手紙やホテルのルームキーのように、物をさまざまなカテゴリに保管または分類するためによく使用されるため、pigeonholeという翻訳は、ディリクレの元の「引き出し」をより適切に表現している可能性があります。家具の特徴を指すpigeonholeという用語の理解は、特に英語を母語としないが科学界の共通語として話す人々の間では、鳩と穴を文字通りに含む、より絵画的な解釈に取って代わられつつあります。この「pigeonhole」を「鳩小屋」と解釈する示唆に富む（ただし誤解を招くものではない）解釈は、最近、「pigeonhole principle」のドイツ語の逆翻訳である「Taubenschlagprinzip」に再び登場しました。^{[ 5 ]}

ドイツ語の元の用語「Schubfachprinzip 」 ^[⁶^]とフランス語の「 Principe des tiroirs」^[⁷^]のほかに、アラビア語( 「مبدأ برج الحمام」 )、ブルガリア語(「принцип на чекмеджетата」 ) では他の直訳が今でも使用されている。")、中国語("抽屉原理")、デンマーク語(" Skuffeprincippet ")、オランダ語(" ladenprincipe ")、ハンガリー語(" skatulyaelv ")、イタリア語(" principio dei cassetti ")、日本語("引き出し論法")、ペルシア語(" اصل لانه کبوتری ")、ポーランド語(" zasada ") szufladkowa ")、ポルトガル語(" Princípio das Gavetas ")、スウェーデン語(「Lådprincipen」)、トルコ語(「çekmece ilkesi」)、ベトナム語(「nguyên lý hộp」)。

歴史

おそらく、鳩の巣原理への最初の記述は、フランスのイエズス会士ジャン・ルレションの1622年の著作『Selectæ Propositiones 』の短い一文に現れる。^{[ 2 ]} 「2人の男性は互いに同じ数の毛髪、エキュ、またはその他のものを持つ必要がある。」 ^{[ 8 ]}この原理の完全な説明は、2年後に別の本で追加の例とともに明らかにされた。この本はしばしばルレションの著作とされているが、ジャン・アピエ・アンズレの著作である可能性もある。^{[ 2 ]}

例

靴下選び

引き出しの中に、黒と青の靴下が混ざっていて、どちらの足にも履けるとします。引き出しから靴下を何足か、見ずに取り出します。同じ色の靴下が必ず一組になるようにするには、最低何足取り出す必要がありますか？鳩の巣原理（ $m = 2$ 、色ごとに1つの鳩の巣を使う）によれば、答えは3足（ $n = 3$ 個）です。同じ色の靴下が3足あるか、同じ色の靴下が2足と、もう一方の色の靴下が1足あるかのどちらかです。

握手

$n$ 人が互いに握手できる場合( $n > 1$ )、鳩の巣原理によれば、必ず同じ人数と握手するペアが存在する。この原理の適用では、人が割り当てられる「穴」は、その人が握手する人数である。各人は 0 から $n - 1 までの人数と握手するので、可能な穴は$ $n$ 個ある。一方、「0」の穴、 $「 n - 1」の穴、またはその両方が空でなければならない。なぜなら ($ $n > 1$ の場合)、ある人が他の全員と握手し、ある人が誰とも握手しないということは不可能だからである。これにより、 $n人を最大で$ $n - 1 個$ の空でない穴に配置することになるので、原理が適用される。

この握手の例は、頂点が複数あるグラフには、少なくとも1組の頂点が同じ次数を持つという記述と同等です。^[⁹^]これは、各人物を頂点に、各辺を握手に関連付けることで確認できます。

毛髪数え

ロンドンには少なくとも 2 人の頭髪が同じ数ある人が必ずいることは、次のように証明できます。^{[ 10 ]}^{[ 11 ]}一般的な人間の頭髪の平均数は約 15 万本なので、(上限として) 頭髪が 1,000,000 本を超える人はいないと仮定するのが妥当です $(m = 100 万の$ 穴)。ロンドンには 1,000,000 人以上の人がいます ( $n$ は 100 万個より大きい )。頭髪の数ごとに鳩小屋を割り当て、頭髪の数に応じて人を鳩小屋に割り当てると、1,000,001 回目の割り当てまでに少なくとも 2 人の人が同じ鳩小屋に割り当てられることになります (頭髪の数が同じであるため、つまり $n > m$ )。ロンドンの人口を900万2千人と仮定すると、^{[ 12 ]}少なくとも10人のロンドン市民が同じ数の毛髪を持っていることになる。なぜなら、100万個の仕切り棚それぞれに9人のロンドン市民がいるとすると、900万人しかいないからである。

制約条件「重複が最小」を満たす平均的なケース（ $m = 150,000$ ）では、各区分けに最大で1人しか割り当てられず、150,001人目は他の誰かと同じ区分けにされることになります。この制約条件がない場合、「衝突」が150,001人目より前に発生するため、区分けが空になることがあります。この原理は重複の存在を証明するだけであり、重複の数（これは確率分布の範疇です）については何も述べていません。

この原則のバージョンについては、英語で風刺的な言及が「アテネ協会の歴史」にさりげなくある。「アテネ神託への補遺：旧アテネ水銀紙の残りの質問と回答のコレクション」（アンドリュー・ベル、ロンドン、1710年刊）の序文となっている。^{[ 13 ]}世界に頭髪の本数が同じ2人いるかどうかという疑問は、 1704年以前にアテネ水銀紙で提起されていたようだ。 ^{[ 14 ]}^{[ 15 ]}

誕生日問題

$誕生日問題とは、無作為に選ばれたn$ 人の人のうち、2人が同じ誕生日である確率はどれくらいか、という問題です。この問題自体は主に直感に反する確率に関するものですが、367人の中から少なくとも1組は同じ誕生日である確率が100%であるということは、鳩の巣原理によってもわかります。なぜなら、選択できる誕生日は366通りしかないからです。

チームトーナメント

7人のプレイヤーがチーム対抗トーナメント $（ n = 7$ アイテム）に参加したいと考えているが、選択できるチームは4チーム $（ m = 4$ ホール）しかないと想像してください。鳩の巣原理によれば、7人全員が異なるチームでプレイすることはできません。少なくとも1つのチームには、7人のうち少なくとも2人が所属していなければなりません。

\left\lfloor {\frac {n-1}{m}}\right\rfloor +1=\left\lfloor {\frac {7-1}{4}}\right\rfloor +1=\left\lfloor {\frac {6}{4}}\right\rfloor +1=1+1=2

部分集合の合計

セットからサイズが 6 の任意の部分集合 $S=\{1,2,3,\dots ,9\}$ 合計が10になる2つの要素を含まなければならない。鳩の巣は、その2つの要素のサブセットによってラベル付けされる。 $\{1,9\}、\{2,8\}、\{3,7\}、\{4,6\}$ そしてシングル $\{5\}$ 全部で5つの仕切りがあります。6つの「鳩」（サイズ6の部分集合の要素）をこれらの仕切りに入れると、各鳩はラベルにその鳩が含まれている仕切りに入ります。2つの要素の部分集合でラベル付けされた仕切りのうち、少なくとも1つには2つの鳩が入ります。^{[ 16 ]}

ハッシュ化

コンピュータサイエンスにおけるハッシュとは、 $n個の任意の大きさのデータセットを$ $m個の$ 固定サイズの値にマッピングするプロセスです。これは、大規模なデータセットをキャッシュする用途に使用されます。s は、高速に呼び出せるように、代表値 (「ハッシュ」) への参照によって「ハッシュテーブル」に格納できます。通常、データセット $n$ 内の一意のオブジェクトの数は、使用可能な一意のハッシュコードの数 $m$ より多く、この場合、鳩の巣原理が成り立ち、これらのオブジェクトをハッシュ化しても一意性が保証されません。データセット $n$ 内のすべてのオブジェクトをハッシュ化すると、一部のオブジェクトは必ず同じハッシュコードを共有することになるからです。

用途と応用例

この原理は、可逆圧縮アルゴリズムが（「圧縮」という言葉が示唆するように）一部の入力を小さくする限り、他の入力を大きくすることも証明するために使用できる。そうでなければ、与えられた長さまでのすべての入力シーケンスの集合は $L$ は、長さが 1 未満のすべてのシーケンスの (はるかに) 小さなセットにマッピングできます。 $L$ 衝突がない（圧縮がロスレスであるため）、これは鳩の巣原理が排除する可能性である。

数学解析における注目すべき問題は、固定された無理数に対して $a$ 集合を示すために $\{[na]:n\in \mathbb {Z} \}$ ⁠の小数部分は密です $[0,1]$ 整数を明示的に見つけるのは容易ではないことがわかる。 $n$ 、 $m$ そのため $|na-m|<\varepsilon ,$ どこ $\varepsilon >0$ は小さな正の数で、 $a$ はある任意の無理数です。しかし、もし $M$ そのため $1/M<\varepsilon$ 鳩の巣原理によれば、 $n_{1},n_{2}\in \{1,2,\ldots ,M+1\}$ そのため $n_{1}a$ そして $n_{2}a$ 同じ整数サイズの細分に属します $1/M$ （ $M$ 連続する整数間のこのような分割）。特に、 $n_{1}$ 、 $n_{2}$ そのため

n_{1}a\in \left(p+{\frac {k}{M}},\ p+{\frac {k+1}{M}}\right),\quad n_{2}a\in \left(q+{\frac {k}{M}},\ q+{\frac {k+1}{M}}\right),

いくつかの整数に対して $p$ 、 $q$ そして $k\in \{0,1,\cdots ,M-1\}$ そうすれば簡単に確認できる。

(n_{2}-n_{1})a\in \left(q-p-{\frac {1}{M}},q-p+{\frac {1}{M}}\right).

これは、 $[na]<1/M<\varepsilon$ 、どこ $n=n_{2}-n_{1}$ または $n=n_{1}-n_{2}$ これは、0 が極限点であることを示しています。 $\{[na]\}$ そうすれば、この事実を利用して、 $p$ で $(0,1]$ ：探す $n$ そのため $[na]<1/M<\varepsilon$ ; ならば $p\in (0,1/M]$ 証明は完了です。そうでなければ

p\in \left({\frac {j}{M}},{\frac {j+1}{M}}\right],

そして設定することで

k=\sup \left\{r\in N:r[na]<{\frac {j}{M}}\right\},

得られるもの

{\Bigl |}{\bigl [}(k+1)na{\bigr ]}-p{\Bigr |}<{\frac {1}{M}}<\varepsilon .

様々な証明で変種が見られる。正規言語のポンピング補題の証明では、有限集合と無限集合を混ぜたバージョンが使われている。「無限個の物体を有限個の箱に入れると、2つの物体が1つの箱を共有する。」^{[ 18 ]}フィスクの美術館問題の解では、一種の逆が使われている。「もし $n$ オブジェクトは $k$ 箱、次に最大で $n/k$ オブジェクト。^{[ 19 ]}

代替製剤

以下は、鳩の巣原理の別の表現である。

$n個の物体が$ $m個の$ 場所に分散され、 $n > m$ の場合、少なくとも2つの物体がどこかの場所に置かれる。^{[ 1 ]}
（1の同等の表現） $n個の物体が$ $n個の$ 場所に分配され、どの場所にも1個以上の物体が分配されない場合、各場所にはちょうど1個の物体が分配される。^{[ 1 ]}
（1の一般化） $S$ と $T$ が集合であり、 $S$ の濃度が $T$ の濃度より大きい場合、 $S$ から $T$ への単射関数は存在しない。
$n個の物体が$ $m個の$ 場所に分配され、 $n < m$ の場合、いずれかの場所には物体が分配されない。
（4の同等の定式化） $n個の物体が$ $n個の$ 場所に分配され、どの場所にも物体が全く分配されない場合、各場所にはちょうど1つの物体が分配される。^{[ 20 ]}
（4の一般化） $S$ と $Tが集合であり、$ $S$ の濃度が $T$ の濃度より小さい場合、 $S$ から $T$ への全射関数は存在しない。

強い形式

$q 1 、 q 2 、...、 q n$ を正の整数とする。

q_{1}+q_{2}+\cdots +q_{n}-n+1

$オブジェクトがn 個の$ 箱に分配されると、最初の箱には少なくとも $q 1 個の$ オブジェクトが含まれるか、2 番目の箱には少なくとも $q 2 個の$ オブジェクトが含まれるか、...、または $n$ 番目の箱には少なくとも $q n 個の$ オブジェクトが含まれる。^{[ 21 ]}

$単純な形式は、 q 1 = q 2 = ... = q n = 2$ とすることで得られ、 $n + 1 個$ のオブジェクトが得られます。q 1 = q 2 = ... = q n = r とすると $、原理のより定量化された$ バージョンが得られます。すなわち、次のようになります $。$

$n$ と $r$ $を$ 正の整数とする。n ( $r - 1)+1個の物体を$ $n$ 個の箱に分配すると、少なくとも1つの箱には $r$ 個以上の物体が含まれる。^{[ 22 ]}

$これは、 k 個の離散オブジェクトを$ $n 個の$ コンテナに割り当てる場合、少なくとも 1 つのコンテナには少なくとも k 個のオブジェクトを収容する必要がある、とも表現できます。 $\lceil k/n\rceil$ オブジェクト、 $\lceil x\rceil$ は天井関数であり、 $x$ 以上の最小の整数を表します。同様に、少なくとも 1 つのコンテナには、以下しか収容できません。 $\lfloor k/n\rfloor$ オブジェクト、 $\lfloor x\rfloor$ は床関数であり、 $x$ 以下の最大の整数を表します。

鳩の巣原理の一般化

鳩の巣原理の確率的一般化によれば、 $n羽の鳩を$ $m個の$ 鳩の巣に一様確率 $1/ m$ でランダムに入れると、少なくとも1つの巣には1羽以上の鳩が入る確率は

1-{\frac {(m)_{n}}{m^{n}}},

ここで $、(m) n$ $は、 m$ $($ $m$ $-$ $1)($ $m$ $-$ $2)...($ $m$ $-$ $n$ $+ 1)$ の階乗です。 $n$ $= 0$ および $n$ $= 1$ (かつ $m$ $> 0$ ) の場合、その確率はゼロです。つまり、ハトが 1 羽しかいない場合は、衝突は起こりません。 $n$ $>$ $m$ (ハトの数よりハトの数が多い) の場合、確率は 1 となり、通常のハトの巣箱の原理と一致します。しかし、ハトの数が巣箱の数を超えない場合 ( $n$ $\leq$ $m$ ) でも、ハトを巣箱に割り当てるのはランダムな性質のため、衝突が発生する可能性がかなり高くなります。たとえば、2 羽のハトが 4 つの巣箱にランダムに割り当てられると、少なくとも 1 つの巣箱に 1 羽以上のハトが入る確率は 25% です。5 羽のハトと 10 個の巣箱の場合、その確率は 69.76% です。 10羽の鳩と20個の穴の場合、その確率は約93.45%です。穴の数が一定の場合、鳩の数を増やすほどペアになる確率は常に高くなります。この問題については、誕生日のパラドックスでより詳しく解説されています。

さらに確率論的に一般化すると、実数値の確率変数 $X が$ 有限の平均 $E (X)$ を持つ場合、 $Xが$ $E (X)$ 以上である確率はゼロではなく、同様に $Xが$ $E (X)$ 以下である確率もゼロではない。これが標準的な鳩の巣原理を意味することを示すために、 $n羽の鳩を$ $m 個の$ 穴に固定配置し、 $X を一様にランダムに選択された穴の鳩の数とする$ $。X$ の平均は $n / m$ なので、鳩の数が穴の数より多い場合、平均は 1 より大きくなる。したがって、 $X$ は少なくとも 2 になることがある。

無限集合

鳩の巣原理は、基数を用いて表現することで無限集合にも拡張できる。すなわち、集合 $A$ の濃度が集合 $B$ の濃度より大きい場合、 $Aから$ $B$ への単射は存在しない。しかし、この形式では原理はトートロジーとなる。なぜなら、集合 $Aの濃度が集合$ $B$ の濃度より大きいという命題の意味は、 $Aから$ $B$ への単射写像が存在しないということと全く同じだからである。一方、有限集合に少なくとも1つの要素を追加すれば、濃度が増加することは保証される。

$有限集合に対する鳩の巣原理を別の言い方で表現すると、有限集合は$ デデキント有限であるという原理に似ています。A と B を有限集合とします $。A$ $から$ B $へ$ の全射で単射でないものがあるならば、 $Aから$ $B$ への全射は単射ではありません。実際、 $Aから$ $B$ へのいかなる種類の関数も単射ではありません。これは無限集合には当てはまりません。自然数上の関数で、1 と 2 を 1 に、3 と 4 を 2 に、5 と 6 を 3 に、といったように送る関数を考えてみましょう。

無限集合についても同様の原理が成り立つ。可算個の鳩小屋に非可算個の鳩を詰め込んだ場合、非可算個の鳩が詰め込まれた鳩小屋が少なくとも1つ存在する。

しかし、この原理は有限集合に対する鳩の巣原理の一般化ではありません。一般に、有限集合に対しては偽です。専門的に言えば、 $A$ と $Bが有限集合であり、$ $Aから$ $B$ への全射関数が単射でない場合、 $B$ の要素 $bが存在し、$ $b$ の逆像と $A$ の間に全単射が存在するということです。これは全く異なる主張であり、有限集合の濃度が大きい場合には不合理です。

量子力学

ヤキール・アハロノフらは、量子力学が鳩の巣原理に違反する可能性があるという議論を提示し、量子力学における鳩の巣原理を検証するための干渉実験を提案した。 ^{[ 23 ]}

その後の研究でこの結論に疑問が呈されている。^{[ 24 ]}^{[ 25 ]} 2015年1月のarXivプレプリントで、バーミンガム大学の研究者アラステア・レイとテッド・フォーガンは、標準的な鳩の巣原理を用いて、さまざまなエネルギーの電子が干渉計を通過する際の理論的な波動関数解析を行った。電子の相互作用がまったくない場合、それぞれが単一の完全な円形のピークを生成する。相互作用が強い場合、各電子は4つの異なるピークを生成し、検出器上に合計12個のピークが現れる。これらのピークは、各電子が経験する可能性のある4つの相互作用（単独、最初の他の粒子とのみ、2番目の他の粒子とのみ、または3つすべてと）の結果である。実際の多くの実験の場合のように、相互作用がかなり低い場合、ゼロ相互作用パターンからのずれはほとんど識別できず、これらのパターンを観測するために使用される検出器などの固体中の原子の格子間隔よりもはるかに小さい。これにより、弱いがゼロではない相互作用の強さと、全く相互作用がない場合を区別することが非常に困難、あるいは不可能になり、結果として、3つの電子が2つの経路を通過したにもかかわらず、相互作用しなかったかのような錯覚が生じることになる。

注記

1 2 3ハースタイン 1964 、p.90
1 2 3 Rittaud, Benoît; Heeffer, Albrecht (2014). "The pigeonhole principle, two centuries before Dirichlet" . The Mathematical Intelligencer . 36 (2): 27–29 . doi : 10.1007/s00283-013-9389-1 . hdl : 1854/LU-4115264 . MR 3207654 . S2CID 44193229 .
↑ジェフ・ミラー、ピーター・フロー、グンナー・ベルク、フリオ・ゴンサレス・カビヨン。「鳩の巣原理」。ジェフ・ミラー編『数学用語の最古の使用例』所収。電子文書、2006年11月11日取得。
↑フレッチャー＆パティ 1987 、p.27
↑ツィンマーマン、カール・ハインツ (2006)。離散数学。オンデマンドの書籍。 p. 367.ISBN 9783833455292。
↑ウェイントラウブ、スティーブン・H.（2017年5月17日）。『インダクション・ブック』。クーリエ・ドーバー出版。13ページ。ISBN 9780486811994。
↑ James, RC (1992年7月31日).数学辞典. Springer. p. 490. ISBN 9780412990410。
↑ Leurechon、Jean (1622)、Tota Sparsim Mathematica Pulcherrimæ の Selecæe Propositiones、Gasparem Bernardum、p. 2
↑ Pandey, Avinash. "D3 Graph Theory - Interactive Graph Theory Tutorials" . d3gt.com . 2021-01-12に取得.
↑リニャーノ、エウジェニオ（1923）。『推論の心理学』。ウィニフレッド・AK・ポール・ホール訳、トレンチ・トルブナー社、リミテッド、72ページ。ISBN 9780415191326。{{cite book}}ISBN /日付の不一致（ヘルプ）
↑表示がやや複雑になるのを避けるため、この例ではハゲていない人だけを対象としています。
↑ 「ロンドンの人口 / グレーター・ロンドン・オーソリティ (GLA)」 . data.london.gov.uk .
↑ 「アテネ神託の補遺：旧アテネ水星誌に掲載された残りの質問と回答のコレクション。…アテネ協会の歴史を序文として付記。…アテネ協会会員による」。1710年。
↑ 「アテネの神託は、あらゆる貴重な質問と回答の完全なコレクションである」。1704年。
↑ 「アテネの神託：古代アテネのメルクリウスに掲載されたすべての貴重な質問と回答の完全なコレクション。…アテネ協会の会員による」 1704年。
↑グリマルディ 1994 、p. 277
↑ガードナー、マーティン（1976 年 10 月）。「組み合わせ問題、古いものも新しいものもあり、すべてコンピュータによって新たに解かれる」。数学ゲーム。サイエンティフィックアメリカン。第235 巻、第4 号、 131～ 137ページ。JSTOR 24950467。
↑『形式言語とオートマタ入門』、ピーター・リンツ著、115～116ページ、ジョーンズ・アンド・バートレット・ラーニング、2006年
↑ O'Rourke, Joseph (1998). Computational Geometry in C. Cambridge Tracts in Theoretical Computer Science (第2版). p. 9. ISBN 0-521-64976-5。
↑ブルアルディ2010、70ページ
↑ブルアルディ 2010 、p. 74 定理 3.2.1
↑冒頭部分では、 $m = n$ および $k = r - 1$ という置換を用いて提示されました。
↑ Aharonov, Yakir; Colombo, Fabrizio; Popescu, Sandu; Sabadini, Irene ; Struppa, Daniele C.; Tollaksen, Jeff (2016). "Quantum violation of the pigeonhole principle and the nature of quantum correlations" . Proceedings of the National Academy of Sciences . 113 (3): 532– 535. Bibcode : 2016PNAS..113..532A . doi : 10.1073/pnas.1522411112 . PMC 4725468. PMID 26729862 .
↑ 「量子鳩の巣は結局パラドックスではない、と物理学者たちは言う」 2015年1月8日。
↑ Rae, Alastair; Forgan, Ted (2014-12-03). "量子鳩の巣効果の含意について". arXiv : 1412.1333 [ quant-ph ].

参考文献

ブルアルディ、リチャード A. (2010)、『入門組合せ論』（第 5 版）、ペンティスホール、ISBN 978-0-13-602040-0
フレッチャー、ピーター、パティ、C.ウェイン (1987)、『高等数学の基礎』、PWS-ケント、ISBN 978-0-87150-164-6
グリマルディ、ラルフ・P. (1994)、『離散数学と組合せ数学：応用入門』（第3 版）、アディソン・ウェスリー、ISBN 978-0-201-54983-6
Herstein, IN (1964)、『Topics In Algebra』、ウォルサム：Blaisdell Publishing Company、ISBN 978-1114541016{{citation}}ISBN /日付の不一致（ヘルプ）

外部リンク

「ディリクレの箱の原理」、数学百科事典、EMS Press、2001年 [1994年]
「鳩の巣原理の奇妙な事例」：エドガー・ダイクストラは、この原理の解釈と再定式化について考察する。
「鳩の巣原理」；ラリー・キューシックによる、この原理を用いた基本的な例。
「インタラクティブ数学雑録とパズルからの鳩の巣原理」; Alexander Bogomolnyによる鳩の巣原理の基本的な分析と例。
「鳩の巣原理の16の楽しい応用例」；この原理から導き出される興味深い事実。
「体毛の本数が同じ人間は何人いるのか？」 PBS Infiniteシリーズ2016年12月1日オリジナルから2021年12月11日にアーカイブ- YouTube経由

[Herstein64-1] 1 2 3ハースタイン 1964 、p.90

[leurechon-2] 1 2 3 Rittaud, Benoît; Heeffer, Albrecht (2014). "The pigeonhole principle, two centuries before Dirichlet" . The Mathematical Intelligencer . 36 (2): 27–29 . doi : 10.1007/s00283-013-9389-1 . hdl : 1854/LU-4115264 . MR 3207654 . S2CID 44193229 .

[3] ジェフ・ミラー、ピーター・フロー、グンナー・ベルク、フリオ・ゴンサレス・カビヨン。「鳩の巣原理」。ジェフ・ミラー編『数学用語の最古の使用例』所収。電子文書、2006年11月11日取得。

[4] フレッチャー＆パティ 1987 、p.27

[5] ツィンマーマン、カール・ハインツ (2006)。離散数学。オンデマンドの書籍。 p. 367.ISBN 9783833455292。

[6] ウェイントラウブ、スティーブン・H.（2017年5月17日）。『インダクション・ブック』。クーリエ・ドーバー出版。13ページ。ISBN 9780486811994。

[7] James, RC (1992年7月31日).数学辞典. Springer. p. 490. ISBN 9780412990410。

[8] Leurechon、Jean (1622)、Tota Sparsim Mathematica Pulcherrimæ の Selecæe Propositiones、Gasparem Bernardum、p. 2

[9] Pandey, Avinash. "D3 Graph Theory - Interactive Graph Theory Tutorials" . d3gt.com . 2021-01-12に取得.

[10] リニャーノ、エウジェニオ（1923）。『推論の心理学』。ウィニフレッド・AK・ポール・ホール訳、トレンチ・トルブナー社、リミテッド、72ページ。ISBN 9780415191326。{{cite book}}ISBN /日付の不一致（ヘルプ）

[11] 表示がやや複雑になるのを避けるため、この例ではハゲていない人だけを対象としています。

[12] 「ロンドンの人口 / グレーター・ロンドン・オーソリティ (GLA)」 . data.london.gov.uk .

[13] 「アテネ神託の補遺：旧アテネ水星誌に掲載された残りの質問と回答のコレクション。…アテネ協会の歴史を序文として付記。…アテネ協会会員による」。1710年。

[14] 「アテネの神託は、あらゆる貴重な質問と回答の完全なコレクションである」。1704年。

[15] 「アテネの神託：古代アテネのメルクリウスに掲載されたすべての貴重な質問と回答の完全なコレクション。…アテネ協会の会員による」 1704年。

[16] グリマルディ 1994 、p. 277

[17] ガードナー、マーティン（1976 年 10 月）。「組み合わせ問題、古いものも新しいものもあり、すべてコンピュータによって新たに解かれる」。数学ゲーム。サイエンティフィックアメリカン。第235 巻、第4 号、 131～ 137ページ。JSTOR 24950467。

[18] 『形式言語とオートマタ入門』、ピーター・リンツ著、115～116ページ、ジョーンズ・アンド・バートレット・ラーニング、2006年

[19] O'Rourke, Joseph (1998). Computational Geometry in C. Cambridge Tracts in Theoretical Computer Science (第2版). p. 9. ISBN 0-521-64976-5。

[20] ブルアルディ2010、70ページ

[21] ブルアルディ 2010 、p. 74 定理 3.2.1

[22] 冒頭部分では、 $m = n$ および $k = r - 1$ という置換を用いて提示されました。

[23] Aharonov, Yakir; Colombo, Fabrizio; Popescu, Sandu; Sabadini, Irene ; Struppa, Daniele C.; Tollaksen, Jeff (2016). "Quantum violation of the pigeonhole principle and the nature of quantum correlations" . Proceedings of the National Academy of Sciences . 113 (3): 532– 535. Bibcode : 2016PNAS..113..532A . doi : 10.1073/pnas.1522411112 . PMC 4725468. PMID 26729862 .

[24] 「量子鳩の巣は結局パラドックスではない、と物理学者たちは言う」 2015年1月8日。

[Rae_Forgan_2014-25] Rae, Alastair; Forgan, Ted (2014-12-03). "量子鳩の巣効果の含意について". arXiv : 1412.1333 [ quant-ph ].

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[

[

[ 8 ]

[

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]