部屋割り論法 （鳩の巣原理）| 少なくとも1つは
部屋割り論法 （もしくは鳩の巣原理）という誰もが納得しやすい命題を拠り所にして、条件を満たすものが少なくとも一つ存在するということを示す問題が高校の数学で扱われるときがあります。
難しい大学受験の問題だと、問題文の内容自体が複雑だったり、部屋割り論法以外の論点が難しいこともあるのですが、部屋割り論法自体は親しみやすい内容です。
表紙の図で述べているように、異なる 3 部屋に、4 人を配置しようとすると、2 人以上の人が入っている部屋が、少なくとも 1 部屋は存在することになります。
これを n を用いて一般的に、
n 室の部屋に (n+1) 人を配置しようとすると、2 人以上の人が入っている部屋が、少なくとも 1 室は存在するということになります。
これを部屋割り論法（鳩の巣原理）といいます。
それでは、シンプルな整数（自然数）を用いた例を通して、部屋割り論法を実際に使って論証を進める練習問題を解説します。
部屋割り論法 :必然的にあふれる数
＜部屋割り論法の証明＞
n 室に (n+1) 人を配置したとき、どの部屋も 1 人以下の人しか入っていなかったと仮定します。
すると、n 室の部屋に配置されている人数が、n 人以下ということになってしまいます。
これは、(n+1) 人を配置したことに矛盾します。
よって、背理法から、「n 室の部屋に (n+1) 人を配置しようとすると、2 人以上の人が入っている部屋が、少なくとも 1 室は存在する」ということになります。
では、具体的な例を使って、部屋割り論法を使う練習をします。
【部屋割り論法１】
1 以上 30 以下の整数から、相異なる整数を 16 個選びます。
このとき、選んだ 16 個の整数には、必ず 16 以上の整数が含まれます。
＜証明＞
1 以上 15 以下の整数の個数は 15 個です。
そのため、部屋割り論法から、16 個の選ばれた相異なる整数の中には、少なくとも一つは 16 以上の整数が存在することになります。【証明完了】
15 個までは、16 以上であるという条件に該当しないように選ぶことができます。しかし、必然的にあふれた 1 個は、16 以上 30 以下の整数となってしまうというわけです。
集合を使うと、次のように考察をすることができます。
1 以上 15 以下の整数全体を A とし、16 以上 30 以下の整数全体を B とします。
すると、A ∩ B は空集合で、
A ∪ B は 1 以上 30 以下の整数全体となります。
個数定理より、
n(A ∪ B) = n(A)+n(B)－0
= n(A)+n(B) = 15+15 = 30 となっています。
今、示した内容の表裏一体となる命題も証明できます。
表裏一体の事柄をどちらも証明
【部屋割り論法２】
1 以上 30 以下の整数から、相異なる整数を 16 個選びます。
このとき、選んだ 16 個の整数には、必ず 15 以上の整数が含まれます。
＜証明＞
16 以上 30 以下の整数の個数は 15 個です。
そのため、部屋割り論法より、
選んだ 16 個の中に、少なくとも一つは 15 以下の整数が含まれています。【証明完了】
先ほど示した内容と表裏一体となる内容も示しました。
これら二つの内容を用いて、より複雑な内容を考察します。
部屋割り論法 :複雑になった問題
数学では、一つの論理的な構造の中に、他の論理構造が入っているときがあります。これが、ネスト構造です。
数学のみならず、プログラミングなどを学習し始めたときにも出てくるので、一つの構造の中に他の構造が入っているということへの意識をしておくと良いかと思います。
ネスト構造を使うと、より複雑な構造になることがあります。
数学の問題でも、このネスト構造を使って、より複雑な問題（命題）が作られるときがあります。
先ほどの算数の内容だった【部屋割り論法１と２】の内容を、ネスト構造の観点から、より複雑にしてみます。
【練習問題】
1 以上 30 以下の整数の中から相異なる整数を 16 個選びます。
これら 16 個から相異なる整数を 2 個選んで和を計算します。
このとき、和が 31 となる異なる整数が二つ、選んだ 16 個の整数の中に必ず存在することを証明してください。
＜証明＞
1 以上 30 以下の整数から、異なる二つの整数を選び、和が 31 となるのは、次の 30 通りの組に含まれている整数を使うしか可能性がありません。
(1, 30), (2, 29), (3, 28),
… , (13, 18), (14, 17), (15, 16)
もしくは、これらの組の x 座標と y 座標を逆にした組である
(16, 15), (17, 14), (18, 13),
… , (28, 3), (29, 2), (30, 1)
・・・★
これら★の 30 通りの各組について、
x 座標と y 座標の数字の和が 31 です。
加法の交換法則から、x 座標と y 座標を逆にしたものを含めて、和が 31 となる全ての可能性です。
加法の交換法則から、各組の x 座標の値が y 座標の値よりも小さい 15 組だけを考えることにします。
したがって、どのように相異なる 16 個の整数を選んだとしても、その 16 個から異なる二つの整数を適切に選ぶと、★の組の二つの整数のペヤができるということを示せば良いことになります。
背理法で示します。
「1 以上 30 以下の整数の中から相異なる整数を 16 個選んだもので、その 16 個から異なる二つをどのように選んでも和が 31 とならない」と仮定します。
この 16 個を x1, … , x16 と置きます。
これら x1, … , x16 の 16 個から、どのように異なる二つを選んでも和が 31 ではないということです。
この状態から矛盾を導きます。
x1, … , x16 の 16 個から、
a < b となるように二つの整数 a と b をどのように選んでも、和が 31 ではないということです。
ここで、【部屋割り論法２】から、
x1, … , x16 の中に、15 以下の整数が含まれます。
その 15 以下の自然数を a とします。
x1, … , x16 という相異なる整数が、すべて 15 以下の自然数とすると、【部屋割り論法１】に反します。
そのため、x1, … , x16 という相異なる整数の中に少なくとも一つは 16 以上 30 以下の整数が存在します。
ここで、
x1, … , x16 を、
(1, 30), (2, 29), (3, 28),
… , (13, 18), (14, 17), (15, 16) の同じ数字がある所に配置することを考えます。
i ≠ k で (xi, xk) と、一つの組の x 座標と y 座標の両方に配置されると、
xi+xk = 31 ということになります。
x1, … , x16 が片方の座標にしか配置されない組は、最大で 15 個までです。
16 個の x1, … , x16 を配置するため、
i ≠ k で (xi, xk) と同じ組に配置されることになります。
（ここで部屋割り論法を使いました。）
★の組の x 座標と y 座標の和は、どれも 31 だったので、
a+b = 31 ということになってしまいます。
これは、「a < b となるように二つの整数 a と b をどのように選んでも、和が 31 ではない」ということに矛盾です。
「1 以上 30 以下の整数の中から相異なる整数を 16 個選んだもので、その 16 個から異なる二つをどのように選んでも和が 31 とならない」と仮定すると矛盾が生じました。
よって、背理法から、
「どのように 1 以上 30 以下の整数の中から相異なる整数を 16 個選んだとしても、その 16 個から異なる二つを適切に選ぶと、和が 31 となる」ということになります。【証明完了】
証明ができたことで、論理構造を振り返ってみます。
論理構造の振り返り
この練習問題では、1 以上 30 以下の整数から 16 個の相異なる整数を選び、その 16 個の整数から、
(1, 30), (2, 29), (3, 28),
… , (13, 18), (14, 17), (15, 16) のいずれかになるように (a, b) を配置するということを考えました。
大きな構造が、(a, b) への整数の配置です。
その中で、【部屋割り論法２】の構造から、x 座標の値が 15 以下の自然数となるものが少なくとも一つは存在することが明らかになりました。
そして、【部屋割り論法１】から、y 座標の値が 16 以上 30 以下の整数となるものが少なくとも一つは存在するということでした。
大きな論理構造の中に、他の論理構造が入り込んで下支えをしている状態です。
つまり、ネスト構造によって、論理が複雑化した内容となっていたということです。
厳密な論理を考えると、言い方や記号が複雑になりますが、簡単に先ほどの証明をまとめておきます。
1 以上 30 以下の整数の中から、
x1, … , x16 という相異なる整数を 16 個選びます。
すると、必ず x1, … , x16 から異なる二つの整数 a と b を選べて、
1 ≦ a ≦ 15, 16 ≦ b ≦ 30 となるということです。
つまり、選んだ 16 個が全て 15 以下や、選んだ 16 個がすべて 16 以上ということが発生しない状態になっているので、上のような議論が進行できました。
論法１と論法２の表裏一体を突いた (□, △) への整数の配置問題でした。
16 ≦ x ≦ 30 の範囲の整数を △ へ配置。
1 ≦ x ≦ 15 の範囲からあふれた整数を □ へ配置。
あふれる根拠は、どちらも部屋割り論法でした。
そうすると、x1, … , x16 という 16 個の相異なる整数を、
(1, 30), (2, 29), (3, 28),
… , (13, 18), (14, 17), (15, 16) の 15 個の組のどちらかの座標に、配置するということを実行できます。
その結果、15 個しか組がないため、
少なくとも一つの組は、
(xi, xk) と、どちらの座標にも整数が配置されることになったわけです。
x1 が使われている組 (x1, *),
x2 は (x1, *) ではない組 (*’, x2) に配置されているというように、なかなか一つの組の両方の座標に配置されていなかったとしても、組は全部で 15 個です。
16 個の x1, … , x16 を配置すると、少なくとも一つの組には、どちらの座標にも配置されるということが起きてしまいます。
そうすると、(xi, xk) が、x 座標と y 座標の和が 31 である 15 個の組のどれかなので、求める異なる二つの整数というわけです。
厳密な証明
(xi, xk) と、少なくとも一つの組は、どちらの座標にも整数が配置されなければならないということを論理的に示しておきます。
部屋割り論法の構造に気づきにくいかと思いますので、明確に背理法で証明しておきます。
x1, … , x16 という 30 以下の相異なる 16 個の自然数が、
15 個の組に、両方の座標に現れる組が一つもないように配置できたと仮定します。
xt が配置された組を At と表すことにします。
（t = 1, … , 16 です。）
すると、両方の座標に現れる組が一つもないということから、
x1, … , x15 が配置された A1 から A15 の組は、それぞれ片方の座標にしか整数が配置されていません。
また、A1 から A15 のすべての座標には、1 から 30 までの整数があります。
x16 は、1 以上 30 以下の整数なので、
A1 から A15 の組のいずれかに配置されます。
これは、15 個の組に、両方の座標に現れる組が一つもないように配置できたという仮定に矛盾です。
よって、背理法から、
x1, … , x16 から選んだ整数を両方の座標に配置した組が、少なくとも一つ存在するということになります。
これで、厳密な証明が完了しました。
数学では、一つの構造の中に他の構造が入り込むというネスト構造を考えることがあります。
この証明ですが、30 か所に整数を配置するので、部屋割り論法の構造に気がつきにくい内容です。
背理法で起こり得ない状況を考えると、部屋割り論法の使える状況になっていることが明確になります。
ネスト構造は、様々な場面で出てきます。この練習問題は、説明をしだすと長くなりましたが、もっと単純なネスト構造の例を中学の数学から知っています。
分数という構造の中に、ルートという構造が入るということは、その例です。
他にも高校の数学IIの計算などで出てくる連分数も、分数という構造の中に分数が入っています。
このようなことを意識しておくと、数学のtexの数式入力に役だったりもします。
最後に、整数の内容との関連問題を扱います。
部屋割り論法 :整数との関連問題
【余りに関する証明問題】
整数 a, b, c, d を 3 で割った余りを、それぞれ p, q, r, s とします。
このとき、a, b, c, d から 2 個を選ぶ組合せの中で、少なくとも一つの組は、選んだ二つの整数の差が 3 の倍数となることを証明してください。
＜証明＞
整数を 3 で割ったときの余りは、0, 1, 2 の 3 種類しかありません。
そのため、部屋割り論法から、余りである p, q, r, s の中には重複している余りが存在することになります。
そこで、a, b, c, d の中から 3 で割ったときの余りが等しくなる二つの整数を選びます。
その選んだ二つの整数を x, y と置きます。
x と y を 3 で割ったときの余りが等しいので、その余りを r とします。（r は、0, 1, 2 のいずれかです。）
除法の原理（定理）より、ある整数 k, h を用いて、
x = 3k+r, y = 3h+r と表すことができます。
※ ユークリッド整域という記事で、除法の原理という算数で学習する検算の証明を厳密に証明しています。
この x と y で差を計算すると、
x－y = (3k+r)－(3h+r)
= 3(k－h) となります。
k－h は整数なので、
3(k－h) は 3 の倍数です。
すなわち、x－y という選んだ二つの整数 x と y の差は、3 の倍数です。【証明完了】
余りについての整数問題で、部屋割り論法が絡むときがあります。
「n 人を n 個の部屋に入れるとき、どの部屋にも 1 人以上は入れないという条件のもとでは、n 人は 1 部屋に 1 人ずつ配置されることになる」というタイプの部屋割り論法も使われます。
抽象的な証明で、よく使う手を紹介します。
相異なるk個の余り
自然数 k で割ったときの余りで、
r1, r2, … , rk という k 個の非負整数があったとします。
そして、これら k 個の余りは、すべて相異なるという状況だったとします。
このとき、部屋割り論法から、
r1, r2, … , rk はそれぞれ、
0, 1, 2, … k－1 という k 個の余りに配置されることになります。
自然数 k で割ったときの余りは、0, 1, 2, … k－1 という k 個です。
これらを k 個の部屋だと思います。
r1, r2, … , rk を k で割ってできた k 個の相異なる余りを k 人の人だと考えて、部屋割り論法を使います。
すると、n 人は 1 部屋に 1 人ずつ配置されるということです。
この内容は、フェルマーの小定理の証明で使うことができます。
※ リンク先の記事は、大学で扱う環論の入門内容となっています。
小さい整数を使って、具体的に見てみます。
5, 6, 7 を k = 3 で割ったときの余りを
それぞれ r(5), r(6), r(7) と置きます。
一般に連続する 3 個の整数を 3 で割ったときの余りは、相異なります。
そのため、r(5), r(6), r(7) は、相異なる 3 で割ったときの余りです。
3 で割ったときの余りは、0, 1, 2 の 3 種類しかありません。
r(5), r(6), r(7) を、
部屋0、部屋1, 部屋2 に配置することを考えます。
部屋割り論法より、
r(5), r(6), r(7) は重複することなく相異なる部屋に配置されます。
実際に計算して確かめてみます。
5÷3, 6÷3, 7÷3 の余りは、それぞれ 2, 0, 1 なので、
r(5) = 2, r(6) = 0,
r(7) = 1 となっています。
r(5) は部屋2 に、r(6) は部屋0 に、r(7) は部屋1 に配置されています。
確かに重複なく、どの部屋にも 1 人ずつ入っています。
それでは、これで今回の記事を終了します。
読んで頂き、ありがとうございました。