伊藤 大幸


開催報告 数学公開講座「鳩の巣原理」

Posted by 伊藤 大幸 on
セミナー・イベント情報

6/18(日),Dear Hope5周年記念 公開講座「鳩の巣原理」を開講しました。

比較的平易な問題から,最後は数学オリンピックの問題まで,さまざまな問題に取り組みました。

参加者の皆さんにおいては,日ごろ触れることがほとんどないタイプの問題を前にして,うんうん唸りながら格闘していただきました。

さて,鳩の巣原理とは,次のような原理です。

「n+1 個以上の対象を n 個以下のグループに分けるとき,2個以上の対象を含むグループが少なくとも1つ存在する。」

より簡単には、

「10羽の鳩が9つの巣に入っているとき,2羽以上の鳩が入っている巣が少なくとも1つ存在する。」

ということになります。

このことは,証明するまでもなく当たり前に感じられると思います。参加者の皆さんにも,「それはそうだよね」とすぐ納得していただきました。

今回の特別講座では,この原理をどのように問題に適用して議論を進めていくのかを一緒に考えました。

例えば,次のような問題に取り組みました。

(問題)

パーティーに100人の参加者がいるとき,その中に同じ人数の友人をもつ2人が少なくとも1組は存在することを示せ。

(着眼点)

友人の人数としてあり得るのは,0~99までの100通りあります。しかし,友人の人数が0人と99人の人は同時には存在しません(友人が99人のAさんがいれば,Aさんは残りのすべての人と友人だから,全員1人以上の友人がいる!)。

したがって,友人の人数が0人の人がいる場合と,そうでない場合とで分けて考えましょう。

(解答)

(場合1)友人が0人の参加者がいる場合

それぞれの参加者の友人の数は,0~98までの99通りがあり得る。

つまり,100人の参加者は,各人が友人の人数として0~98のいずれかの数をもつ。ゆえに鳩の巣原理から,少なくとも2人の参加者は,必ず友人の数が一致する。(鳩が参加者100人,巣が友人の人数としてありうる99通り)

(場合2)どの参加者も少なくとも一人の友人がいる場合

それぞれの参加者の友人の数は,1~99までの99通りがあり得る。

よって(場合1)と同様に考えて,少なくとも2人の参加者は,必ず友人の数が一致する。

以上から,命題は示された。 ■

このように,鳩の巣原理を問題に適用する際には,何が鳩で何が巣であるかをうまく設定することが大切です。

授業の最後には,数学オリンピックの問題として次の問題にも取り組みました。

(問題)

Aを16桁の整数とする。Aから連続する何桁かの数字をうまく取り出すと,それらの数字の積を平方数にできることを証明せよ。

 例えば,Aのある桁が4ならば,この桁だけを取り出せばよい。

(日本数学オリンピック)

(着眼点)

各桁を構成するのは1桁の整数です。1桁の整数のうち,素数は2,3,5,7の4つです。したがって,「何桁かの数字の積」をBとすると,「B=2p×3q×5r×7s」という形に素因数分解することができます。そして,これが平方数になるとは,p,q,r,sのすべてが偶数になることを意味します。

(解答)

 A の1桁目からk桁目(1≦k≦16)までの連続する数字の積をB(k)とおく。

(場合1)p,q,r,sのすべてが偶数となるようなB(k)が存在するとき:

そのB(k)が平方数です。

(場合2)p,q,r,sのすべてが偶数となるようなB(k)が存在しないとき:

p,q,r,sの偶奇の組み合わせは,24-1=15 通り存在します(p,q,r,sのすべてが偶数の場合は(場合1)で考えているため,ここでは考えません)。

一方,B(k)はk=1~16の16通りがあるから,鳩の巣原理より,2つ以上のkでp,q,r,sの偶奇の組が一致するB(k)が必ず存在します。それらをB(k1),B(k2)(k1<k2)とします。

すると,B(k2)÷B(k1)(k1+1桁目からk2桁目までの連続する数字の積)は,p,q,r,sがすべて偶数になるから,平方数となります。

以上から,命題は示されました。 ■

いかがでしたでしょうか。

いかにして「鳩」と「巣」を作っていくかという部分に醍醐味があります。

数学は計算を頑張るシーンもありますが,以上のように「いかにして議論を進めていくか」ということもとても重要です。今後も,一般的な大学入試とは一味違うテーマを用意して,特別講座を開催していきたいと考えています。

それでは,また次回お会いしましょう!