2019-04-27

【数学小話】鳩の巣原理、部屋割り論法

数学小話数学

高校数学の発展事項として扱われる鳩の巣原理。内容はごくごく当たり前のことですが、とても強力な証明の道具です。この原理に関する面白い事柄をご紹介します。

鳩の巣原理とは
問題１
- 解答１
問題２(早稲田大学の過去問)
- 解答２
- 補足２
問題３
- 解答３
- 補足３
”存在”を証明する

鳩の巣原理とは

鳩の巣原理は部屋割り論法、ディリクレの箱入れ原理などと呼ばれることもあります。内容は以下の通りです。

n個の物をm個の箱に入れるとき、n>mならば、物が2個以上入っている箱が必ず存在する。

例えば、5個の玉を4個の箱に入れる時、必ずどれかの箱には玉が2個以上入ることになります。

ごくごく当たり前のことです。

この鳩の巣原理を使って、このようなことが分かります。

・さいころを7回振ると、いずれかの目は必ず2回以上出る。
・血液型はA,B,O,ABの4種類がある。5人に血液型を聞くと、必ず同じ血液の2人が見つかる。
・エレベーターに乗っている人数が、押されているボタンの数より多いとき、どっかの階で2人以上がエレベーターをおりる。

では、この鳩の巣原理が使われる問題をいくつか見てみましょう。

問題１

1辺が2の正方形がある。この内部に5個の点を打つと、その中で距離が√2以下の2点が存在することを示せ。

解答１

f:id:hby:20181114230040j:plain

正方形をこのように1辺が1の正方形4つに分けると、鳩の巣原理から、5個の点のうち、同じ正方形にある2点が存在する。分けられた正方形の1辺は1だから、その2点の距離は√2以下である。

ここでは、箱が4つ、玉が5つあるわけです。

この鳩の巣原理、大学の入試問題でも、知らないと解けない問題がたまに出題されます。

問題２(早稲田大学の過去問)

xy平面において、x座標、y座標がともに整数である点(x,y)を格子点という。

互いに異なる5個の格子点を任意に選ぶと、その中に、2つの格子点を結ぶ線分の中点がまた格子点になるような2点が存在することを示せ。(1996年早稲田大学)

解答２

格子点のx座標、y座標の偶奇で分類すると、

(偶,偶),(偶,奇),(奇,偶),(奇,奇)

この4通りが存在する。
5個の格子点を任意に選ぶと、鳩の巣原理から、x座標同士、y座標同士の偶奇が一致するような2点が存在する。
2点のx座標またはy座標がどちらも偶数であれば、

$\displaystyle\frac{(偶数)+(偶数)}{2}=(整数)$

どちらも奇数であれば、

$\displaystyle\frac{(奇数)+(奇数)}{2}=(整数)$

より、この2点を結ぶ線分の中点のx座標、y座標は整数である。よって示された。

補足２

この問題の解法では、箱は4つ、玉が5つです。
箱は格子点のxyの偶奇の組み合わせ。（(偶,偶),(偶,奇),(奇,偶),(奇,奇)のこと）

適当に5つの格子点を作って、証明がやっていることを追ってみます。
5つの格子点を、

(1,1), (2,2), (3,-4), (6,1), (-1,-3)

とします。それぞれの偶奇をみると、

(1,1)と(-1,-3)はどちらも(奇,奇)で一致しています。この2点を結ぶ線分の中点の座標を求めると、

$\displaystyle\frac{1+(-1)}{2}=0$
$\displaystyle\frac{1+(-3)}{2}=-1$

から、(0,-1)となり、これは格子点です。

このように、中点がまた格子点になるような2点がとれる、ということが、どんな5個の点をもってきても成り立つ、というのがこの問題の内容でした。

問題３

pを2,5でない素数とする。 $\displaystyle 1,11,111,\dots$ という数の中に、必ずpで割り切れるものが存在することを示せ。(数検1級2次)

解答３

$\displaystyle 1,11,111,\dots,\overbrace{111\dots1}^{p+1}$ というp+1個の数を考える。

整数をpで割った余りは0からp-1までのp通りあるので、このp+1個の数を全てpで割ると、鳩の巣原理から、余りが等しい2数が存在する。その2数を、

$\displaystyle \overbrace{111\dots1}^{a}\ ,\ \overbrace{111\dots1}^{b}\ (a＜b)$

とする。この2数をpで割った余りが等しいので、この2数の差、

$\displaystyle \overbrace{111\dots1}^{b-a}\overbrace{000\dots0}^{a}$

はpで割り切れる。ここで、

$\displaystyle \overbrace{111\dots1}^{b-a}\overbrace{000\dots0}^{a}=\overbrace{111\dots1}^{b-a}\times10^a=\overbrace{111\dots1}^{b-a}\times2^a\times5^a$

と表すことができ、これがpで割り切れることと、pは2,5でない素数であることより、

$\displaystyle \overbrace{111\dots1}^{b-a}$

はpで割り切れる。

補足３

「pで割った余りが等しい2数の差はpで割り切れる」について。
例えば19と34は5で割った余りが等しく、差の34-19=15は5で割り切れます。
pで割った余りが等しい2数をap+r,bp+rとおけば、差は(a-b)pよりpで割り切れます。

”存在”を証明する

さきほどの問題3で、2,5でない素数pに対して、1,11,111,...という数の中にpで割り切れるものが存在することが証明されました。ここで面白いのが、「存在すること」が証明されただけあって、それがいくつであるかについては一切言及されていないのです。

例えば、137は素数ですから、1,11,111,...という数のどこかに、137で割り切れるものが存在するのは確実ですが、それがいくつなのか、具体的にどう求められるのか、などは一切分かりません。

「じゃあ『存在すること』だけが分かっても役に立たないじゃないか」と思うかもしれませんが、そうでもありません。存在証明はとても意味のある、重要なものです。

中学校(しばしば高校も)までの数学の問題は、基本的にまず答えがあって、それを求めることに焦点が置かれました。テストの問題文は「求めよ。」「証明せよ。」など、答えがある前提で書かれています。しかし、現実世界は「そもそも答えはあるかどうかわからない問題」であふれています。答えが必ずしもあるとは限らないのです。そのような現実の問題に立ち向かうとき、答えが存在するかどうかが分かることは大きな意味を持ちます。

ちなみに、数学では一般的に、存在定理は具体的に存在を求める定理より難しいとされています。

written by k