少なくとも1つ存在することの証明(存在証明)の1つの手法に,\ 部屋割り論法がある.
鳩ノ巣原理,\ ディリクレの原理とも呼ばれ,\ 以下のように表現される.
「\,$n}$個の部屋に$n+1}$人が入るとき,\ 2人以上入る部屋が少なくとも1つは存在する」
「\,$n}$人が$n}$個の部屋に入るとき,\ 2人以上入る部屋がなければ,\ 各部屋に1人ずつ入る」
これらは,\ 言われてみれば当たり前のことである.
しかし,\ 原理として認識すると,\ ある種の証明問題において極めて強力な武器となる.
まずは簡単な具体例を1つ示そう.
全校生徒733人の高校には,\ 誕生日も性別も同じ2人の生徒が少なくとも1組存在する.
誕生日と性別の組合せの総数は$366×2=732$通りである.
よって,\ 733人いれば少なくとも2人の誕生日と性別は同じである(部屋割り論法).
この論法の重要性は,\ 性質を満たす人が誰かを具体的に特定する必要がないことにある.
1人ずつ調べずとも,\ その存在が保証されるわけである.
自分(特定の誕生日と性別)と誕生日も性別も同じ人が存在することを保証するわけではない.}
誰かと誰か(自分の可能性もある)の誕生日と性別が同じであることが保証される.
本項では,\ 部屋割り論法が有効な代表的問題を扱う.\ 大学入試でも時々出題される.
原理はほぼ自明だが,\ 実際の問題に応用するには経験が必要になる. \\
$n$を自然数とする.
(1)\ \ 1から$2n$までの自然数の中から異なる$n+1$個の自然数を選んだとき,\ その中に
\ \ 和が$2n+1$になるような2数の組合せが存在することを示せ.
(2)\ \ 1から$2n$までの自然数の中から異なる$n+1$個の自然数を選んだとき,\ その中に
\ \ 互いに素である2数の組合せが存在することを示せ.
(3)\ \ 異なる$n+1$個の整数があるとき,\ その中に差が$n$の倍数となるような2個の整数
\ \ が存在することを示せ.
(4)\ \ 整数ではないすべての有理数は有限小数または循環小数であることを示せ. \\
(1)\ \ 1から$2n$までの自然数を和が$2n+1$になる2数ずつに分ける.
$(1,\ 2n),\ (2,\ 2n-1),\ (3,\ 2n-2),\ ･･････,\ (n-1,\ n+2),\ (n,\ n+1) (n組)}$
異なる$n+1$個の自然数を選んだとき,\ 少なくとも2個は同じ組の数}である.
つまり,\ $n+1}$個の自然数の中に和が$2n+1}$になるような2数の組合せが存在する.}
(2)\ \ 1から$2n$までの自然数を互いに素になる2数ずつに分ける.
$(1,\ 2),\ (3,\ 4),\ (5,\ 6),\ ･･････,\ (2n-3,\ 2n-2),\ (2n-1,\ 2n) (n組)}$}
異なる$n+1$個の自然数を選んだとき,\ 少なくとも2個は同じ組の数}である.
つまり,\ $n+1}$個の自然数の中に互いに素である2数の組合せが存在する.} $n$で割ったときの余りは$0,\ 1,\ 2,\ ･･･,\ n-1$の$n$種類}である.
異なる$n+1$個の整数があるとき,\ 少なくとも2個は$n$で割ったときの余りが等しい.}
つまり,\ $n+1}$個の整数の中に差が$n}$の倍数となるような2数の組合せが存在する.}
(4)\ \ 有理数を$ mn\ (m,\ n:自然数\,;n≠0)$とおく.
$m$を$n$で割り算し続けるとする.
このとき,\ 各段階における余りは$0,\ 1,\ 2,\ ･･･,\ n-1$の$n$種類}のいずれかである.
余りが0になる}とき,\ 有理数$ mn$は有限小数}である.
余りが0にならない}とする.
このとき,\ 各段階における余りは$1,\ 2,\ ･･･,\ n-1$の$n-1$種類}のいずれかである.
よって,\ $n$回目の計算までには必ず以前と同じ余りが現れ,\ 以降は循環する.}
∴$ 整数ではないすべての有理数は有限小数または循環小数である.}
整数の選び方に関する存在証明}では,\ 部屋割り論法が有効である.
実際の問題を解くときは,\ 部屋と人に対応するものが何かを考えることになる.
(1)\ \ nのままではわかりにくいので,\ n=5として具体的に考えてみる.
\ \ 1から10までの数から6個を選んだとき,\ 和が11になる2数の組合せの存在証明となる.
\ \ この6個という個数は,\ おそらくは存在が保証されるために最低限必要な個数}である.
\ \ 最低限必要な個数より多く選ぶとする問題も作れるが,\ 普通はそんな意地悪な出題はしない.
\ \ よって,\ 部屋割り論法を適用するために作るべき部屋は5個}であるとわかる.
\ \ この例では,\ 条件(和が11)を満たす5組(1,\ 10),\ (2,\ 9),\ (3,\ 8),\ (4,\ 7),\ (5,\ 6)を作ればよい.
\ \ この5組には,\ 10個の自然数がもれなく含まれている}という点が重要である.
\ \ それゆえ,\ 10個から6個の自然数を選ぶとき,\ 同じ組の数が少なくとも2個選ばれる.
\ \ これを一般化すると解答のようになる.
(2)\ \ (1)と同様に考え,\ 互いに素である2数の組をn個作る.}
\ \ このとき,\ 連続する2整数は互いに素}を利用することになる.\ この性質は常識としておきたい.
\ \ ここでは省略したが,\ 自明ではないので記述試験では簡単にでも証明を示しておくとよい.
\ \ n,\ n+1が共通の素数の約数pをもつとすると,\ n=pk,\ n+1=pl\ (k,\ l:整数)とおける.
\ \ p(l-k)=1となるが,\ pは素数なので矛盾である.
(3)\ \ 自分の携帯番号11桁を5個の整数に分割してみてほしい.\ 例えば,\ 090\,|\,11\,|\,34\,|\,56\,|\,79\,とする.
\ \ その5個の整数の中に差が4の倍数となるような2数の組合せが必ず存在するはずである.
\ \ この例の場合は,\ 90-34=56,\ 79-11=68が存在する.\
\ \ 一見不思議に思えるが,\ 部屋割り論法を用いると一般化した命題を容易に証明できる.
\ \ 存在保証に最低n+1個必要と思われるので,\ 条件を満たす部屋をn個作ればよい.
\ \ ここで,\ 整数分野では,\ 次の言い換えを常識としておく必要がある.
\ \ nで割ったときの余りが一致\ ⇔\ 差がnの倍数(nで割り切れる)}
\ \ a_1=q_1n+r_1,\ a_2=q_2n+r_1\ ⇔\ a_1-a_2=n(q_1-q_2)\ ということである.
\ \ 結局,\ nで割ったときの余りが一致する2数の存在証明}に帰着する.
\ \ nで割ったときの余りはn種類である}点が重要で,\ 余りのもれがないn個の部屋を作成できる.
\ \ n+1個あれば,\ 少なくとも2個は同じ余りの部屋に入ることになるわけである.
(4)\ \ 例えば,\ 17\,を筆算で割り算してみるとよい.
\ \ 7で割ったときの余りは,\ 割り切れないのならば1,\ 2,\ ･･･,\ 6の6種類しかない.
\ \ よって,\ 遅くとも7回目までには必ず以前と同じ余りが現れ,\ 以降は循環する.
座標がすべて整数である点を格子点という.
(1)\ \ 座標平面上の格子点から異なる5個を選んだとき,\ その中に中点が格子点となる
\ \ ような2個の組合せが含まれていることを示せ.
(2)\ \ 座標空間上の格子点から異なる9個を選んだとき,\ その中に中点が格子点となる
\ \ ような2個の組合せが含まれていることを示せ. \\
(1)\ \ すべての格子点の偶奇パターンは,\ 次の4通りのいずれかである.
$(偶数,\ 偶数),\ (偶数,\ 奇数),\ (奇数,\ 偶数),\ (奇数,\ 奇数)}$}
よって,\ 5個の格子点を選んだとき,\ 少なくとも2個は同じパターンの格子点}となる.
同じパターンの2個の格子点の中点もまた格子点である.
∴$ 5個の格子点の中に中点も格子点となる組合せが存在する.
(2)\ \ すべての格子点の偶奇パターンは,\ 次の8通りのいずれかである.
$(偶数,\ 偶数,\ 偶数),\ (偶数,\ 偶数,\ 奇数),\ (偶数,\ 奇数,\ 偶数),\ (奇数,\ 偶数,\ 偶数),}$
$(偶数,\ 奇数,\ 奇数),\ (奇数,\ 偶数,\ 奇数),\ (奇数,\ 奇数,\ 偶数),\ (奇数,\ 奇数,\ 奇数)}$
よって,\ 9個の格子点を選んだとき,\ 少なくとも2個は同じパターンの格子点}となる.
同じパターンの2個の格子点の中点もまた格子点である.
∴$ 9個の格子点の中に中点も格子点となる組合せが存在する.}
格子点の中点に関する存在証明}では,\ 部屋割り論法が有効である.
一般に,\ 2点の座標を足して2で割ると中点が求まる.
例えば,\ 2点(a_1,\ a_2),\ (b_1,\ b_2)の中点の座標は\ a_1+b_1}{2},\ a_2+b_2}{2}\ である.
よって,\ 中点が格子点になるか否かは,\ a_1+b_1\,とa_2+b_2\,が2の倍数になるか否かで決まる.}
和が2の倍数となるのは,\ (偶数)+(偶数)=(偶数),\ (奇数)+(奇数)=(偶数)の場合に限られる.
結局,\ a_1\,とb_1,\ a_2\,とb_2\,の偶奇がいずれも一致する場合に中点が格子点}となる.
つまりは,\ 偶奇パターンが一致する2個の点の存在証明に帰着}する.
格子点の偶奇パターンで4個の部屋を作成できるから,\ 5個あれば少なくとも2個は同じ部屋に入る.
空間の場合も同様である.
1辺2の正方形の周または内部に異なる5点をとるとき,\ 距離が$√2$以下となる
\ \ ような2点の組合せが存在することを示せ.
(2)\ \ 1辺2の正三角形の周または内部に異なる5点をとるとき,\ 距離が1以下となる
\ \ ような2点の組合せが存在することを示せ.
(3)\ \ 1辺2の正方形の周または内部に異なる9点をとるとき,\ 三角形の面積が$12$以下
\ \ となるような3点の組合せが存在することを示せ. \\
1辺2の正方形を1辺1の4個の正方形}に分割する.
5個の点をとるとき,\ 少なくとも2個は同じ正方形の周または内部の点}となる.
1辺1の正方形の周または内部にある2点の最大距離は対角線の$√2$である.
∴$ 5点の中に距離が$√2}$以下となるような2点の組合せが存在する.}
(2)\ \ 1辺2の正三角形を1辺1の4個の正三角形}に分割する.
5個の点をとるとき,\ 少なくとも2個は同じ正三角形の周または内部の点}となる.
1辺1の正三角形の周または内部にある2点の最大距離は1である.
∴$ 5点の中に距離が1以下となるような2点の組合せが存在する.
(3)\ \ 1辺2の正方形を1辺1の4つの正方形}に分割する.
9個の点をとるとき,\ 少なくとも3個は同じ正方形の周または内部の点}となる.
1辺1の正方形の周または内部にある3点で作られる三角形の面積の最大値は$12$である.}
∴$ 9点の中に三角形の面積が$12}$以下となるような3点の組合せが存在する
座標平面上の最大距離や最大面積に関する存在証明}では,\ 部屋割り論法が有効である.
(1),\ (2)\ \ 存在保証に最低5点必要と思われるので,\ 条件を満たす部屋を4個作ればよい.
(3)\ \ 右図において,\ 三角形の面積Sは\ S=12s_1t+12s_2t=12(s_1+s_2)t\ である.
\ \ 3点が1辺1の正方形の周または内部にあるときs_1+s_2≦1,\ t≦1より,\ S≦12\,である.
