ディリクレの部屋割り論法

質問

ディリクレの部屋割り論法を用いた問題で、

1以上2N以下の自然数から(N+1)個を選ぶ。このとき、どのように選んでも、その中には一方を他方を割り切るようなペアが必ず存在することを示せ。

という問題があり、その証明が、↓↓

集合A(1)～A(N)を次のように定義する。

A(k)＝｛(2k－1)2m ｜ mは0以上の自然数｝
このとき、A(1)～A(N)は互いに共通要素をもたず、また2N以下の自然数はこのいずれかに属する。
よって、2N以下の自然数から(N+1)個を選ぶと、いずれかの集合からは少なくとも2要素選ばれる。
これを(2k－1)2m, (2k－1)2n（m＜n）とおくと、後者を前者で割れば2n-mと整数になる。
よって、題意は満たされた。

とあるのですが、

A(1)～A(N)は互いに共通要素をもたず、また2N以下の自然数はこのいずれかに属する。
よって、2N以下の自然数から(N+1)個を選ぶと、いずれかの集合からは少なくとも2要素選ばれる。

の部分ができないので、わかりやすく説明していただけませんか？

回答No.2

pori_boy · ベストアンサー

こんにちは

A(k) の定義式の2m はNo.1の方も言っているとおり
2のm乗と思いますので、そのつもりでの回答です。
＃以下、2^m と表記します

まず、A(1)～A(N)は互いに共通要素をもたず、
また2N以下の自然数はこのいずれかに属する、

という部分についてですが、ここは素因数分解
(のようなもの)を考えるのがよいと思います

ある自然数を（奇数）＊ 2^m という形に分解
するのは、素因数分解と同様に一意に決まります。
ここで、奇数という部分はもとの自然数より大きく
なることはありえないので今回の問題の範囲では
1以上2N-1以下ということになります。
よって、いずれかに属する／2つ以上の所に同時に
入ることはない（A(1)～A(N)は共通要素をもたない）
ということがいえます。

次に、2N以下の自然数から(N+1)個を選ぶと、
いずれかの集合からは少なくとも2要素選ばれる、
（ここが部屋割り論法と呼ばれる）部分ですが、

今、「部屋」がN部屋あり（A(1)～A(N)）、
部屋に入る「人」がN+1人（1から2Nまでの自然数の
うちのN+1個）いるという状況です。
もしも、どの部屋にも1人以下の人しか入れない
とすると、最大でN人の人が部屋に入ることができる、
つまり1人がどうしても余ってしまうことになります。
よって、N+1人の人がいる場合、どの部屋なのかは
わかりませんが、少なくとも一つの部屋には2人以上
の人が入っていることがわかります。

よって、2N以下の自然数から(N+1)個を選ぶと、
いずれかの集合(N種類ある)からは少なくとも
2要素が選ばれることになります。

お礼

わかりやすい説明本当にありがとうございました。やはり部屋割り論法は＋1がミソですね。

ほんとにわかりやすかったです。馬鹿な高校2年生ですが、また機会があればお願いします。

回答No.1

tasu9

こんにちは
Ｎに数を当てはめてみて、具体的に考えるとわかると思いますよ。
書かれている２ｍというのは、２のｍ乗のことですね。
集合が全部でＮ個あって、集合の数より１個多く自然数を選ぶので、ここが部屋割り論法を使うとこで、１つの集合から２数が選ばれることがいえます。
↓のページの下の方に、似たような問題の証明があります。

参考URL：

http://www.janis.or.jp/users/task/en2-3K.htm

お礼

＞書かれている２ｍというのは、２のｍ乗のことですね

そうですね。ありがとうございました。