鳩の巣原理

鳩の巣原理：N個のものをk個の箱に入れるとき、N > k であれば、少なくとも一つの箱には二つ以上のものが入ります。より正確に言えば、少なくとも一つの箱には ⌈N/k⌉ 個以上のものが入ります。これは N/k 以上の最小の整数を表します。

各記号の意味

N

入れるものの数

k

箱の数

⌈N/k⌉

N/k の切り上げ。最も多く入っている箱が少なくとも保持する数

公式の導き方

1. なぜ ⌈N/k⌉ なのか。すべての箱に入っているものが N/k 個未満だとすると、k個の箱の合計は k × N/k = N 個未満になってしまい、全部でN個あることと矛盾します。したがって、少なくとも一つの箱には N/k 個以上のものが入っており、ものの数は整数であるため、それは少なくとも ⌈N/k⌉ 個となります。5つの関係を2色で分けると ⌈5/2⌉ = 3 つが同じ色になり、16個の関係を3色で分けると ⌈16/3⌉ = 6 つが同じ色になります。
2. 割り切る数のための箱の選び方。すべての整数は、奇数と2の累乗の積 m × 2ᵃ としてただ一通りに表せます。この数を箱mに入れます。同じ箱に入る二つの数は m × 2ᵃ と m × 2ᵇ（a < b）という形になり、前者が後者を必ず割り切ります。1から2nまでの奇数は 1, 3, …, 2n − 1 と全部でn個なので、箱はn個です。したがって、n + 1 個の数を選べば、どこかの箱に二つ入ることになります。この限界は正確です。n + 1, …, 2n はn個の数であり、各箱に一つずつ入って、どれも他方を割り切りません。一番小さな数を2倍しただけでもすでに 2n を超えてしまうからです。
3. 等しい和から独立したグループへ。和が等しい二つの異なるグループAとBは、いくつかの数を共有しているかもしれません。両方からその共通の数を取り除いてみます。それぞれの和は同じだけ減るため、和が等しいという関係は保たれます。ここでどちらのグループも空になることはありません。すべての数は正なので、もしAが完全にBに含まれていたとしたら、Bの和の方が大きくなってしまうからです。結果として残るのは、和が等しく、共通の数を持たない二つの空でないグループです。このページで描画されているのはまさにそれです。