鳩ノ巣原理

数学に「鳩ノ巣原理」と言われるものがある。

「鳩」と聞くと最近はあの売国鳩を連想してあまりいい気分でないが、話は簡単で、n個の容器に(n+1)個以上のモノを入れようとすると、少なくともひとつの容器には複数個のモノが入っているという、当たり前のことである。
「モノ」が「鳩」で、「容器」が「鳩ノ巣」ということか。
こんな当たり前の話が、数学の問題を考える時に強力な武器となるのである。

例えば、10メートルｘ10メートルの正方形の空き地に、101本の旗を立てるとする。
すると、お互いの距離が√2メートル以下の2本の旗のペアが必ずできるのである。
これを正攻法で証明しようとすると、結構難しそうである。
しかし、鳩ノ巣原理を使うと、いとも簡単に証明できるのである。
空き地を1メートルｘ1メートルの小さい正方形のマス100個に分ける。
すると、この小さいマスが「鳩ノ巣」となるのである。
空き地に101本の旗を立てると、少なくとも一つのマスには2本の旗が立つ。
その2本の旗は1メートルｘ1メートルの正方形の中にあるから、互いの距離は√2メートル以下となるのである。

あるいは、こんな例もある。
xy座標平面の点で、x座標・y座標がともに整数である点を「格子点」とよぶ。
そして、5個の格子点を好きなように取ると、そのうちのある2点で、互いを結ぶ線分の中点がまた格子点となるようなものが必ず存在するのである。
これも、まともに証明しようとすると難しいが、鳩の巣原理を使うとあっさりと証明できる。
今度の場合、鳩ノ巣の役割を果たすのは、下記の４つの格子点の座標のタイプである。
1) （偶数、偶数）
2) （偶数、奇数）
3) （奇数、偶数）
4) （奇数、奇数）
5点の格子点を取ると、上の4タイプのうち少なくともひとつのタイプには2個以上の格子点が属する。
そのとき、その2つの格子点をとると、その格子点のペアが属するタイプがなんであろうと、2点を結ぶ線分の中点はx座標、y座標ともに整数、すなわち、格子点となるのである。

このように、鳩ノ巣原理という極めて当たり前の話が強力な論法となるので、数学というのは何があるのかわからない、奥の深い森なのである。