証明を教えてください

質問

A1,A2 ...........Amnをmn+１の実数の列として

m+1の数からなる単調増加部分列
あるいはn+１からなる単調減少部分列
が存在する

これを鳩ノ巣原理を用いて証明してください

回答No.2

MagicianKuma

問題は正確に書きましょう。想像して補足してみます。
>A1,A2 ...........Amnをmn+１の実数の列として
「A1,A2,・・・Amn+1をmn+1個の異なる実数の列として」が正しいと想像されます。（3箇所補いました）

定義
1.部分列：先の実数列からk個の数値を選び、順番を変えずに並べたものを長さkの部分列と呼ぶとします。ただし1≦k≦mn+1
2.単調増加部分列：部分列をB1,B2,・・・,BkとしたときB1<B2<・・・<Bkなら単調増加部分列と呼ぶことにします。
3.単調減少部分列：部分列をB1,B2,・・・,BkとしたときB1>B2>・・・>Bkなら単調減少部分列と呼ぶことにします。
4.長さ1の部分列は単調増加部分列でもあり、単調減少部分列でもあるとします。

証明する定理
長さm+1の単調増加部分列あるいは長さn+1の単調減少部分列が存在する。
指針：背理法と鳩の巣原理を用います。
証明
(1)長さm+1の単調増加部分列も長さn+1の単調減少部分列も存在しないと仮定します。
(2)元の実数列に戻って、i番目の実数Aiから始まる部分列全体を考えます。
この時、これらの部分列で単調増加列になっているものの最大の長さをXiとします。
また、、これらの部分列で単調減少列になっているものの最大の長さをYiとします。
定義と(1)よりXi、Yiは必ず存在し、1≦Xi≦m,1≦Yi≦nである。
(3)(2)と同様にi≠jなるj番目の実数Ajから始まる部分列全体を考えます。
i<jのとき、Ai>AjならYi>Yj,Ai<AjならXi>Xjとなる。
i>jのとき、Ai>AjならXi<Xj,Ai<AjならYi<Yjとなる。
よって、i≠jならXi≠XjまたはYi≠Yj
(4)ここで、写像φをφ(Ai)=(Xi,Yi)として定義する。(3)の結果から、Ai≠Ajならφ(Ai)≠φ(Aj)なので、写像φは単射である。
(5)一方、集合｛Ai}の要素数はmn+1,1≦Xi≦m,1≦Yi≦nから{φ(Ai)}の要素数はmn以下。よって写像φは単射ではありえない。これは(4)と矛盾。
(6)この証明のなかで、仮定したのは(1)のみ。よって(1)は偽。すなわち、長さm+1の単調増加部分列あるいは長さn+1の単調減少部分列が存在する。

蛇足：鳩の巣原理は(5)です。大きい集合から小さな集合への単射は存在しない。

回答No.1

noname#157574

鳩ノ巣原理ではなく鳩の巣原理です。
鳩ノ巣なる地名がありますが、誤字に注意しましょう。