鳩の巣原理（部屋割り論法）の公式｜n+1個をn個の箱に入れる原理の証明・余りや図形の分割で使う例題【大学数学・東大京大レベル】

うかるくん

鳩の巣原理って当たり前すぎて、どこで使うのかわからないよ。

合格先生

「必ず〜となる2つがある」を示すときだ。割った余りや図形の区切りを箱にするのがコツだぞ。

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

5羽の鳩が4つの巣に入れば、どこかの巣には2羽以上います。あたり前に見えるこの原理が、整数や図形の「必ず〜となるものが存在する」という証明で大活躍します。部屋割り論法、ディリクレの箱入れ原理（引き出し論法）ともいいます。

証明（背理法）

基本形：どの箱にも1個以下しか入っていないと仮定します。すると全部で多くても $1\times n=n$ 個。ところが実際は $n+1$ 個あるので矛盾。よって2個以上入っている箱があります。

一般形：$k=\left\lceil\dfrac mn\right\rceil$ とし、どの箱にも $k-1$ 個以下しか入っていないと仮定します。$k-1<\dfrac mn$（$k$ は $\dfrac mn$ 以上の最小の整数だから）なので、全部で

個より少なくなり、$m$ 個あることに矛盾します。よって $k$ 個以上入っている箱があります。

使い方のコツ：問題の中から「何を箱にするか」を見つけるのが勝負です。整数なら割った余り、図形なら領域を分ける、が2大パターンです。

大学受験での使い方

高校の範囲をこえる内容と入試での使い方

教科書での位置：鳩の巣原理は、高校の教科書で「公式」として習うものではありません（発展・コラムで紹介されることはあります）。しかし考え方は背理法そのものなので、高校数学で完全に説明できます。大学では組合せ論（離散数学）の基本原理として学びます。

入試での使い方：

• 答案では「鳩の巣原理より」とだけ書かず、「箱は何で何個、入れるものは何個」をはっきり書きます。そうすれば、それ自体が証明になります。
• 難関大の入試では、「必ず〜となる2つが存在することを示せ」という整数・図形の問題で、この原理が背景になっているものがあります。
• 「存在する」ことは言えても、どれがそうなのかは教えてくれません。具体的に求める問題では別の方法が必要です。

よくある間違い

合格先生

一般形は切り上げだ。100個を7箱なら14ではなく、15個以上の箱があるんだぞ。

• ものの数と箱の数が同じで使う：$n$ 個を $n$ 個の箱に入れても、1個ずつ入るかもしれません。ものが箱より多いことが必要です。
• 一般形で切り捨てる：100個を7箱なら $100\div7=14.28\cdots$ で、答えは14ではなく15個以上（切り上げ）。$7\times14=98$ 個では足りないからです。
• 箱の分け方にもれや重なりがある：どのものも、どれか1つの箱に必ず入るように分けます。図形では境界の点も入るように「周をふくめて」考えます。

練習問題

合格先生

何を箱にするか、まずそれを決めよう。

1. 大学受験 何人以上集まれば、生まれた月が同じ人が必ず2人以上いるといえますか。
   答えと解説を見る

   月は12通り（箱12個）。12人では全員ちがう月のこともあるが、13人なら必ず同じ月の2人がいる。答え：13人
2. 大学受験 100個のボールを7つの箱に入れるとき、少なくとも何個入っている箱が必ずありますか。
   答えと解説を見る

   $\left\lceil\dfrac{100}{7}\right\rceil=15$。各箱14個以下なら合計98個以下で足りないので、15個以上の箱がある。答え：15個
3. 大学受験 $n$ 個の整数 $a_1,\ a_2,\ \ldots,\ a_n$ があります。この中から1個以上を選んで、その和を $n$ の倍数にできることを示しなさい（連続する番号から選べることも示す）。
   答えと解説を見る

   $S_k=a_1+\cdots+a_k$（$k=1,\ \ldots,\ n$）を考える。どれかが $n$ の倍数なら終わり。そうでなければ、$n$ 個の $S_k$ を $n$ で割った余りは 1〜$n-1$ の $n-1$ 通りなので、鳩の巣原理より余りが等しい $S_i,\ S_j$（$i<j$）がある。$S_j-S_i=a_{i+1}+\cdots+a_j$ は $n$ の倍数。

関連する公式

• 合同式（mod の計算）
• 整数の性質
• 集合の要素の個数（包除原理）
• ガウス記号
• 順列・組合せの公式
• カタラン数

よくある質問

あわせて読みたい

• 合格大作戦 算数・数学公式辞典（公式一覧）