- ベストアンサー
ディリクレの部屋割り論法
ディリクレの部屋割り論法を用いた問題で、 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要素選ばれる。 の部分ができないので、わかりやすく説明していただけませんか？
- Acer2
- お礼率62% (132/211)
- 数学・算数
- 回答数2
- ありがとう数5
- みんなの回答 （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)
- tasu9
- ベストアンサー率42% (9/21)
こんにちは Ｎに数を当てはめてみて、具体的に考えるとわかると思いますよ。 書かれている２ｍというのは、２のｍ乗のことですね。 集合が全部でＮ個あって、集合の数より１個多く自然数を選ぶので、ここが部屋割り論法を使うとこで、１つの集合から２数が選ばれることがいえます。 ↓のページの下の方に、似たような問題の証明があります。
お礼
＞書かれている２ｍというのは、２のｍ乗のことですね そうですね。ありがとうございました。
関連するQ&A
- 部屋割り論法の問題の解き方
部屋割り論法を利用する問題の解き方の方針などを教えてください。 ⑴ 1 辺の長さが1 の正六角形の周および内部に7 個の点をとったとき，そのうちの2 点で，距離が1 以下となるようなものが少なくとも 1 組存在することを示せ。 ⑵ n を自然数とするとき，相異なるn + 1 個の整数の中に，その差が n の倍数である2 数が必ず存在することを示せ。 ⑶ 100 以下の自然数から51 個を選ぶと，必ず和が101 になる2 数 が存在することを示せ。 ⑷ 100 以下の自然数から21 個を選ぶと，この中にa + b = c + d をみたす4 数a，b，c，d が必ず存在することを示せ。
- ベストアンサー
- 数学・算数
- 論理的な誤りがあるなら指摘して
いまnを3以上の自然数、mを自然数とする。 f(n)を「nと互いに素でnよりも小さい自然数の個数」と定義します。 f(6)なら、1、2、3、4、5のなかで互いに素なのは、1、2、4、5の4個よりf(6) = 4です。 さてm<nのときにmとnが互いに素なら、n-mとnも互いに素です（これは証明されたとします） このときf(n)が偶数であることを証明します。 ------------ k∈Nとして n = 2k＋1のとき ｛１、２・・k｝の集合をA ｛k+１、k+２・・2k｝の集合をBとする。集合Aでnと互いに素な自然数をrとすると、 1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+1≦ n-r ≦ 2kより互いに素なn-rは必ず集合Bに存在するので、集合Aの互いに素な個数とBの個数は同数なので、f(n)は偶数になる n = 2k＋2のとき ｛１、２・・k｝の集合をA ｛k+2、k+２・・2k+1｝の集合をBとする。 ｛k+1｝の集合をCとする 集合Cにおいて、n =2(k+1)とk+1は因数としてk+1(≧2)を持つので互いに素ではないのは 明らか。 集合Aでnと互いに素な自然数をrとすると、 1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+2≦ n-r ≦ 2k+1より互いに素なn-rは必ず集合Bに存在し、さきほどと同じ議論になるので、f(n)は偶数になる qed で何か誤りがあるかね？
- 締切済み
- 数学・算数
- Ｑ．Xを自然数全体の集合Nの部分集合とするとき、｜X｜＞アレフゼロを証
Ｑ．Xを自然数全体の集合Nの部分集合とするとき、｜X｜＞アレフゼロを証明せよ。 以下、ネットでのどなたかの回答を参考に、私なりにテキストを読み返すなどして解釈して、作成しました。 テスト問題としての解答として、 「修正および補足」などをお願いします。 Ａ． |Ｘ|=|Ｎ|と仮定すると、ＮからＸへの全単射ｆが存在する。 ∀n∈N ⇒ f(n)=M, ∃M∈X ∀M∈X ⇒ f(n)=M, ∃n∈N つまり 1 ←→ M1 2 ←→ M2 ・ ・ n ←→ Mn ・ ・ このとき、左右の対応関係について、属するか属さないかを分類でき、 N∈Mn または n?Mnとなる。 次に集合M'を以下のように定義する。 (1) n∈Mnのときnを要素としない。 (2) n?Mnのときnを要素とする。 この集合は一意に決まり、また自然数だけを要素に持つ集合となり、明らかに自然数の部分集合を意味する。 つまりM'∈Xであるが、このM'は定義により、上の対応関係からは外れている。 これはNとXとが全単射できたという仮定に矛盾する。 ｜X｜≠アレフゼロ また、写像ｇ：Ｎ→Ｘをｇｎ＝{ｎ}とすると、これは単射であるから ｜Ｎ｜＝アレフゼロ≦｜X｜ 以上より、アレフゼロ＜｜X｜
- ベストアンサー
- 数学・算数
- 集合
こんにちは. 集合を独学で勉強しています高校1年生です, わからない問題があります. よろしくお願いいたします. 次のうち正しいものを選びなさい. (1) Ａ＝｛ｘ2｜ｘは自然数｝ を，要素を書き並べて表わすと Ａ＝｛1,2,3,4,5,....｝ Ａ＝｛2,4,6,8,10,...｝ Ａ＝｛1,4,9,16,.....｝ Ａ＝｛1,3,5,7,9,....｝ Ａ＝｛0,1,4,9,16,...｝ これは3つめが正解だとわかりました. (2)Ｎを自然数全体の集合とするとき Ａ＝｛ｎ｜ｎ＝ｍ(ｍ－１)，ｍ∈Ｎ｝ を，要素を書き並べて表わすと Ａ＝｛0,3,8,15,....｝ Ａ＝｛0,1,2,3,.....｝ Ａ＝｛1,2,3,4,.....｝ Ａ＝｛2,6,12,20,...｝ Ａ＝｛0,2,6,12,....} これは私は４つめが正解だと思いましたが違いました. 正解は5つめです. なぜ5つめが正解なのでしょうか？ 自然数は0も含まれるのでしょうか？ (1)では0が含まれていないのに(2)では0が含まれているので混乱です. どうぞ,ご教授お願いいたします.
- ベストアンサー
- 数学・算数
- 青チャートp424の149の数列の問題です
a_{n}=8n-2 , b_{n}=6n＋2 に共通して現れる数を小さい順に並べた数列c_{n}を求めよ 解答；a_{l}=b_{m}とすると、8(n-2)＋14=6(n-2)＋14から 4(l-2)=3(m-2), l≧2, m≧2 4と3は互いに素より、kを自然数として l-2=3(k-1),m-2=4(k-1) （後は省略） ここでなぜkはk-1にするのでしょうか。あとl≧2,m≧2の理由もわかりません。ご指導のほど宜しくお願いします。
- ベストアンサー
- 数学・算数
- N以下の自然数からできる部分集合
N以下の自然数(1-N)の集合Sからできるk個要素を含む部分集合Tの個数を数列であらわしたい( k=2のとき Σ(i=1～n) n-i のように） ただ3以降がいまいち思いつきません。 こういう風にあらわすのは無理なのでしょうか？
- ベストアンサー
- 数学・算数
- エジプトの分数問題が解けたように思えるのですが。
エジプトの分数問題が解けたように思えるのですが。 4/n=1/a+1/b+1/cとすると4/(2^n・3^n-1)の形にできる数は解くことが出来ると一般にわかっているのですが2^n・3^m-1＝p(ｐは素数)とすると、ｐは必ず解ける集合CS(n、m)に含まれることは解っていません。 OOOOOO ？ ↑ ↑ ２ｑ 2q+1 2^n・3^m-1の形に解ける集合CS 2q+1はCS(n,m)集合に含まれるかどうかはまだ解らない まずはｐは解かれていない最小の素数とします。また、ｐ以下の素数はもう解かれていて2^h・3＾k-1の形になることが解っているとします。 ｐ＝2q+1＝2^h・3^k-1 2q＝2^h・3^k-2 ｑ＝{2^(h-1)}・{3^k}-1 q<ｐですのでCS(n,m)に含まれます。 CS(n,m)集合に含まれているということはｑはh、kのある自然数によって表現可能です。ということは、p=2q+1=2^h・3^h-1という形の素数にはh、kは必ず存在します。ですのでｐも2q+1も解くことができます。 あとは解くことができるかどうかわからない最小の素数をｐとおいて、数学的帰納法を用いればすべての素数を解くことができます。
- ベストアンサー
- 数学・算数
- ピタゴラス数にからんだ整数問題
以下の問題を一応証明したのですが、論述に自信がありません。入試の採点でつっこまれそうなか所を指摘して欲しいです。（京大志望です） 自然数 a，b，c について，等式 a^2+b^2=c^2 が成り立ち，かつ a，b は互いに素とする。このとき，次のことを証明せよ。 (1) a が奇数ならば，b は偶数であり，したがって c は奇数である。 (2) a が奇数のとき，a+c=2d^2 となる自然数 d が存在する。 (1) a,bをともに奇数とすると i,jを任意の自然数として a=2i-1 b=2j-1 とおける。 すると、 a^2+b^2=(2i-1)^2+(2j-1)^2 =4(i^2+j^2)+4(i-j)+2=c^2 よってcが奇数であるときc^2も奇数となるからcは偶数。 よって c=2k とおく。 すると、 0=a^2+b^2-c^2 =4(i^2+j^2-k^2)+4(i-j)+2≡2(mod.4) となって不合理。 よってa,bがともに奇数とはなり得ない。 よってaが奇数ならばbは偶数以外ありえない。 (2) m,n（m＜n）を自然数として a=n^2-m^2 c=n^2+m^2 とおく。 （a,cはともに奇数よりn,mのうち一方は偶数で一方は奇数） 以下題意をみたす任意のa,cがこのようにあらわせることを示す。 上の式をn^2,m^2について解くと n^2=(c+a)/2 m^2=(c-a)/2 となる。 よって n^2m^2=(c^2-a^2)/4=b^2/4 よって b=2mn となる。 これはbが偶数であるという(1)に矛盾しない。 よって上のようにa,b,cを表現することに不合理はない。（ただしm,nは互いに素とする。でないとa,b,cが互いに素であるという仮定に反する） またこれより題意をみたすとき a+c=2n^2 よって題意は示された。 (2)のa,cがm,nであのように表現できるという証明で、とりあえず矛盾はなさそうだからＯＫと言うような論法になってしまっている気がするのですが… どうでしょうか？
- ベストアンサー
- 数学・算数
- 自然数と偶数の一対一対応について
自然数の中から小さい方から順番にn個取り出した集合をAとし、 正の偶数の中から小さい方から同様に、同じ数だけ取り出した集合をBとします (要は自然数と正の偶数の一対一対応です) A={1,2,3,4,5, ...n} B={2,4,6,8,10,...2n} (AとBは同じ数) ここで、あるnの時の"Aには存在しないBの要素(値)の数"を考えます n=1の時、1個 n=2の時、1個 n=3の時、2個 個数だけ上げていくと、 1,1,2,2,3,3,4,4,5,5,.....と続きます "Aには存在しないBの要素の数"は、nの数に対して単調増加しており、 全てのnにおいて、少なくとも1以上であるように見えます また、nが無限大になった時でも、"Aには存在しないBの要素の数"は1以上あるようにしか思えません nが無限の時、Aを自然数全体の集合、Bを正の偶数全体の集合と呼ぶとします。 nが無限の時でも、Aに含まれないBの要素が存在します。 言い換えれば、自然数(=A)ではない正の偶数が存在するということです。 (もしそうなら最大値の存在が示せそうな気がしますし、現時点で私はそれが正しいように思います) この考えで、どこか間違いがあれば教えてください
- 締切済み
- 数学・算数
お礼
わかりやすい説明本当にありがとうございました。やはり部屋割り論法は＋1がミソですね。 ほんとにわかりやすかったです。馬鹿な高校2年生ですが、また機会があればお願いします。