日比谷高校のススメ

日比谷高校出身者たちが日比谷高校の紹介や、勉強に関する様々なことを語ります。

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

↓ここからカテゴリー別に記事を見ることができます。↓

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

 

 

 

鳩の巣原理とは

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

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

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

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

 

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

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

 

 

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

 

問題1

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

 

解答1

f:id:hby:20181114230040j:plain

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

 

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

 

 

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

 

スポンサーリンク

 

 

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

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

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

 

解答2

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

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

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

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

どちらも奇数であれば、

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

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

 

補足2

この問題の解法では、箱は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個の点をもってきても成り立つ、というのがこの問題の内容でした。

 

 

 

 

問題3

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

 

解答3

\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で割り切れる。

 

補足3

「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

Copyright © 2017 日比谷高校のススメ All rights reserved.