|
問題1535
上の図のようにア〜シの１２枚の正方形のタイルが並んでいます。
いま、「ア」のタイルを踏んでいるマサルさんが、隣り合うタイルを次々と踏んでいく（※）とき、全部のタイルを１回ずつ踏む方法（順番）は何通りあるでしょうか。
※例えば、「ア」にいるときには、次に踏むタイルは「イ」または「ウ」であることになり、「ア」→「ウ」と進んだ場合は、次に踏めるのは「イ」または「エ」または「オ」となります。
（現実には、「エ」に進んでしまうと、全部踏むことが出来なくなってしまいますのでダメですが..）
解答
結局途中で放棄してました...^^;
・バルタン星人さんのもの Orz〜
アからはイとウ以外に行けない。イからはＡn-1、ウからイエに行くのは
はＡn-3、ウエと行くのが１通り。Ａｎ＝Ａn-1＋Ａn-3＋１、
あとは漸化式を解くのではなくＡ1＝Ａ2＝１ Ａ3＝２から順にＡ12を求めました。
・なかさんのもの Orz〜
漸化式
タイルがｎ枚のときにa(n)通りの踏み方があるとする。
a(1)=1, a(2)=1, a(3)=2 である。
タイル n 枚の踏み方は、
(1) アイ で始める場合が a(n-1)通り、
(2) アウイエ で始める場合が a(n-3)通り、
(3) アウオ からぐるりとまわる 1通り、がすべてである。
よって、a(n) = a(n-1)+a(n-3)+1
a(4)=2+1+1=4
a(5)=4+1+1=6,,,a(12)=100,,,,a(18)=1000
う〜ん、、、わたしには漸化式の作り方がよく分からないなあ...^^;
|
コメント（5）
