数学コラム
部屋割り論法 (鳩の巣原理)
当たり前のような話ですが，例えば5人を4つの部屋に分けようとすると，どうしても2人以上入る部屋ができることになります。なぜなら，人数に対して部屋の方が少ないからです。(きちんと証明するなら背理法で)
この論理を利用したのが部屋割り論法または鳩の巣原理といわれる論法です。こんな当たり前のことがどう役に立つのか？と思ってしまいますが，これに上手く当てはめればたちまち解決する証明問題もあり，その様はなかなか鮮やかです。
この論法が使える証明を紹介しましょう。
[命題1]
任意の $n+1$ 個の自然数がある。この中から適当に2つの自然数を選べば，その2つの自然数の差は $n$ で割り切れるようにできる。
[証明]
自然数を $n$ で割ったときの余りは $0,~1,~2,~\cdots,~n-1$ の $n$ 通りである。よって，$n+1$ 個の自然数の中には $n$ で割ったときの余りが等しい2数が存在し，この2数の差は $n$ で割り切れる。■
後半をきちんと式で示すならば，等しい余りを $r$ とおいて，余りの等しい2数を，$a=pn+r$，$b=qn+r$ と表すと，$a-b$$\;=(pn+r)-(qn+r)$$\;=(p-q)n$ となります。
[命題2]
座標平面上に任意の5つの格子点があり，これらを結ぶすべての線分を考える。このとき，これらの線分の中点のうち少なくとも1つは格子点である。
[証明]
すべての格子点は各座標の偶奇によって，(偶, 偶), (偶, 奇), (奇, 偶), (奇, 奇)の4タイプに分けられる。5つの格子点があれば，このうち少なくとも2つは同じタイプに属するので，その2つの点を結ぶ線分の中点は格子点である。■
[命題3]
1辺の長さが2の正三角形の内部に任意の5つの点をとったとき，その中のある2点は距離が1より小さい。
[証明]
正三角形の各中点を結んで，下の図のように4つの正三角形の領域に分ける。境界線上は中央の正三角形に含むとする。(実際はどちらに含むとしてもよい)
5つの点をこの中にとると，2つ以上の点が入る領域があり，同じ領域内にある2点間の距離は1より小さい。(どの領域も正三角形の頂点は含まないことに注意) ■
どの証明もはじめから部屋が与えられているわけではないので，それをどう設定するかというところに工夫が必要です。
では，いくつか関連問題を載せておきます。興味があれば挑戦してみてください。
[問題1]
$1,~2,~\cdots,~4n$ の $4n$ 個の自然数の中から $2n+1$ 個を選ぶとき，その $2n+1$ 個の自然数の中に差が $2$ である2数が必ず含まれることを証明せよ。
[問題2]
$n$ 個の任意の自然数の列 $a_1,~a_2,~\cdots,~a_n$ がある。この中から連続する一部 $a_i,~a_{i+1},~\cdots,~a_j$ ($1\leqq i\lt j\leqq n$) を選んで，その和が $n$ の倍数であるようにできることを証明せよ。
[問題3]
1辺の長さが $6$ の正方形の領域(辺上も含む)がある。この領域内に $n$ 個の点をとり，どの2点も距離が $3$ 以上になるようにする。
これが可能な $n$ の最大値は $9$ であることを証明せよ。
また，次の問題は数学の部屋で見つけた問題ですが，最初「これは部屋割りだ！」と思って挑戦したのに，部屋割りで解く方法は分かりませんでした。部屋割りでは無理なのかなぁ？
[問題4]
$2n-1$ 個の任意の自然数がある。($n$ は自然数，$2n-1$ 個の中に同じ自然数があっても構わない) その中のある $n$ 個の自然数の和で，$n$ で割り切れるものが存在することを証明せよ。
このコラムで以前に紹介した代数学の基本定理に触れる面白い証明にも，この部屋割り論法が使われています。
ところで，この部屋割り論法は無限の場合にも拡張できます。
"有限個の部屋に無限個のものを入れようとすれば，無限個のものが入っている部屋が必ず存在する"
例えば，「有界な数列には少なくとも１つの集積値が存在する」というワイエルストラスの定理の証明にはこの原理が利用できます。
(2003/08/29)