今週の問題　問131　答え

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

問131

答え

n≧8のとき，\( b_n \)を数える。
Sには少なくとも1と2は含まれている必要がある。3,4が含まれるかどうかで場合分けをする。

3が含まれるとき
Sには2,3が含まれているので{2,3,・・・,n}の部分集合SをとってきたときS∪S’’={2,3,・・・,n}になるものは\( b_{n-1} \)通りある。

3が含まれず4が含まれるとき
Sには1,2,4,5が含まれるので{4,5,・・・,n}の部分集合SをとってきたときS∪S’’={4,5,・・・n}になるものは\( b_{n-3} \)通りある。

3も4も含まれないとき
Sには1,2,5,6が含まれるので{5,6,・・・,n}の部分集合SをとってきたときS∪S’’={5,6,・・・n}になるものは\( b_{n-4} \)通りある。

よって\( b_{n} = b_{n-1}+b_{n-3}+b_{n-4} \)が成り立つ。

n=4のときは{1,2}のみ条件を満たすから\(b_4=1 \)
n=5のときは{1,2,3}のみ条件を満たすから\(b_5=1 \)
n=6のときは{1,2,3,4}のみ条件を満たすから\(b_6=1 \)
n=7のときは{1,2,3,4,5},{1,2,4,5}のみ条件を満たすから\(b_7=2 \)

ここから漸化式を使って\( b_8 , b_9 ,\cdots \)を求めていくと

となる。よって\( b_{16}=169 \)

正解者：1名（チンポ矢沢 さま）