電子書籍の厳選無料作品が豊富!

以下の問題の解答・解説がわかりません。
問題
gは任意の正の整数nに対し定義された関数で、以下の条件をみたすものとする。
(1) g(1)=1
(2) g(n+1) = g(n) +1 または g(n+1) = g(n) -1(n>=1)
(3) g(3n) = g(n) (n>=1)
(4) g(k) = 2001を満たす正の整数kが存在する。
このような全ての関数gのうちで(4)の条件を満たす最も小さいkの値を求めよ。

解説の6行目に
このように定義したf(n)が,3^m<=n<3^(m+1)を満たすすべてのnについて以下を満たすことを、mに関する帰納法で証明する。
とありますが、上記になるのがよくわかりません。また解として記載されているN(2000)=(3^2000+1)/2 である。という箇所もどこが解(解はk=2000という事でしょうか)でどうしてそうなるのかわかりません。
解答の解説については画像にて添付します。

「「中学生からの数学オリンピック」P21 」の質問画像

A 回答 (1件)

答は (3^2000 + 1)/2 。


 (2)から、nを1増やすとgはたかだか1しか増えない。なので(1)から、g(2000)≦2000 なのは明らかですよね。

 問題の仕掛けのエッセンスはというと: 早く2001に到達するために、nを増やすにつれてg(n)を1づつ増やして行きたいところだけれど、(3)の条件から、nが3の冪乗のときにg(n)=g(1)=1に戻ってこなくちゃならない。nが2×(3の冪乗)のときにg(n)=g(2)≦2に戻ってこなくちゃならない。こういう縛りがあるために、gはちょっとずつしか大きくなれない関数であり、2001という値を取るには、どんなに旨くやってもとんでもなく長い系列を辿る必要があるってことです。
 たとえばn=1〜100ぐらいについて、例を作ってみると良いでしょう。(3)の条件 g(1)=g(3)=g(9)=g(27)=1, g(2)=g(6)=g(18)=g(54), g(4)=g(12)=g(36), g(5)=g(15)=g(45), … に注意して「1づつ増減しながら、なるべく大きな値を取る」という方針でgの例を作ってみると、こういうことか、と分かるだろうと思います。(その「分かったこと」を旨く言語化(記号化)すれば、解けたも同然です。)
 まるで犬の放し飼いのようで、犬はどんどん走って行きたいのだけれども、呼ばれると戻ってこなくちゃならん。呼ばれる間隔(すなわち((3の冪乗)の間隔)が長くなるにつれて、犬はだんだん遠くまで行けるようになる。最初(n=1,2,3)は 1, 2, 1 で戻ってくるので最大2までしか行けないのが、2回目(n=3〜9)は 1*, 2, 3, 2*, 3, 2, 1*で最大3、3回目(n=9〜27)は 1*,2,3,2*,3,4,3*,4,3,2*,3,4,3*,4,3,2*,3,2,1* で最大4、という風に、1つずつ遠くに行けるわけです。(*印は(3n)=g(n)の条件によって前の回で決まってしまう所です。)

 で、ご質問の証明のどこがどう分からんのか、もうちょっと詳しく説明していただけませんかね。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!