ディリクレの部屋割り論法を用いた問題で、
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で質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
∈と⊂の違いは何ですか?
-
{0,1}^3 の意味を教えてください
-
∈ と ⊂ のはっきりとした違い
-
空集合のべき集合
-
この中括弧の意味は・・・
-
Rの半開区間(0,1]と開区間(0,1)...
-
0以外の実数全体のどれかになる...
-
順列組合せについて
-
A∩BとAかつBは意味が違うのでし...
-
数学で、数字の上にある横線の意味
-
数研出版 メジアン 集合の問題
-
有限な区間ですか有界な区間ですか
-
線形代数
-
1から100までの自然数で、3,4,5...
-
空集合について〇か×か返答をお...
-
500以下の自然数を全体集合とし...
-
数学のノーベル賞
-
要素と、部分集合の違いを教え...
-
φと{φ}と{φ{φ}} 集合に...
-
加法・整数倍について閉じてい...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報