鳩の巣原理

質問

部屋割り論法（鳩の巣原理）とはどういう原理で、どのような問題のときに使いますか？

回答No.3

51232

鳩ノ巣原理とは、
n＞mのとき
n羽の鳩をm個の箱に入れると
鳩が二羽以上入る箱が必ず存在しますよねということです。
分かりやすく言うと､
パーティーに参加者が366人いて
全員誕生日が違います。そこに
もう一人来たら、367人で絶対誕生日同じ人がいますよね。
ということです。
この原理を理解することで
任意に与えられた相異なる 5つの整数 a,b,c,d,e
に対して，その中から適当に 2
つの整数を選んで，その差を 4
の倍数にすることができる｡これを示せ。
というような問題も解くことができます｡
まず、整数を4で割るとき、余りは0.1.2.3があります。
そして整数は、5つあります。
なので､同じ余りの出るものは確実にあり､差は4の倍数であるという論理展開ができます。
小六なので間違っていたらすいません｡

回答No.2

masudaya

巣箱より巣箱にはいっている鳩の数が多ければ，どれかの箱は鳩が2匹いるという原理。
問題は，様々なものがある。
(1)3次元空間に格子点を9つ取ると必ず中点も格子点となる2組の点が見つかる。というわかりやすいものから，(2)正三角形 ABCにおいて，3つの辺上の点全体の集合を EE とおく。 EE を2つに分割するとき，どちらか一方は直角三角形をなす3点を含むことを示せ。という数学オリンピック予選に出題される問題。(3)100万人の都市には必ず髪の毛の本数が同じ人がいる。という面白い問題までいろいろあります。
鳩ノ巣原理は，存在を証明する問題で当たり前だけどどう証明するのかわからないときなどに使うことを試みても良いと思います。
せっかくですので，各問題の回答を

(1)格子点なので(偶/奇，偶/奇，偶/奇)となっている。(偶：偶数，奇：奇数)中点がまた格子点になるには，各成分の偶奇が一致すればよく，(偶/奇，偶/奇，偶/奇)の組み合わせは2^3=8通りなので9点取れば必ず各成分の偶奇が一致するものがあり，その2点を取れば中点は格子点になる。
(2)はご自身でお調べください。(https://manabitimes.jp/math/692)
(3)は，髪の毛の本数はおおよそ最大30万本といわれている。このため100万人が0~30万のどれかに割り振られるので，髪の毛の本数の本数の同じ人がいる。

回答No.1

asuncion

n個の部屋に(n+1)個のものを入れようとすると、
少なくとも1個の部屋には2個以上が入る。

例)
1辺の長さが1の正六角形がある。
ここに7個の点を置くとすると、
点どうしの距離が1以下（あるいは未満かも）になる
組合せが1つ以上存在することを証明せよ。