7759：漸化式の初項...

問題7759・・・やどかりさんのブログ  http://blogs.yahoo.co.jp/oka_yadokary/34722630.html より Orz〜

　すべての項が 0以上である数列{ a_n }が、次のように定義されています。

　　a_n が３の倍数のとき a_n+1＝a_n/3　，　a_n が３の倍数でないとき a_n+1＝a_n−1

　では、a₁₂＝1 であるとき、a₁ の値として考えられるのは何通り？

解答

上記サイト http://blogs.yahoo.co.jp/oka_yadokary/34746148.html より Orz〜

[解答]

　例えば、a₁＝134 のとき、

　a₂＝133，a₃＝132，a₄＝44，a₅＝43，a₆＝42，a₇＝14，a₈＝13，a₉＝12，a₁₀＝4，a₁₁＝3，a₁₂＝1 になります。

　a_n から a_n+1 を求めるときの計算は、

　−1，−1，÷3，−1，−1，÷3，−1，−1，÷3，−1，÷3　になります。

　このように、−1，÷3 を 11個並べて、a₁₂ から逆にたどれば a₁ になります。

　ただし、−1 は３個以上連続で並べられませんし、−1，−1 で終わるものも適しません。

　この条件で、−1，÷3 を ｎ個並べる方法の数を T_n 通りとすれば、 

　11個の並べ方のうち、

　÷3 で始まるものが T₁₀ 通り，−1，÷3 で始まるものが T₉ 通り，−1，−1，÷3 で始まるものが T₈ 通り、

　よって、T₁₁＝T₁₀＋T₉＋T₈ になり、一般に、T_n+3＝T_n+2＋T_n+1＋T_n になります。

　T₁＝2 、−1，−1 は適さないから T₂＝3 、−1，−1 で終わるものは適さないから T₃＝6 、

　T₄＝T₃＋T₂＋T₁＝6＋3＋2＝11 、T₅＝T₄＋T₃＋T₂＝11＋6＋3＝20 、T₆＝T₅＋T₄＋T₃＝20＋11＋6＝37 、

　T₇＝T₆＋T₅＋T₄＝37＋20＋11＝68 、T₈＝T₇＋T₆＋T₅＝68＋37＋20＝125 、

　T₉＝T₈＋T₇＋T₆＝125＋68＋37＝230 、T₁₀＝T₉＋T₈＋T₇＝230＋125＋68＝423 、

　T₁₁＝T₁₀＋T₉＋T₈＝423＋230＋125＝778 となって、778通りあります。

*こういう風に漸化式を作ればいいのかと勉強になりました☆

わたしゃ…わからず…^^;

大方の目安は…連続する3個の中に÷が(1+2+3)/3=平均2個あり…

連続9個が9**,*9*,**9 の3種類、*は-1 or ÷の2種類だから…

(2^2)^(9/3)*3*2^2=2^8*3=768個...ほんまかいな ^^;…Orz〜

3進法で…最大が3^11=100000000000 なので…
次は…10000000001, 次は…1000000002,次は…100000010…
最小が134=11222 ってことから計算できないのか知らん…^^;

・友人からのもの…

後ろから見てa(12)=b(1) a(11)=b(2) ,,,,,,,,a(1)=b(12) として考える
b(i)が3n、3n+1のときはb(i+1)は+1と*3の2通りあり
3n+2のときは*3の1通り。 b(i)の場合の数を{b(i)}と書く
3n、3n+1、3n+2 いずれから出発しても{b(n+3)}={b(n)}+{b(n+1)}+{b(n+2)}
が成り立つことが分かる。
1,2,3から出発して{b(12)}=778

[スモークマン]

＞鍵コメ様へ ^^
👍 👍 ^^w
笑顔と柔らかフォルムに走化性を持つ生物が男あるね…^^…Orz〜

[スモークマン]

↑
やどかりさんの解答がアップされました♪