今週の問題 問28 答え

上野竜生です。問28の答えを発表します。

問28

自然数から文字列への関数f(n)を次のように定める。
f(1)=トマト
f(n+1)=f(n) + とトマト
たとえばf(2)=トマトとトマト, f(3)=トマトとトマトとトマト である。
このときすべての自然数nに対し,f(n)が回文であることを証明せよ。
ただし,回文とは上から読んでも下から読んでも同じになる文字列である。

答え

[ ]は文字を下から読んだものとする。例:[トマトと]=とトマト,[あいうえ]=えういあ

このとき示すものは[f(n)]=f(n)である。これを数学的帰納法で示す。

n=1のときf(1)=トマトなので[f(1)]=f(1)=トマト

n=2のときf(2)=[f(2)]=トマトとトマト より成立。

n=k, k+1での成立を仮定してn=k+2での成立を示す。

[f(k)]=f(k) , [f(k+1)]=f(k+1)を仮定する。

このとき,漸化式よりf(k+2)=f(k+1) + とトマト

[f(k+2)]
=トマトと+[f(k+1)]
=トマトと+f(k+1)
=トマトと+f(k)+とトマト
=f(k+1) +とトマト
=f(k+2)

よりn=k+2のときも成立。

下線部は
f(k+1)
=[f(k+1)]
=[f(k)+とトマト]
=トマトと+[f(k)]
=トマトと+f(k)
なので成立です。

※単純に考えると
A=トマト
B=と
とおくとA,Bは回文。
f(1)=A
f(2)=ABA
f(3)=ABABA

という風に交互に並ぶので回文 などという解答になります。とりあえず正解にしました。

また

f(n)は4n-1文字の文字列で左からk番目の文字は
kが奇数のとき ト
kを4で割った余りが2のとき マ
kが4の倍数のとき と

であるから右からt番目の文字は左から4n-t番目の文字であり,
tが奇数のとき ト
tを4で割った余りが2のとき マ
tが4の倍数のとき と

となるので回文 という解答もOKです。

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする