すべての正の整数 n に対して
f(f(n)) = n+1
となるような正の整数から正の整数への写像fは存在しないことを示せ。
fの定義域だけではなく、値域も「正の整数」でないといけません。
寝る前にこの問題を見てしまって、夢の中でうなされながらこの問題を考えていたんだけど、一応解けたような気がします。・・・間違ってるかもしれん(ﾟ∀ﾟ)
僕の解答は先日のエントリの末尾にコメントで書きましたが、他の方法などあったらぜひ教えてください。
(追記)
dsk氏のコメントにありましたが、1987年の数学オリンピックの問題を易しくしたものだそうです。
こういうシンプルで面白い問題を考え付く人って本当に凄いと思います。
Comments
fが全射であるとするとf^2も全射なので、f(f(n))は正の整数全体を取るので
f(f(n)) = n+1と矛盾。よってf(n)がとり得ない正の整数があるはずですが、
そのうちの一つをkとし、f(k) = mとします。
f(k) = k とすると、k は f(n)が取り得ない正の整数であることに矛盾するので、k ≠ mです。
f(f(n)) = k となるnがあるとするとfにf(n)を適用してkとなるのでやはり、k は f(n)が取り得ない正の整数であることに矛盾するので f(f(n)) = kとなるnはありません。
またf(f(n)) = m となるnがあるとするとf(f(n)) = f(k) とfが単射より f(n) = k
となって、やはりk は f(n)が取り得ない正の整数であることに矛盾。よって、f(f(n)) = mとなるnはありません。
よってf(f(n))がとり得ない値がkとmの2つできました。これはf(f(n)) = n+1と矛盾します。
この方法で分かるように f(f(n)) = n+1以外でも定義域から値域を除いた集合が丁度1つになるような場合は起きないことが分かります。
1の行き先を決めれば、この写像は一意に決まります。
簡単のため、fの写像を→で書きます。
f(a)=bをa→bという具合に。
f(1)=xとすると、
1→x→2→x+1→3→x+2→4→x+3→5→x+4・・・
こんな数列が現れます。
この数列。1から少しずつ増えて行き、何回か進むといずれxに到達し、元に戻ってしまう。。。
具体的には2x+1回目でxに戻ります。
・・・→x-1→2x→x→？？？
そうすると、その次の値に矛盾がでますね。
この数列の定義でいけば、次は2x+1。
でもx→2なんです。
これは矛盾。
よって、このような写像は存在しません。
なるほど!
こっちの解答のほうがエレガントですね。
matsuさん:
僕も最初に数列を使う解法を思いついたのですが、数列の一般項の証明で挫折しました。
(一般項が証明できないと、全体の証明が成立しないですよね?)
An = (n+1)/2 (nが奇数のとき)
An = f(1)+n/2-1 (nが偶数のとき)
上のような一般項になると思うのですが、これって自明なんですかね?
うまく証明できなかった。
・A1=1
・A2=f(1)
・A(2n+1)=n+1と仮定すると、A(2n+3)=A(2n+1)+1=n+2
・A(2n)=f(1)+n-1と仮定すると、A(2n+2)=A(2n)+1=f(1)+n
f(1) = x とおく。このとき、
f(x) = 2 かつ f(x) = 2x - 1 であること(matsuさんは2x+1と書いていますが正確には2x-1です。ご確認ください。)を導いています。ここを正確にかくと、
f^{2x-1}(1) = f^{2(x-1)}(x) = x+(x-1) = 2x-1
f^{2x-1}(1) = f(f^{2n}(1)) = f(n+1) = f(x) = f(f(1)) = 2
よって、 2 = 2x - 1 となって f(1) = x = 3/2 となり矛盾。
実はこれは本質的に miyanoくんの解答と同じなのです。
miyanoくんの場合はfをもう一回掛けていたのを戻す都合上、
単射の証明が必要でしたが、
「fの存在を仮定してf(1) = x とおき、 2 = 2x-1 という矛盾
を導いている」というところが両方の解答の本質です。
この式は説明不足でした。
自分の中で n = x-1 とおいて計算していました。
f^{2x-1}(1) = f(f^{2(x-1)}(1)) = f(x) = f(f(1)) = 2
と書くべきでした。
この問題を見ると、シャンボール城の二重螺旋階段の上に、黄色と赤のメビウスの輪が飾られている情景が思い浮かびます。
f(n)=nとなるnがあるとすると、f((f(n))=n となるので、
すべての正の整数は以下の二つの集合に分けられます。
A = {x|f(x)>x}
B = {x|f(x)<x}
(i) f(1)は1以外の正の整数なので、1はAに属します
(ii) ある整数nがAの要素だとすると、
f(n) > n
f(n+1) = f(f(f(n))) = f(n)+1 > n+1
となるため n+1もAの要素となります。
(i),(ii)から全ての正の整数はAに属します
そのとき、 f(f(n)) > f(n) > n から
f(f(n)) > n+1 となり、題意を満たしません。
これはわかりやすい!さすがです。
数学的帰納法で f(n) > n が証明できてしまうんですね。
カルティエブランドコピー、ブルガリコピー時計販売「18%OFF」当店はカルティエコピー、
ブルガリコピー品のレプリカ販売専門ショップです。
新作品の世界大人気ブルガリコピー、ブランドコピーカルティエ腕時計続々入荷中!
ロレックス時計コピー http://www.cocoejp.com/ProductList1.aspx?TypeId=933972618491451