整数No.4(部屋割り論法)

$n$個の部屋に$n+1$人を入れると必ず2人以上が入る部屋が存在する
という原理を「ディリクレの部屋割り論法」という。(別名 : 鳩ノ巣原理)
では、このディリクレの部屋割り論法を使った問題を見ていきましょう。

$x-y$平面において、$x$座標、$y$座標がともに整数である点を格子点という。いま、互いに異なる5個の格子点を任意に選ぶと、その中に次の性質を持つ格子点が少なくとも1対は存在することを示せ。
一対の格子点を結ぶ線分の中点がまた格子点となる。

与えられた格子点を一般表示してみましょう。たとえば、格子点$(a, b), (c, d)$の中点の座標は$(\dfrac{a+c}{2}, \dfrac{b+d}{2})$です。いま、この中点が格子点となるので、$x$座標でいうと$a+c$が偶数でなければならず、つまり$a, c$の偶奇が一致しなければならないことが分かります。
$y$座標でも同様に考えると、($x$座標, $y$座標) = (偶数, 偶数), (偶数, 奇数), (奇数, 偶数), (奇数, 奇数)の4通りですべてのパターンをカバーできるのでこの４つを準備します。
では、解答です。

$(x, y)$において、$x, y$が偶数か奇数かで場合分けをすると、(偶数, 偶数), (偶数, 奇数), (奇数, 偶数), (奇数, 奇数)の4タイプある。5つの格子点があれば、部屋割り論法からどれか２点は同じになる。それを$(a, b), (c, d)$とすると、$a$と$c$の偶奇は一致し、さらに$b$と$d$の偶奇が一致するので$a+c, b+d$は偶数になり、$(\dfrac{a+c}{2}, \dfrac{b+d}{2})$は格子点となる。よって、題意が示された。

では、もう一題やってみましょう。

$3\times 3$の正方形内に$10$個の点を打った時、その中の距離が$\sqrt{2}$以下となる$2$点が存在することを証明せよ。

$\sqrt{2}$を作りたいので、一辺を$1$の正方形に縮小して考えてみましょう。

では、解答です。

$3\times 3$の正方形を$1\times 1$の小正方形$9$個に分割する。部屋割り論法より、$9$個の部屋に対して、$10$個の点があるので、必ず$1$部屋に少なくとも$2$点は存在する。一辺$1$の小正方形の斜辺の長さは$\sqrt{2}$であるから、同じ小正方形に属する2点の距離は$\sqrt{2}$以下であることが示された。