ディリクレの部屋割り論法を用いた問題で、
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ベストアンサー
- 回答日時:
こんにちは
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
- 回答日時:
こんにちは
Nに数を当てはめてみて、具体的に考えるとわかると思いますよ。
書かれている2mというのは、2のm乗のことですね。
集合が全部でN個あって、集合の数より1個多く自然数を選ぶので、ここが部屋割り論法を使うとこで、1つの集合から2数が選ばれることがいえます。
↓のページの下の方に、似たような問題の証明があります。
参考URL:http://www.janis.or.jp/users/task/en2-3K.htm
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
∈と⊂の違いは何ですか?
-
【 数I 集合の要素の個数 】 問...
-
有理数÷有理数は絶対有理数なん...
-
数学で、数字の上にある横線の意味
-
部分が全体に等しいのが無限で...
-
6以下の自然数全体の集合の要素...
-
集合について。
-
集合論のカップ(∪)と普遍集合...
-
集合の基数について
-
ボレル集合体に含まれないRの部...
-
1から100までの自然数で、3,4,5...
-
R\\{0} って、0を除く実数って...
-
部分集合になる、ならない
-
数学の解き方を教えてください...
-
同値関係の問題です。
-
巾集合
-
高校数学 集合についての質問で...
-
問題の解説と回答をお願いしま...
-
高校数学 集合Xの要素の個数を ...
-
上限でないことを示したいです...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報