部屋割論法を紹介していきます。
解説
「n(≧1)個の部屋にn+1人以上の客を入れようとすれば、
相部屋のところが必ずできる」
という事実を用いて証明する方法を部屋割論法という。
一般化された部屋割論法は、
「n(≧1)個の部屋に、kn+1(k≧1)人以上の客を入れようとすれば、
k+1人以上の客が入る部屋が必ずできる」
となる。
具体的な問題に、この論法を適用する場合、部屋と客に対応するものを明確にすることが大切である。また、この論法は、ある条件を満たす解を具体的に求めることなく、その存在を証明するときに有用である。
部屋割論法が適用できる例を紹介する。
(1)
13人が集まれば、少なくとも2人が同じ月に生まれている。
(2)
41個のリンゴを8個の箱に入れようとすると、少なくとも6個のリンゴが入っている箱ができる。
(3)
ある山に8001本の桜の木が生えている。1本の木に8000枚以上の葉がある桜の木はないとする。この山には、同じ枚数の葉をもつ桜の木が少なくとも2本ある。
(4)
20人の男女が丸いテーブルを囲んでいる。このうち男性が半分を超えている。
このとき、テーブルの対角線上に座る男性のペアが必ず存在する。
(5)
5人の中に友人数が同じ人が2人いる。