回 8-7 分野 8 考え方
鳩の巣原理は、n 個の箱に n + 1 個以上の物を入れると、2 個以上入る箱が必ずあるという原理です。2 月 29 日を含めて誕生日は 366 通りなので、367 人いれば誕生日が同じ 2 人が必ずいます。一般に N 個を n 箱に入れると、N ÷ n の切り上げ個以上入る箱があります。答えが少なくともいくつか (下界)、多くてもいくつか (上界) を先に決めると、探す範囲を絞れます。
答えの範囲を計算の前に決める上界と下界を、鳩の巣原理、答えの二分探索、並べ替えの回数の下界で、Python と照らして確かめます。
文 ゆめさくコード編集部公開 2026年10月30日更新 2026年10月30日出典を確かめた日 2026年10月30日
何人いれば、誕生日が同じ 2 人が必ずいるか
367 人です。2 月 29 日を含めても誕生日は 366 通りしかないので、367 人目は、それまでの誰かと必ず重なります。
8-3 では、23 人いれば誕生日が重なる確率が半分を超えると数えました。こちらは確率ではなく「必ず」です。どんな誕生日の組み合わせでも、367 人なら重なり、366 人なら重ならない組み合わせが作れます。
「n 個の箱に n + 1 個を入れると、2 個以上入る箱がある」という当たり前の事実を、鳩の巣原理と呼びます。この回では、鳩の巣原理と、答えの範囲を計算の前に決める上界と下界の考え方を、Python で確かめます。
鳩の巣原理と上界、下界
鳩の巣原理
n 個の巣に n + 1 羽の鳩が入ると、2 羽以上が入る巣が少なくとも 1 つあります。どの巣にも 1 羽以下なら、鳩は多くても n 羽で、n + 1 羽に足りないからです (反対を仮定して食い違いを示す、背理法の形です)。
英語では pigeonhole principle と呼びます。日本語では、ディリクレの箱入れ原理、部屋割り論法とも呼ばれます。
一般形
N 個を n 個の箱に入れると、N ÷ n を切り上げた数以上が入る箱があります。100 個を 7 箱に入れると、100 ÷ 7 = 14.28… なので、15 個以上入る箱が必ずあります。どの箱も 14 個以下なら、合計は多くても 98 個で、100 個に足りないからです。
箱の作り方が鍵
鳩の巣原理を使う問題では、何を箱にするかを決めるのが一番の仕事です。
| 物 | 箱 | 言えること |
|---|
| 367 人 | 366 通りの誕生日 | 誕生日が同じ 2 人がいる |
|---|
| 6 個の整数 | 5 で割った余り (0〜4) | 差が 5 の倍数になる 2 個がある |
|---|
| 平面の 5 個の格子点 | x と y の偶奇の組 (4 通り) | 中点も格子点になる 2 個がある |
|---|
| 2^32 + 1 個のデータ | 32 ビットのハッシュ値 | ハッシュ値が同じ 2 個がある |
|---|
| フィボナッチ数の余りの、隣り合う 2 つの組 | m で割った余りの組 (m² 通り) | m² + 1 組までに同じ組が 2 回出て、そこから繰り返す (8-1 の周期) |
|---|
2 行目は、余りが同じ 2 個の差は 5 で割り切れるからです。3 行目は、x 座標どうし、y 座標どうしの偶奇がそろえば、足して 2 で割った中点も整数になるからです (8-2 の偶奇の考え方)。
箱を工夫する 3 つの例
箱の作り方が分かりにくい問題を 3 つ見ます。どれも下の 5 本目のコードで確かめます。
- 1 から 200 の整数から 101 個を選ぶと、一方が他方を割り切る 2 個が必ずある。どの数も「奇数 × 2 の何乗か」と 1 通りに書けるので、奇数の部分 (1、3、…、199 の 100 通り) を箱にする。101 個なら同じ箱の 2 個があり、奇数の部分が同じなので、2 の何乗かが小さい方が大きい方を割り切る
- n 個の整数が並んでいると、続いて並んだ何個か (1 個以上) の和が n の倍数になる所が必ずある。先頭からの和 (累積和) を 0 個目から n 個目まで n + 1 個作り、n で割った余り (n 通り) を箱にする。余りが同じ 2 つの累積和の差が、間の区間の和で、n の倍数になる
- 1 辺 2 の正方形の中に 5 個の点を置くと、距離が √2 以下の 2 点が必ずある。正方形を 1 辺 1 の小さな正方形 4 つに分けて箱にする。同じ小さな正方形の 2 点の距離は、対角線の √2 以下
箱は有限個でなければなりません。0 から 1 の実数 11 個を「同じ数」で分けようとすると箱は無数にあり、何も言えません。0 以上 0.1 未満、0.1 以上 0.2 未満、と幅で 10 個の箱に分けて初めて、差が 0.1 以下の 2 個があると言えます (1 は最後の箱に入れます)。
上界と下界
答えが多くてもいくつか (これ以上にはならない値) を上界、少なくともいくつか (これ以下にはならない値) を下界と呼びます。
鳩の巣原理は、下界を出す道具です。「15 個以上入る箱がある」は、一番多い箱の個数の下界が 15 という意味です。そして 15、15、14、14、14、14、14 と入れれば一番多い箱は 15 なので、15 はちょうどの答えでもあります。下界と、実際に作った例 (上界) が一致すれば、答えが決まります。
並べ替えに要る比べる回数の下界
2 つを比べて並べ替える方法では、n 個の並びは n! 通りあり、1 回比べると答えは 2 通りに分かれます。k 回比べて区別できるのは多くても 2^k 通りなので、どの並びでも正しく並べ替えるには、最悪の場合で 2^k ≥ n!、つまり k ≥ log2 (n!) 回が要ります。3 個なら 3! = 6 通りで、log2 6 ≈ 2.58 なので、最悪で 3 回は比べます。これは、比べ方をどう工夫しても下回れない下界です。
動かして確かめる
1 本目は、一般形を乱数で試します。100 個を 7 箱にでたらめに入れることを 1 万回繰り返し、一番多い箱が 15 個を下回ったことがあるかを数えます。15 にできる入れ方も作ります。
動かす 100 個を 7 箱に入れる
実行すると、次の通りに出ます
一番多い箱の最小 15
切り上げ 15
ならす 15 15 14 14 14 14 14
合計 100 最大 15
1 万回試しても、一番多い箱が 15 を下回ることはありませんでした。ならして入れると最大がちょうど 15 になるので、15 は下回れない数 (下界) であり、実際に取れる数でもあります。
2 本目は、余りと格子点の例です。でたらめな組を 1 万回作って言えることが外れないかを確かめ、物が 1 つ少ないときに外れる例も示します。
動かす 余りと格子点
実行すると、次の通りに出ます
6 個の整数 True
5 個の格子点 True
5 個の 0〜4 False
4 個の格子点 False
6 個の整数と 5 個の格子点では、1 万回とも言った通りの組がありました。物が 1 つ少ない 0〜4 の 5 個と、正方形の角の 4 点では、そういう組がありません。箱の数より 1 つ多いことが、ちょうど効いています。
3 本目は、答えの二分探索です。重さの決まった荷物を、並んだ順のまま D 日で運び切るとき、1 日に運べる重さ (容量) は最小でいくつ要るかを求めます。容量の下界は一番重い荷物 (それより小さいと載らない)、上界は全部の合計 (1 日で運べる) です。この範囲を半分ずつ絞ります。
動かす 容量を二分探索で絞る
実行すると、次の通りに出ます
範囲 9 から 47
二分探索 13
判定 5 回
全部試す 13
答えは 9 から 47 の間にあると先に決め、5 回の判定で 13 に絞れました。容量を 9 から 1 ずつ全部試した答えも 13 です。容量を大きくすると要る日数は減る一方なので、「D 日で足りるか」は、ある容量を境に「足りない」から「足りる」に 1 回だけ切り替わります。この切り替わる所を、二分探索で探しています (二分探索そのものは CS 2-1)。
4 本目は、並べ替えの下界です。log2 (n!) の切り上げを、マージソートで実際に比べた回数と並べます。
動かす 並べ替えの比べる回数の下界
実行すると、次の通りに出ます
3 下界 3 実際 3
10 下界 22 実際 23
1024 下界 8770 実際 8965
どの n でも、比べた回数は下界と同じか少し多い数でした。ただし下界は最悪の場合についての数なので、並びの運がよければ、下界より少なく済むことがあります。このマージソートに 1、2、3 と並んだ 3 個を渡すと、2 回で済みます。それでも、どんな並びでも正しく並べ替える方法は、最悪の並びでは下界の回数を下回れません。
5 本目は、上の 3 つの例を乱数で確かめます。1 つ少ないと外れる例も出します。
動かす 箱を工夫する 3 つの例
実行すると、次の通りに出ます
101 個 True
101〜200 False
[99, 45, 79, 92, 21, 27, 5]
区間 1 〜 4 和 315
9 個でいつもある True
5 点 True
角の 4 点 False
101 個を選ぶと 2000 回とも割り切る組があり、101 から 200 の 100 個ではありません (どの 2 個も、大きい方が小さい方の 2 倍に届かないからです)。7 個の数の並びでは、和が 7 の倍数になる区間が見つかりました。正方形の 5 点も 2000 回とも近い 2 点があり、角の 4 点では、どの 2 点も距離が 2 以上です。
上界と下界で外れる所
鳩の巣原理は「どこが」重なるかを教えない
鳩の巣原理で分かるのは、重なる箱が「ある」ことだけです。どの箱かは分かりません。重なっている 2 個を実際に見つけるには、箱ごとに数えるなどの処理が要ります。
物と箱を逆にする
鳩の巣原理が言えるのは、物の数が箱の数より多いときだけです。誕生日の問題で、人を箱、日付を物にすると、何も言えなくなります。「物 > 箱」の不等号の向きを、使う前に確かめます。
「必ず」と「たぶん」を混ぜる
367 人なら誕生日は必ず重なりますが、23 人で重なるのは確率約 0.507 です。ハッシュ値も、2^32 + 1 個なら必ず衝突しますが、約 7 万 7 千個で衝突の確率が半分を超えます (8-3)。設計では、必ず起こる限界 (鳩の巣) より、ずっと手前で起こる確率の方が先に問題になります。
判定が切り替わる所が 1 つでないと、二分探索できない
答えの二分探索は、判定 (D 日で足りるか) が、境目を 1 回だけ越える形のときに使えます。容量を増やすと日数が増えたり減ったりするような問題では、半分を捨てたときに答えも捨ててしまいます。判定が一方向に切り替わるかを、先に確かめます。
仕事とコンテストでどう使うか
上界と下界、鳩の巣原理が効く場面は、次の通りです。
- 答えの二分探索。「最小の容量」「最大の距離」のように答えそのものを探す問題で、下界と上界を決めて半分ずつ絞る。コーディングテストの定番
- 性能の予算。データが 10 万件なら 2 つの組は約 50 億組で、全部の組を調べる処理は重くなりやすい。書く前に手間の上界を数え、間に合わないなら方法を変える
- できないことの証明。並べ替えの下界のように、どう工夫しても下回れない数が分かれば、それ以上の工夫に時間を使わない
- ハッシュと ID。値の通り数より多いデータを入れれば必ず衝突するので、衝突したときの処理を最初から用意する
- 圧縮。n ビットの並びは 2^n 通りあるが、n − 1 ビット以下の並びは全部で 2^n − 1 通りしかない。だから、どんなデータも必ず短くする圧縮の方法は無い。圧縮で縮むのは、偏りのあるデータだけ
- 締め切りと見積もり。作業の量を「少なくとも」「多くとも」で挟むと、1 つの数で言うより外れにくい
よくある問い
鳩の巣原理とは何ですか
n 個の箱に n + 1 個以上の物を入れると、2 個以上入る箱が必ずあるという原理です。一般に、N 個を n 箱に入れると、N ÷ n を切り上げた数以上が入る箱があります。
鳩の巣原理の身近な例はありますか
367 人いれば誕生日が同じ 2 人が必ずいます。13 人いれば生まれ月が同じ 2 人が必ずいます。
靴下が 3 色あれば、暗い所で 4 本取り出すと、同じ色の 2 本が必ず入っています。
2 人以上の集まりで、各自が中の何人と握手したかを数えると、同じ人数と握手した 2 人が必ずいます (0 人と n − 1 人は同時に起こらないので、n 人に対して握手の人数の箱は実質 n − 1 個)。
6 人いれば、互いに知り合いの 3 人か、互いに知らない 3 人が必ずいることも、鳩の巣原理を使って示せます (ラムゼーの定理の小さな例)。
上界と下界とは何ですか
答えが多くてもいくつかを上界、少なくともいくつかを下界と呼びます。両方が一致すれば答えが決まり、一致しなくても、答えを探す範囲がそこまで絞れます。
鳩の巣原理はプログラミングのどこで使いますか
ハッシュの衝突が必ず起こる条件、繰り返す並びの周期 (8-1)、余りが同じ 2 つを探す問題、並べ替えのような下界の証明で使います。コーディングテストでは、「必ず存在する」ことを根拠に、探す範囲を決める問題が出ます。
確認クイズ
答えだと思う選択肢を押すと、その場で正誤と理由が開きます。3 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。
1 問目
50 人の生徒を 12 の班に分けます。必ず言えることはどれですか。
2 問目
1 から 100 の整数から、同じ数を選ばずに何個選べば、差が 10 の倍数になる 2 個が必ず含まれますか。
3 問目
答えの二分探索を使えるのは、どんな場合ですか。
説明課題
「367 人いれば誕生日が同じ 2 人が必ずいるのに、366 人では必ずとは言えない理由」を、鳩の巣原理の言葉 (物と箱) を使って 3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
模範解答
自分の説明を書いてから開いて、比べてください。
人を物、2 月 29 日を含む 366 通りの誕生日を箱と見ると、367 人を 366 箱に入れることになり、2 人以上入る箱が必ずある。どの箱にも 1 人以下なら、人数は多くても 366 人で、367 人に足りないからである。366 人なら、全員の誕生日を 1 日ずつずらした組み合わせが作れるので、必ず重なるとは言えない。
計算を始める前に「答えは少なくとも、多くとも」を言えると、無理な要求を早く見抜き、探す範囲を絞った速い処理を書けます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。
もっと深く
この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。
一次資料
どれも 2026年10月30日に開いて、題と中身を確かめました。
