第84回　算数問題　（2月５日〜3月4日）

○か×を１０個並べます。このとき　どの連続する３つの記号のなかにも必ず○と×があるような並べ方は何通りあるでしょうか。

たとえば○○××○○××○○はこの条件を満たしています。


解答

条件を満たすｎ個からなる記号の並び全体の個数をｓ（ｎ)とし　
このなかで
○○で終わるのものの個数を　a（n）
○×で終わるのものの個数を　b（n）
×○で終わるのものの個数を　c（n）
××で終わるのものの個数を　d（n）　とします。

このとき　○○で終わるものと×○で終わるものの最後に×をつけると
○×で終わるn+1個記号になるので
b(n+1)=a(n)+c(n)
同様に
a(n+1)=c(n)
c(n+1)=b(n)+d(n)
d(n+1)=b(n)
この4つの式を足すと
s(n+1)=a(n)+2×b(n)+２×c(n)+d(n)
　　　　=s(n)+b(n)+c(n)
　　　　=s(n)+a(n-1)+b(n-1)+c(n-1)+d(n-1)
　　　　=s(n)+s(n-1)
s(1)　○　、×　　より　s(1)=2
s(2)　○○　、○×、×○　、××　より　s(2)=4
s(3)=s(1)+s(2)=2+4=6
s(4)=s(2)+s(3)=4+6=10
s(5)=6+10=16
s(6)=10+16=26
s(7)=16+26=42
s(8)=26+42=68
s(9)=42+68=110
s(10)=68+110=178