第102回　算数問題　（9月5日〜10月4日）

上の図のように赤い点が黒い線で結ばれている
このとき　一番左の点を出発して黒い線をたどって　すべての点を１度ずつ通る方法は何通りありますか

解答

ｎ個の点があるときの方法をa(n)とおりとします
最初に右上に動いたときは　最初の点を除いてn-1個の場合を考えることになるから　a(n-1)とおり
最初に右横に動いたときは
　　　　　次にまたひとつ右横に動くとき　下の点をすべて通ってから上の点をたどって戻ってくる１通り
　　　　　次に左上に動くとき　次は右横にうごかなくてはいけない　その後はn-3個の点の場合を考えることになるから
　　　　　　　　　　　　　　　　　　a(n-3)とおり

よって　a(n)=a(n-1)+a(n-3)+1となる

a(1)=1　a(2)=1　a(3)=2　a(4)=4から　順次求めると
a(5)=a(4)+a(2)+1=６
a(6)=a(5)+a(3)+1=9
a(7)=a(6)+a(4)+1=14
a(8)=a(7)+a(5)+1=21
a(9)=a(8)+a(6)+1=31
a(10)=a(9)+a(7)+1=46
となります