部屋割り論法が未だに理解できないんだが

難関大学目指してるのに部屋割り論法が理解できないし、実行しようと考えられん

ハッシュテーブルの衝突

代表元と同値類割り。

ヒルベルトのホテルに非加算無限の団体客がやって来ました。
「おいこら、さっさと全員収容しろ！」
「ただいまお一人ずつお部屋を空けております」
「ええい、日が暮れるから相部屋で構わん！」

非可算無限が個々として実体を持つって変な感じがする

というのも非可算無限すべてに名前を付けようとしても必ず計算不可能なものが入ってくるから超越的に存在は言えてても名前は付けられないような
そんなこと言い出したら可算無限でも実はマズいのかな

「実体」ということなら、可算無限個でも存在しないというか、
存在してるとしても確認しようがないでしょ。

弱鳩の巣原理という概念もあるくらいだから違和感を覚えるのは数学的センスがあるよ

今日はいい天気、風が強いけど

枕投げでもするか

余ったやつがどこかの部屋に重複するやつと
重複しないように部屋に入れるとどの部屋にも誰かいるみたいなやつ
あるよな
どっちが部屋割り論法なられ？

コンパクトなら高々有限数枚の開被服で覆い切れる。

コンパクトなら高々有限数枚の開被覆で覆い切れる。

よくない言い方だ

数学に「鳩の巣」のような言葉はいかがなものか

これは証明できるの
公理なの

>>15
部屋の数に関して数学的帰納法を使えば証明出来るだろ。

集合XからYへの写像は、|X|>|Y|であれば単射ではない。

有限集合XとYの要素の数がそれぞれｍとｎとする。
そうしてｍ＞ｎとする。
X要素に適当に番号を振ってx_1, x_2, ..., x_m とする。
そうしてXからYへの単射関数ｆが存在すると仮定して、それにより
f(x_1) = y_1, f(x_2)=y_2, ... , f(x_m)=y_mとする。
ｆの単射性から y_1, y_2, ... の列には重複はないことが示せる。
よってYは　すくなくとも 　y_1, y_2, ..., y_m というｍ個の相異なる要素を
含むことになるが、Yの要素数はｎであってｍ＞ｎなのであるから矛盾が生じる。
よってXからYへの単射関数は存在しえない。

単射でなければ、あるYの元ｙが存在して、そのｙに対して
x_1 ≠ｘ_2でかつｆ（ｘ_1）＝f(x_2)=ｙとなるようなx_1とx_2あ
Xの中に存在する。つまり巣穴ｙに二匹のハトｘ_1とｘ_2が入って居る
ようなｙが必ずある。

男子がｍ人、女子がｎ人いて、
男子は必ずどれかの女子と交際をするものとする。
ｍ＞ｎであれば、女子の中に二人以上の男子と交際をする者が存在する。

「ｍ本の棒をｎ個の穴に差しこむ場合に、
m>nであるならば、2本以上の棒が
差しこまれた穴が存在する。」
というだけのこと。
棒がハトであっても良い。
鳩ノ巣原理。Pigon Hole　Principle　（PHP)

N人の学生がM社に対して就活する。
学生が全員内定を得ているとき、N>Mなら
二社以上から内定を得た学生が必ず存在する。

宿泊費が2万円以上なら個室、1万円以下は相部屋。。。。

有限集合AとBがあって、
Aの要素数はｍ、Bの要素数はｎとする。そのとき
以下の各問いに答えよ。（配点各5点）

問1）AからBへの単射となる写像の数はどれだけあるか。
問2）AからBへの全射となる写像の数はどれだけあるか。
問3）AからBへの全単射となる写像の数はどれだけあるか。

問4）A上の写像で不動点を持たないものの数はどれだけか。

鳩ノ巣原理の定式化には全写バージョンもあるらしい

大数の本によると

部屋割論法は「A(集合)の中に少なくとも1つB(という性質を持つ元)が存在する」という問題の時に使える。
「n+1人をn部屋に入れると(n個のグループに分割すると)少なくとも一部屋(1グループ)には2人以上が入る」というのが原理である。

部屋割論法は鳩の巣原理、ディリクレの部屋割論法、引き出し論法ともいう。

暗記用基本例題1

1, 2, 3,…,, 2nの2n個の整数の中からn+1個選ぶと、その中には連続する整数が必ず含まれることを示せ。

(12)、(34)、…、(2n-1, 2n)
のn個のグループに分ける。
連続しないように取る時の必要条件としてn個のグループから各1つずつ選ぶ。最後の1個を選ぶ時には2個揃っているグループは無いので題意が成り立つ。

連続しないように取る取り方を構成してみる。
1を取り、2は取らず、3を取り…とやって行くと奇数だけ取ることになる。最後(2n-1)までとっても全部でn個しか取れない(偶数だけでも同様)。すなわちn+1個とると偶数が1つ交じることになり前後の奇数は取っているので連続する。これ以外の取り方は不可能である。

暗記用基本例題2

例題1において
2n→4n、n+1→2n+1、連続→差が2とする。

同様に2個ずつ2n個のグループに分ける。1つのグループから2個取るとその前または後のグループからどちらをとっても差が2になってしまう。従ってあるグループから2個取ると別のグループが2個とも残ることになる。すると多くても2n個しか取れない。最後の1個を取るとそのグループは2個取られたことになり題意が成り立つことが示された。

(1,3)(2,4)(5,7)(6,8)のようにグループを作ると2n個のグループが出来る。1つのグループから2個取ると差が2になってしまうので各グループから1個ずつ取ることが必要。これで2n個取れるがその後の1個はあるグループの2個めを取るしかない。

暗記用基本例題3

一辺の長さが2の正三角形の内部(周は含まない)に5個の点を取ると、その5点のうちの2点間の距離のうちに1より小なるものが存在する。


一辺が1の正三角形4個に分割すると5点のうちの少なくとも2点はそれらの正三角形のうちの1個の内
内部に入る。それは距離1未満である。
正三角形の周及び内部の2点間の最大距離は頂点同士で1となる。それ以外は全て1未満である。

暗記用基本例題4

5人集まると知り合いの人数が同じ2人の組が必ず存在する。

5人の人の中での知り合いは必要条件として0、1、2、3、4であり同数が存在しないと仮定するとこのパターンしかない。知り合い0人と知り合い4人は矛盾する。
0~3の4個の部屋に5人入るか、
1~4の4個の部屋に5人入るかしかない。

以上の4問で部屋割論法の基本はバッチリだ。
ポイントは
「部屋の個数」と「部屋の性質」の2点だけ。

例題1は差が1の2個ずつのn個の部屋12, 34, 56, …, (2n-1, 2n)
例題2は差が2の2個ずつの2n個の部屋13, 24, 57, 68, (4n-2, 4n)
例題3は一辺1の4個の正三角形の部屋
例題4は0~3の4個または1~4の4個しか作れず0~4の5個は不可能。

おわり