【鳩の巣原理】（部屋割り論法）整数問題

はじめに

鳩の巣原理（部屋割り論法）という言葉を聞いたことがありますか？

原理や論法と聞くと難しく聞こえるかもしれませんが、すごく当たり前の簡単な考え方です。しかし、一度どこかでしっかりと扱っておかないと、いざ本番でこのような発想を持つことは非常に難しいです。

上の３題を使って、鳩の巣原理を理解しましょう。

鳩の巣原理（部屋割り論法）

簡単な例で言うと、

 5 匹の鳩に対して、巣が 4 つしかなかったら、どれかの巣には 2 匹以上の鳩が入っているってことです！

もちろん 5 匹の鳩すべてが同じ巣に入っっているかもしれませんし、 2 匹と 3 匹ずつに分かれているかもしれません。どのような状況になっているはわからないけど、鳩の巣原理で言いたいのは、絶対に、「少なくとも 1 つの巣に 2 匹以上の鳩がいると言うこと」です。

このことを踏まえて、問題を考えてみましょう！

【問題①】について

【問題①】については、鳩の巣原理を理解すれば当たり前なのがわかりますか？

・鳩 ⇒ 366 人

・巣 ⇒ 365 日

と考えると、誰か 2 人は誕生日が重なるよねって言う話です。

すごく当たり前のことだ！と思ってくれたらそれでOK！！

【問題②】

【補題】連続する２つの自然数は互いに素である．

問題②の解答

・鳩 ⇒ 51 個の数

・巣 ⇒ { 1 , 2 } , { 3 , 4 } , { 5 , 6 } , ・・・ , { 99 , 100 } の 50 個の組

【問題③】

問題③の解答

それぞれの格子点の \(x , y , z\) 座標の偶奇に注目してグループ分けを以下の通りに行うと

1. （ 偶数 ，偶数 ，偶数 ）
2. （ 偶数 ，偶数 ，奇数 ）
3. （ 偶数 ，奇数 ，偶数 ）
4. （ 偶数 ，奇数 ，奇数 ）
5. （ 奇数 ，偶数 ，偶数 ）
6. （ 奇数 ，偶数 ，奇数 ）
7. （ 奇数 ，奇数 ，偶数 ）
8. （ 奇数 ，奇数 ，奇数 ）

の 8 タイプしかない．

したがって、 9 個以上の格子点を準備すれば、必ず同じタイプの格子点が 2 個以上存在し、その同じタイプの格子点の中点を考えれば、必ず格子点となる．

・鳩 ⇒ \(n=9\)

・巣 ⇒ 8 タイプの格子点

と考えたと言うことです！

最後に

「鳩」と「巣」が何に対応するかを考えるには少し工夫と慣れが必要になりますが、考え方自体は非常に単純なものです。大学入試において頻出ではありませんが、たまに出題れています。

全く知らない状態で、初見で解くことはさすがに難しいかと思いますので、考え方だけでもおさえておいてください。