鳩ノ巣原理の証明

質問

S={1,2,3......2n}の自然数の集合があり、
この中からn+１個を任意に取り出しペアーを組むと、必ず一方が他方の異なる二つの数x,yがあります
これを証明したいのですが、

例えばn=4として
Ｓ＝1,2,3,4,5,6,7,8となるので
後半の5,6,7,8をまず選び、前半のどれを選んでも後半のどれかの約数になるという感じの証明はできますか?

回答No.4

178-tall · ベストアンサー

参考 URL みたいな「話題」？

参考URL：

http://www004.upp.so-net.ne.jp/s_honma/divisor/divisor2.htm

回答No.5

MagicianKuma

やりたいことがわかりました。ありがとう。No4さんの参考URLに答えが出ているようです。ちょっと補足しますね。
>任意の ａ∈Ａ は、必ず、２＾s（２ｔ＋１） の形に書けるので
この部分が分かりにくいと思います。まず、
全ての自然数は素因数分解できまたその分解は一意に決まります。[有名な定理です］素因数分解とは次のことです。
自然数をnとしたとき　n＝(p1^k1)・(p2^k2)・(p3^k3)・・・と表される。ここでp1,p2,・・・は小さい順に並べた素数を表しています。k1,k2,・・・は0以上の整数です。
一意という意味は、nを上のように表したとき、k1,k2,・・・の数値が1種類に決まるということです。例：6860=2^2x3^0x5^1x7^2 (k1,k2,・・・)=(2,0,1,2,0,0,0・・・)
以上を踏まえた上で、p1^k1(=2^k1)の部分とそれ以降の部分に分けて考えて見ます。p2,p3,、・・・は2以外の素数ですから全て奇数となります。
奇数のべき乗も奇数になりますから、結局(p2^k2)・(p3^k3)・・・の部分は奇数の値となります。なので、
任意の自然数　n＝２＾k1・奇数　文字を書き換えて、a＝2^s（2t+1)　　s、tは0以上の整数　とかけます。
で、具体的に考えているaの最大値が分かっていれば、(2t+1)のtのとりうる範囲を抑えることができます。
問題では、aの奇数の最大値は2n-1ですから、2n-1＝2^0・(2t+1)の可能性を考えると、t≦n-1となります。
まとめると、1から2nまでの自然数は2^s・(2t+1)　0≦t≦n-1 で一意に表現できるということです。

回答No.3

MagicianKuma

>必ず一方が他方の異なる二つの数x,yがあります
の意味は？

もともとS＝{1,2,3,...2n}なら各元は全て異なる数値ですね。
そこからn+1個を選んでもそれぞれは全て異なる数値ですね。
で、そこからペアを組んだ（2個選んだ）x,yは必ず異なる数値では？

質問の例えば以降の文章は、n=4として・・・後半の5,6,7,8をまず選び（n+1個選んでないし！)・・・約数って元問題に関係ないし。ということでまったく参考になりません。

ので、元問題の証明したいことの例を、分かる日本語で書いておくれ。

補足

S := {1, 2, 3, . . . , 2n} の 2n 個の数値からなる集合を考える．S から任意
の n + 1 個の数値を選び取り，選んだ n + 1 個の数値の中に，必ず一方が
他方の約数になる異なる二つの数 x, y が存在する．という問題です

回答No.2

asuncion

＞例えばn=4として
＞Ｓ＝1,2,3,4,5,6,7,8となるので

これはいいとして、

＞この中からn+１個を任意に取り出し

ということは5個を任意に取り出すのですよね。

＞後半の5,6,7,8をまず選び

4個しかないですよ。おかしくないですか？

結局、何をどうしたいのか、よくわからないままです。

回答No.1

MagicianKuma

日本語がいまいち理解できません。
>この中からn+１個を任意に取り出し　　
これは分かります。
>ペアーを組むと
どういう意味？　何と何のペア？
>必ず一方が他方の異なる二つの数
必ず一方が他方「と」異なる二つの数　の意味？

補足

n+1個の中から任意に二つずつ割り振るということです

(１，３）　（２，４）みたいな感じにです