# 鳩の巣原理 ## 定義 鳩の巣原理(Pigeonhole Principle、規則14.8.1)は、「鳩の数が巣穴の数より多ければ、少なくとも2羽の鳩が同じ巣穴に入る」という直観を厳密化したもので、「|A| > |B| ならば、任意の全域関数 f: A → B について、fが同じ元に写す異なる2つのAの要素が存在する」と定式化される。一般化鳩の巣原理(規則14.8.2)はこれを「|A| > k・|B| ならば、少なくともk+1個の異なるAの要素を同じBの元に写す」という形に拡張する。応用のたびに (1) 鳩の集合A、(2) 巣穴の集合B、(3) 鳩を巣穴へ対応づける関数f、の3つを明確に特定することが鍵になるとされる。代表的な応用として、90個の25桁の数の部分集合(2^90通り)を取りうる部分和の値(高々90×10^25通り)へ写す写像に適用し、異なる2つの部分集合で和が一致するものが必ず存在することを示す例、ボストン市の非はげ頭の住人(約50万人)を髪の本数(1万〜20万本の範囲)へ写す写像に一般化鳩の巣原理を適用し、同じ本数の髪を持つ人が少なくとも3人存在することを示す例がある。いずれも存在を主張するのみで具体例を与えない**非構成的証明**である点が特徴的である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.8) ## 横断的知見 - 鳩の巣原理は、第4章のMapping Ruleの単射版(定理4.6: A inj B iff |A| ≤ |B|)の対偶にすぎないことが、第14章の本文で明示的に述べられている(「it is simply the contrapositive of the Mapping Rule's injective case (4.6)」)。第4章はこの対応を抽象的な濃度比較の枠組みの一部として提示するにとどまるが、第14章はこれを独立した「原理」として名付け直し、非構成的証明の道具として実践的に使いこなす方法論(鳩・巣穴・写像の3点セットを特定する手順)へ発展させている。同じ論理的事実(単射版Mapping Ruleの対偶)が、第4章では濃度比較の理論的な一部品として、第14章では実務的な証明技法として、異なる役割で再登場している。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.8) - カードマジックの種明かし(5枚の手札から4枚を見せて5枚目を当てる)は、鳩の巣原理と第11章のグラフマッチング理論という2つの独立した道具を組み合わせて完成する。トリックの実行可能性そのものは第11章の次数制約マッチング定理(定理11.5.6)による二部グラフの完全マッチングの存在保証に依拠する一方、実際に「アシスタントがどの2枚を同じスートとして選ぶか」という具体的な手順の構成には鳩の巣原理(5枚のカードと4つのスートから、同じスートの2枚が必ず存在する)が使われる。この例は、鳩の巣原理(非構成的な存在証明)とグラフマッチング理論(構成的なアルゴリズム設計)が補完し合う形で1つの応用に統合される様子を示している。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]], [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.8.4〜§14.8.5) ## 未解決の問い - 鳩の巣原理による証明は非構成的であり、どの2要素が同じ像を持つかを明示しない。第14章は「90個の25桁数」の例で、実際に一致する部分集合を発見するには格子基底簡約(lattice basis reduction)のような別のアルゴリズムが必要だったという逸話を紹介するにとどまる。非構成的証明から構成的アルゴリズムへ橋渡しする一般的な手法(計算論的な側面)は本章の範囲外であり、暗号理論やアルゴリズム論のソースが ingest されたら関連づけたい。 - 一般化鳩の巣原理は |A| > k・|B| という単純な不等式条件しか使わないが、AやBに追加の構造(例えば距離や順序)がある場合により強い結論(Ramsey理論など)が得られることが数学ではよく知られている。本章はこの方向へは踏み込んでいない。関連するソースが ingest されたら追記する。 ## 関連 - 概念: [[数え上げ]] / [[濃度]](Mapping Ruleの単射版との対偶関係) / [[包除原理]] / [[二項係数]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 14 §14.8.