質問: ディリクレの部屋割り論法 ディリクレの部屋割り論法を用いた問題で、 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要素選ばれる。 の部分ができないので、わかりやすく説明していただけませんか?
回答: こんにちは nに数を当てはめてみて、具体的に考えるとわかると思いますよ。 書かれている2mというのは、2のm乗のことですね。 集合が全部でn個あって、集合の数より1個多く自然数を選ぶので、ここが部屋割り論法を使うとこで、1つの集合から2数が選ばれることがいえます。 ↓のページの下の方に、似たような問題の証明があります。 参考url:http://www.janis.or.jp/users/task/en2-3k.htm