鳩ノ巣原理を使った面白い問題５選【なぜ成り立つの？無限についても考察】

こんにちは、ウチダです。

皆さんは、「鳩ノ巣原理（部屋割り論法）」とは何かご存じですか？

[ふきだし set=”悩む女性”]え、これのどこが難しいの？当たり前のこと言ってるだけでしょ？[/ふきだし]

[ふきだし set=”悩む男性”]鳩ノ巣原理を問題でどう使うかがわかりません。面白い問題をたくさん解きたいです。[/ふきだし]

よって本記事では、鳩ノ巣原理を使った面白い問題 $5$ 選から、鳩ノ巣原理と無限に関する深～いお話まで

• 東北大学理学部数学科卒業
• 教員採用試験に１発合格　→　高校教諭経験アリ

の僕がわかりやすく解説します。

鳩ノ巣原理（部屋割り論法）を使った面白い問題５選

冒頭でもお伝えした通り、鳩ノ巣原理はたしかに当たり前のことしか言ってません。

ただし、この理論を使わないと解けない問題もあるのです！

具体的には

• 整数の問題【２問】
• 正三角形の問題
• 格子点の問題（1996年早稲田入試問題）
• 【超良問】タイルの問題
• 血液型や誕生日のお話（おまけ）

の $5$ 問 $+α$ について解説します。

[ふきだし set=”ウチダ”]それぞれリンクになってますので、お好きな所から読んでください！[/ふきだし]

整数の問題【２問】

最初からそこそこ難しい問題を取り上げてみました。

何が”鳩”で、どれが”鳩ノ巣”か、考えて証明してみましょう＾＾

【解答】

(1)　$4$ で割ったときの余りで組分けすると、$0$，$1$，$2$，$3$ の $4$ 組ができる。

ここで、異なる自然数が $5$ つあるので、$4$ で割った余りが同じ数の組が少なくとも $1$ つ存在する。

したがって、その $2$ 数の差は必ず $4$ の倍数となる。

(2)　和が $41$ となる組合せは、全部で $20$ 組ある。

ここで、$21$ 個の自然数を選ぶので、$2$ 個以上入っている組が少なくとも $1$ つ存在する。

したがって、和が $41$ となる組合せは必ず存在する。

(解答終了)

(1)(2)の”鳩”と”鳩ノ巣”をまとめておくと…

• (1)　→　鳩は「 $5$ 個の自然数」，鳩ノ巣は「 $4$ で割った余りで分けられた $4$ 組」
• (2)　→　鳩は「 $21$ 個の自然数」，鳩ノ巣は「和が $41$ となる $20$ 組」

どちらの問題も、鳩が鳩ノ巣より $1$ 個だけ多くなってますよね！

よって、鳩ノ巣原理が使えるわけです。

正三角形の問題

さて、この問題でも、「鳩と鳩ノ巣がそれぞれ何か」考えると…

• 鳩　　　→　$5$ つの点
• 鳩ノ巣　→　？？？

と、鳩ノ巣が与えられていないことに気づきます。

では、どうやって鳩ノ巣を作ればいいでしょうか。

良問ですので、ぜひお考え下さい。

↓↓↓（解答アリ）

【解答】

$5$ つの点が鳩なので、距離が $1 \ (cm)$ 以下となる $4$ 組が作れれば勝ち。

よって、以下の図のように組分けすればいいことに気づく。

$5$ つの点を置くので、①～④の少なくとも $1$ つには $2$ つの点が存在することになる。

したがって、その $2$ 点間の距離は $1 \ (cm)$ 以下となる。

(解答終了)

「鳩が $5$ 匹のときは鳩ノ巣を $4$ つ作ればいい。」

ゴールが見えていると、解答が作りやすくなってきますね＾＾

格子点の問題（1996年早稲田入試問題）

さて、この問題も鳩が $5$ 匹なので、鳩ノ巣を $4$ 組作ればいいことになります。

$2$ つの整数の組で $4$ 組ということは…

• $x$ で $2$ 通り
• $y$ で $2$ 通り

に分ければ、$2×2=4$ 通りですね。

…このヒントで、もうお分かりかもしれませんね。

それでは解答に移ります。

【解答】

格子点の種類を、

と、偶奇によって $4$ 組に分ける。

※この組合せの式は横にスクロールできます。（スマホでご覧の方対象。）

すると、同じ種類の $2$ つの格子点 $( \ a_1 \ , \ b_1 \ )$，$( \ a_2 \ , \ b_2 \ )$ の中点であれば、

$$( \ \frac{a_1+a_2}{2} \ , \ \frac{b_1+b_2}{2} \ )$$

であるので、$x$，$y$ 座標共に整数となる。

したがって鳩ノ巣原理より、$2$ つの格子点を結ぶ線分の中点がまた格子点となる組合せが必ず存在する。

(解答終了)

この問題は、$1996$ 年の早稲田大学の入試問題でもあります。

大学入試でもたま～に出題されることがあるので、しっかり押さえておきたいところですね。

【超良問】タイルの問題

最後は超良問。

ただ、問題設定がややこしいので、図解します。

[ふきだし set=”ウチダ”]「本当に必ず存在するのか」実験して確かめるのも面白いですよ。[/ふきだし]

さてこの問題は、鳩ノ巣原理を使うと知っていても難しいと思います。

超良問ですので、ぜひここで一度立ち止まって考えていただきたいです！

それでは解答です。

【解答】

鳩と鳩ノ巣を、それぞれ次のように定義する。

• 鳩　　　…　縦 $3$ マス、横 $1$ マスのタイル（これを「タイルＡ」と呼ぶことにする）。
• 鳩ノ巣　…　タイルＡの種類のうち、全て白 or 全て黒 を除いたもの

すると、鳩ノ巣は $6$ 組になる。

ここで、横が $7$ マスなので、この $6$ 種類のタイルから $7$ 個選ぶ。

したがって、$4$ 隅の色が一致する長方形は必ず存在する。

(解答終了)

一つだけ補足しておきます。

[ふきだし set=”考える女性”]「全て黒」「全て白」を除く理由は何ですか？[/ふきだし]

これは、たとえば全て黒のタイルＡを使ってしまった場合、もう黒が $2$ つ以上含まれるタイルＡは使えなくなります。

すると残り $6$ つのタイルＡで $3$ 種類のタイルＡしか使えなくなってしまうため、鳩の巣原理より条件を満たす長方形が作れてしまいます。

ようは、「条件を満たす長方形が簡単に作れてしまうから、考える必要がない」ということになりますね。

[ふきだし set=”ウチダ”]この問題は、僕が高校教諭として働いていたときに研修で解いた問題です。短い教師人生の中で一番感動した問題ですね。[/ふきだし]

とまあ、鳩も鳩ノ巣も何なのか自分で定義しなければ解けない、メチャクチャ美しい問題の解説でした～。

血液型や誕生日の話（おまけ）

おまけですが、血液型や誕生日に関する問題もあります。

解答は大丈夫ですね。

それぞれ鳩ノ巣原理を使えば一瞬で示せます。

ただ…この問題の(2)には続きがあるのです。

• $23$ 人集まれば、同じ誕生日の人がいる確率は、約 $50$ ％
• $40$ 人集まれば、同じ誕生日の人がいる確率は、約 $90$ ％

同じ誕生日の $2$ 人組は、体感よりも結構高い確率で存在するんですね！

[ふきだし set=”ウチダ”]これは「誕生日のパラドックス」と呼ばれる有名な問題です。詳しく知りたい方は、「誕生日のパラドックスとは【同じ誕生日の人がいる確率はどのくらい？】」の記事をご覧ください。[/ふきだし]

鳩ノ巣原理（部屋割り論法）と無限に関する深～い考察【集合論】

さて、最後に内容の濃い話をして終わりにします。

具体的には、

• 自然数の個数と偶数の個数が同じであること
• 鳩ノ巣原理（部屋割り論法）はなぜ成り立つのか

以上 $2$ つについて、簡単に解説します。

可算集合と非可算集合【濃度って何？】

鳩ノ巣原理を使って、こんな問題を考えてみましょうか。

[ふきだし set=”考える男性”]こんなのカンタンじゃん。もちろん、すべての自然数の個数の方が多いでしょ。[/ふきだし]

そう思った方が大半だと思います。

ただ…実はこれ、「自然数の個数＝偶数の個数」が成り立つのです！！

どういうことか、図解して簡単に解説します。

よって、鳩ノ巣原理の対偶を考えてあげれば、$1$ つずつキレイに割り振れるとき、個数は同じだということになります。

これを応用すれば、$3$ の倍数，$4$ の倍数，…と、何であっても自然数の個数と等しくなることが言えるんですね～。

[ふきだし set=”ウチダ”]無限に関する話はイメージしづらいと思いますが、これは理論的かつ厳密に示すことができます。数学って不思議ですね！[/ふきだし]

また、これを応用した考えが、可算集合・非可算集合であり、非可算集合の存在性を示したものが「（カントールの）対角線論法」と呼ばれる証明方法です。

簡単にまとめると…

• 可算集合　…　自然数の集合と同じ個数（数学では「濃度が等しい」という。）である集合のこと。
  • （具体例）… 偶数の集合、$3$ の倍数の集合、有理数の集合など
• 非可算集合　…　自然数の集合よりも個数が多い集合のこと。
  • （具体例）… 実数の集合、無理数の集合など

あとの話は、がっつり大学数学の範囲ですので、ここでは省略します。

興味のある方は「対角線論法とは～（準備中）」の記事をご覧ください。

鳩ノ巣原理はなぜ成り立つのか【ペアノの公理】

鳩ノ巣原理って、一見すると当たり前（自明）に思えます。

ただ、これは自然数の集合で考えているから成り立つのであって、実数や無理数の集合だと成り立ちません。

[ふきだし set=”ウチダ”]ここら辺の話が、先ほど説明した「可算集合・非可算集合」にもつながってきます。[/ふきだし]

では、一体どういう原理で成り立っているかというと、自然数に成り立つ公理が重要になってきます。

…はい、「なんじゃこりゃ」と感じましたね？

大丈夫、正しい感覚です。(笑)

実は、我々が考えている自然数というのは、この $5$ つの条件を満たすものとして定義されています。

[ふきだし set=”ウチダ”]これらの条件をよ～く見てみると… $5$ 番って、数学的帰納法ではありませんか？[/ふきだし]

そうなんです。実は数学的帰納法が成り立つ理由も、このペアノの公理のおかげなんです！。

また鳩ノ巣原理については、条件 $2$ や条件 $4$ などを使えば、成り立つことが示せます。

※厳密には、「自然数 $m$，$n$ に対して写像 $f$ : $\{1,2,…,m\}$ → $\{1,2,…,n\}$ が単射ならば $m≦n$ である」ことを示せばOKです。

興味を持った方は、以下の関連記事から勉強してみてください。

• 数学的帰納法とは～（準備中）
• ペアノの公理とは～（準備中）

鳩ノ巣原理（部屋割り論法）に関するまとめ

本記事のポイントを改めてまとめておきます。

1. 鳩ノ巣原理を使うと簡単に証明できる問題は多いです。（「タイルの問題」はぜひ友達に出題してみてください！）
2. 鳩ノ巣原理を使うと、自然数の個数と偶数の個数が等しいことが示せます（大学で習う「対角線論法」につながってきます）。
3. 鳩ノ巣原理がなぜ成り立つのか、については「ペアノの公理」が一番しっくりくると思います。

最後はがっつり大学数学のお話でしたが、いかがだったでしょうか。

こういうところから興味を持って、大学数学を勉強してみるのもアリかと思いますよ＾＾

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

あわせて読みたい

整数の性質とは？【高校数学Ａの解説記事総まとめ２５選】 「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全２５個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

以上で終わりです。