関数の問題

質問

０と正の整数を定義域とする関数ｆは以下の性質を持ちます
f(2n)=f(f(n))
f(2n+1)=f(2n)+1

問一　どの非負整数ｋにおいて、f(0)は2^k＋2に等しくなりますか？（f(0)がつねに2^k＋2に等しくならないという答えも可能です。その証明が必要になります）

問二　ｆ(0)の値として可能な値についてなにか説明できますか？（自分はf(0)は2のべき乗や１にはならない事を発見しました。ほかに何かこの関数の特性を見つけたら教えてください）

回答No.3

muturajcp · ベストアンサー

非負整数nに対して
f(2n)=f(f(n))
f(2n+1)=f(2n)+1
とする

f(0)=1
と仮定すると
1=f(0)=f(f(0))=f(1)=f(0)+1=2
となって矛盾するからf(0)≠1

自然数kに対して
f(0)=2^k
と仮定する
f(1)=f(0)+1=2^k+1
だから
n=1のときf(2^{n-1})=2^k+1が成り立つ
ある自然数nに対してf(2^{n-1})=2^k+1を仮定すると
f(0)=2^kは偶数だから
f(2^n)=f(f(2^{n-1})=f(2^k+1)=f(2^k)+1=f(f(0))+1=f(0)+1=2^k+1
だから
任意の自然数nに対してf(2^{n-1})=2^k+1が成り立つから
n=k+1のときも成り立つから
f(2^k)=2^k+1
2^k=f(0)=f(f(0))=f(2^k)=2^k+1
となって矛盾するからf(0)≠2^k

自然数k≧3に対して
f(0)=2^k-2
と仮定する
f(1)=f(0)+1=2^k-1
f(2)=f(f(1))=f(2^k-1)=f(2^k-2)+1=f(f(0))+1=f(0)+1=2^k-1
f(3)=f(2)+1=2^k
だから
n=1のときf(2^{n-1})=2^k-1が成り立つ
ある自然数nに対してf(2^{n-1})=2^kを仮定すると
f(2^n)=f(f(2^{n-1})=f(2^k-1)=f(2^k-2)+1=f(f(0))+1=f(0)+1=2^k-1
だから
任意の自然数nに対してf(2^n)=2^k-1が成り立つから
n=k+1のときも成り立つから
f(2^k)=2^k-1
n=1のときf(2^{n+1}-1)=2^kが成り立つ
ある自然数nに対してf(2^{n+1}-1)=2^kを仮定すると
f(2^{n+2}-1)=f(2^{n+2}-2)+1=f(f(2^{n+1}-1))+1=f(2^k)+1=2^k
だから
任意の自然数nに対してf(2^{n+1}-1)=2^kが成り立つから
n=k-2のときも成り立つから
f(2^{k-1}-1)=2^k
2^k-2=f(0)=f(f(0))=f(2^k-2)=f(f(2^{k-1}-1))=f(2^k)=2^k-1
となって矛盾するからf(0)≠2^k-2

問1
k=1のときf(0)=2^k+2=4=2^2だからk≠1
k=2のときf(0)=2^k+2=6=2^3-2だからk≠2
kをk≠1,k≠2となる非負整数においてf(0)=2^k+2

問2
f(0)の値として不可能な値は
{2^k}_{整数k≧0},{(2^k)-2}_{整数k≧2}

f(0)の値として可能な値は
0,3,5,7,9,10,12,…

お礼

問一のほうは2^k-2ではなく2^k+2ですが、興味深い結果が見れてよかったです。ありがとうございました。

回答No.2

noname#199771

＞いろいろと単純な計算を行うと矛盾をはらんだ結果が生まれる

では、それを補足に書いてみてください。

回答No.1

noname#199771

f(f(0))=f(0)からfの値が０または正の整数を取る必要があることまではいいとして、
それら21つの式がf(0)を規定（2のベキとか2^k+2とか）するようには見えません。
なぜそう思われたのでしょう？

nが1以上のときf(n)はk<nなるkについてのf(k)たちによって値が決まるので、
どんな値にしても矛盾は生じないようにみえます。

ちなみに、nを2進展開すると、
n=Σ[j=1,...,k]2^(l_j)
0≦l_1<...<l_k
としてf(n)をf(0)とl_1,...,l_kを使って表せます。

補足

実はこれらの式はf(0)を規定します。
自分は問一の証明はできて問二に取り掛かってるんですが、なかなか難しいですよね。f(0)は2^k+2にならないです。それがなぜかというとこの関数の二つの性質を用いていろいろと単純な計算を行うと矛盾をはらんだ結果が生まれるからです。