Question

名探偵コナン好き

全く理解できませんでした。どなたか教えていただけませんか？

13*自然数nに対して, 1からnまでのすべての自然数の集合を Nとする。
Nから N への写像f が次の条件
「i,j が Mの要素で, isj ならば, つねに f(i)<f())」
をみたすとき,f(k)=k となるN の要素kが存在することを示せ.

牛(ロー)
ると
13*(解答1](数学的帰納法)
「1Sf(1)Sf(2)<…sf(n)<nならばf(k)=Dk となる k (1ハんニn)がある」. …0
これを数学的帰納法で示す。
(i) n=1 のとき, 1<f(1)<1 ならば f(1)=1 であるから, ① は成り立つ。
(i) n=1 (21) のとき, ①が成り立っと仮定すると, n=l+1 のとき,
f(1+1)=1+1 ならば k=l+1 として①は成り立つ。
f(1+1)<1 ならば1<f(1)<f(2)<…. ハf(1)S1
であるから,数学的帰納法の仮定から, ① は成り立つ.
よって, ① は n=1+1 のときも成り立つ。
以上の(i), (i) から, ①は任意の自然数 n について成り立つ.
(終)
【解答2)(背理法 1)
「1SkSn である任意の k に対して, f(k)キ1k である」

と仮定する。
条件より 1Sf(1) であるが,仮定②より f(1) +1 だから 2f(1).
これと条件より 2<f(1)sf(2) であるが、 ② ょり f(2)キ2 だから 34f(2).
これを繰り返すと,n+1<f(n)となり、fが N から N への写像,すなわち
1Sf(k)Sn(1sksn) であることに反する。
(終)
f(k)=k となる k(1<kハ») がある。
【解答3)(背理法2)
「F(k)=k となる k (1<kSn)がない」
と仮定すると,右図において, 点(1, f(1)) は直線
ソ=x より上にあり,点(n, f(n)) は直線 y=x より下
にあることになり,点(1, f(1)) から点(n, f(n)) まで
非右下がり(: isjならば f(i)<f()) で進めるこ
とになるが,仮定から対角線上の× 印は通れないからこ
n
3
2
れは矛盾。
x
: f(k)=k となる k(1<kいn) がある. (終)
0123…n-1n
【解答4)(集合の利用)
(i) f(n)=n なら, 題意成立.
(i) f(n)キn なら, 条件から f(n)<n.
よって,集合 S={k|f(k)<k} を考えると, Sキゆ.(: nES)
S の要素の最小数を ko とすると, f(ko)<ko(キ1).
ここで,f(ko)=k, とおくと, kくんo.
f は非減少関数だから f(ki)<f(ko),
かつ
k」年S だから, S の定義から f(ki)>kf(ko).
: f(ko)=k=f(ki) (1<kSn).
f(k)=k をみたす k (1<kSn) がある。
よって,
(終)