組合せ論と離散数学

鳩の巣原理

箱の数より多くの物を入れると、少なくとも1つの箱に2つ以上の物が入るという原理。

直観なぜ2羽の鳩が同じ巣に入らなければならないのか

$10$ 羽の鳩がいて、鳩の巣が $9$ 個しかなく、すべての鳩がどこかの巣に入らなければならないとしよう。どんなに工夫して鳩を配置しても、少なくとも1つの巣には2羽以上の鳩が入ることになる — 単純に、すべての鳩が自分専用の巣を持つには巣の数が足りないのである。この当たり前に聞こえる事実は鳩の巣原理と呼ばれ、単純であるにもかかわらず、数論、幾何学、計算機科学にわたって驚くほど深い結果を証明する。

10

羽の鳩と

9

個の巣をつなぐ二部ネットワーク:辺をどのように引いても、

10 > 9

であるから、少なくとも1つの巣の頂点は2本以上の辺を受け取ることになる。

中高原理を正確に述べる

定義: 鳩の巣原理

$n$ 個の物を $k$ 個の箱に入れ、 $n > k$ であるとき、少なくとも1つの箱には少なくとも $2$ 個の物が入る。より一般に、 $n$ 個の物を $k$ 個の箱に入れるとき、少なくとも1つの箱には少なくとも $\lceil n/k\rceil$ 個の物が入る。

n>k\ \Longrightarrow\ \exists\text{ box with}\ge2\text{ objects}

$\lceil n/k\rceil$ (「 $n/k$ を切り上げたもの」)は $n/k$ 以上の最小の整数であり、 $n$ 個の物を $k$ 個の箱にできるだけ均等に分けたときの、最も多く入った箱に保証される最小の個数である。例えば $n=10$ 個の物を $k=3$ 個の箱にできるだけ均等に分けると $4,3,3$ となり、実際 $\lceil 10/3\rceil=4$ である。

\left\lceil\frac{n}{k}\right\rceil=\left\lfloor\frac{n-1}{k}\right\rfloor+1

物の数、箱の数、何が保証されるか
物の数 $n$ / 箱の数 $k$	最も満杯な箱に保証される最小数
$n=10,\ k=9$	$\lceil 10/9\rceil=2$
$n=13,\ k=12$	$\lceil 13/12\rceil=2$
$n=100,\ k=9$	$\lceil 100/9\rceil=12$
$n=k+1,\ k$ は任意	$\lceil (k+1)/k\rceil=2$

大学2つの定理:基本原理と一般化された原理

定理: 基本鳩の巣原理

$n$ 個の物を $k$ 個の箱に分配し、 $n>k$ であるとき、少なくとも1つの箱には少なくとも $2$ 個の物が入る。

なぜ正しいのか?

これは実際には数え上げに関する主張であり、逆を仮定して矛盾を導くことで証明される:もしすべての箱が高々 $1$ 個しか物を持たないなら、箱全体で保持できる物の総数は $k$ を超えられない。

証明

背理法のため、結論が成り立たないと仮定する: $k$ 個の箱のそれぞれが高々 $1$ 個の物しか含まないとする。

このとき分配された物の総数は高々 $k\times1=k$ である。

しかし実際には $n$ 個の物を分配しており、仮定より $n>k$ であるから、分配された物の総数は $n>k$ である。

同じ物の集合に対するこの2つの数え方は矛盾する( $n>k$ であると同時に総数 $\le k$ でもある)。したがって仮定は誤りであり、少なくとも1つの箱には少なくとも $2$ 個の物が入らなければならない。

定理: 一般化された鳩の巣原理

$n$ 個の物を $k$ 個の箱に分配すると、少なくとも1つの箱には少なくとも $\lceil n/k\rceil$ 個の物が入る。

なぜ正しいのか?

基本原理はどこかに $2$ 個の物があることしか保証しないが、一般化された版はこれを、 $n$ 個の物を $k$ 個の箱で平均したときに強制される正確な最小値へと精密化する。同じ背理法の考え方を使うが、 $1$ の代わりに $\lceil n/k\rceil-1$ と比較する。

証明

背理法のため、すべての箱が高々 $\lceil n/k\rceil-1$ 個の物しか含まないと仮定する。

このとき分配された物の総数は高々 $k\left(\lceil n/k\rceil-1\right)$ である。

$\lceil n/k\rceil$ は $n/k$ 以上の最小の整数であるから、 $\lceil n/k\rceil-1<n/k$ であり、したがって $k\left(\lceil n/k\rceil-1\right)<k\cdot\frac{n}{k}=n$ となる。

よって分配された総数は $n$ より真に小さく、 $n$ 個すべての物が分配されたことと矛盾する。したがって少なくとも1つの箱には少なくとも $\lceil n/k\rceil$ 個の物が入る。

大学実世界での応用と具体例

単純であるにもかかわらず、鳩の巣原理は計算機科学(スロット数よりキー数が多いハッシュテーブルには必ず衝突が起きることの証明)、数論(与えられた整数のある倍数が特定の桁パターンを持つことの証明)、そしてスケジューリングや整列、ソーシャルネットワークに関する日常的な組合せパズルにおいて標準的な道具である。

例: 引き出しの中の靴下

引き出しに $4$ 色の靴下がたくさん入っており、暗闇の中で混ざっている。同じ色のペアを確実に手に入れるには、最低何足の靴下を取り出す必要があるか。

解答

$4$ 色を $k=4$ 個の箱と考え、取り出す各靴下をその色に対応する箱に入れる物と考える。「同色のペア」とは、ある箱が少なくとも $2$ 個の物を受け取ることを意味する。

基本鳩の巣原理により、 $n$ 枚の靴下を $n>k=4$ 、すなわち $n\ge5$ 枚取り出せば、あるいずれかの色の箱は少なくとも $2$ 枚の靴下を含むことになる — 同色のペアが保証される。

$5$ が実際に最小の数だろうか。わずか $4$ 枚の靴下では、(運が悪ければ) $4$ 色それぞれちょうど1枚ずつを取り出し、まだペアがない場合があり得る。したがって $4$ 枚ではペアは保証されないが、 $5$ 枚なら保証される。

答えは $5$ 枚の靴下である。

例: パーティーで友人の数が同じ2人

$n\ge2$ 人が参加するパーティーで、「友人関係」は相互的であり、誰も自分自身の友人ではないとする。パーティーには、出席している友人の人数がちょうど同じである2人が必ず存在することを示せ。

解答

パーティーでの各人の友人数は $0$ から $n-1$ までの整数である(出席している他の $n-1$ 人より多くの友人を持つことはできない)ので、可能な値は $n$ 個、人数も $n$ 人となる — 友人数にそのまま鳩の巣原理を適用しても、 $n$ 人に対して $n$ 個の箱があるだけで、まだ衝突は強制されない。

鍵となる追加の観察は、値 $0$ と $n-1$ が同時には起こり得ないということである:誰かの友人数が $0$ ならば、誰も $n-1$ 人の友人を持つことはできない(それは全員と友人であることになり、その人自身も含まれてしまう)。逆も同様である。したがって実際に可能な友人数の値は $n-1$ 個しかなく、 $\{0,1,\dots,n-2\}$ か $\{1,2,\dots,n-1\}$ のいずれかである。

ここで、 $n$ 人(物)と高々 $n-1$ 個の可能な友人数(箱)に基本鳩の巣原理を適用する。 $n>n-1$ であるから、ある友人数の箱は少なくとも $2$ 人を受け取ることになる。

したがって、パーティーには出席している友人の人数がちょうど同じである2人が少なくとも存在する。

$13$ 羽の鳩が $12$ 個の巣に入るとき、基本鳩の巣原理は何を保証するか。

一般化された鳩の巣原理を使うと、 $n=100$ 個の物を $k=9$ 個の箱に入れたとき、最も満杯な箱に保証される最小の個数はいくつか。

次のうち、鳩の巣原理を直接応用している日常的な状況はどれか。

友人関係が相互的なパーティーの例で、 $n$ 人のゲストの中で友人数 $0$ と $n-1$ が同時に起こり得ないのはなぜか。