鳩の巣原理

質問

100以下の自然数を11個選ぶとき、その差が9以下の二つの数があることを示せ

という問題の正解がわかりません。
本の解説には、
A1={1,2,•••10},A2={11,12,•••,20},•••A10={91,92,•••100}
のように10個の互いに素な部分集合に分割し、鳩の巣原理を適用する、と書いてありましたが、この解説から正解を導けません。
どなたか正解を教えてください。

回答No.1

asuncion · ベストアンサー

A1～A10の10個の部分集合から
自然数を11個選ぶので、いずれかの部分集合からは
必ず2個以上選ぶことになる（鳩の巣原理）。
このとき、自然数を1つも選ばない部分集合があってもいっこうにかまわない。
要素を2個以上選んだ部分集合において、
その最小値と最大値の差は、たかだか9である。
よって、題意は示された。

回答No.6

shuu_01

asuncionさん、鳩の巣原理の説明ありがとうございます

Wikipedia 鳩の巣原理
http://ja.wikipedia.org/wiki/鳩の巣原理

でわかっちゃいました

今回の問題に当てはめると、100以下の自然数を

A1={1,2,•••10},A2={11,12,•••,20},•••A10={91,92,•••100}

10個の箱に入れます

100以下の自然数を 11個 選ぶ時、どうしてもどれか
１つの箱から ２個選ばざるおえません

１つの箱のその自然数も差は ９以下ですので、
差が９以下の２つの数があることになります

回答No.5

asuncion

＞#3さん
鳩の巣原理はけっこう有名な考え方です。
ぜひお調べになってみてください。
もちろん、背理法で解いてもかまわないと思います。

回答No.4

asuncion

10個の部分集合から11個の自然数を選ぶ
=
旅館に10部屋あって、11人が泊まる
=
巣が10個あって、11羽の鳩を住まわせる

どれも、少なくとも1つ以上は相部屋になりますよね。
要素を選ばない部分集合や
だれも泊まらない部屋や
1羽も住まない巣が
あったとしても。

回答No.3

shuu_01

鳩の巣原理ってなんなの？

僕だと、

その差が9以下の二つの数がないとすると、

１番小さな数と２番目に小さな数の差は 10以上、
２番目に小さな数と３番目に小さな数の差も 10以上
ですので、１番目と　３番目の差は 20以上です

同様に、４番目以後も
１番目と　４番目の差は 30以上、
１番目と　５番目の差は 40以上、
１番目と　６番目の差は 50以上、
１番目と　７番目の差は 60以上、
１番目と　８番目の差は 70以上、
１番目と　９番目の差は 80以上、
１番目と１０番目の差は 90以上、
１番目と１１番目の差は 100以上、

となり、１番目に１番 小さな自然数 １ を選んでも、
１番目と１１番目の差 100以上ですので、
１１番目は 101以上となり、100 以下という条件を
満たせません

したがって、その差が9以下の二つの数があります

と背理法で示します

回答No.2

yyssaa

＞A1～A10のそれぞれから1数字計10数字を選べば
それぞれの数字の差は10以上になるが、11個目は
A1～A10のいずれかから選ぶことになるので、
例えばA10から選べばA10にはその差が9以下の二つ
の数があることになり、100以下の自然数を11個選ぶ
と、その差が9以下の数が最低二つは含まれる。