鳩ノ巣原理(Pigeonhole Principle)
鳩ノ巣原理とは, 元々は
羽の鳩を
個の
鳩ノ巣に割り当てようとするとき,
であれば2羽以上が割り当てられる巣が少なくとも1つ存在する, という原理で，発見したドイツの数学者の名前から
ディリクレの原理とも呼ばれます. 1羽ずつ割り当てても何羽か鳩が余ることを考えればあきらかですね.
より一般的に(鳩にこだわらず), 個あるものが 個()の性質のいずれかに当てはまる時, 同じ性質のものが少なくとも1組ある, ということができます.
原理自体は単純ですが, 高校では習わないので, 知っておくといいと思います. 実際, 以下のように大学入試で問われたこともあります.
例題. (早稲田大)
平面において, 
座標, 
座標がともに整数である点 
を格子点という. いま, 互いに異なる5個の格子点を任意に選ぶと, その中に次の性質をもつ格子点が少なくとも一対は存在することを示せ.
一対の格子点を結ぶ線分の中点がまた格子点となる.
格子点の 
座標はそれぞれ偶数または奇数なので, 各格子点の座標は
(偶数, 偶数), (偶数, 奇数), (奇数, 偶数), (奇数, 奇数)
のいずれかになります. ここで, 格子点は5つあるので, (鳩ノ巣原理より), 座標の偶奇( 座標が偶数であるか奇数であるか)の組が一致する2点が少なくとも一対存在します. そのような2点を選べば, その中点はまた格子点となります.
