今週の問題　問131　答え｜数学の偏差値を上げて合格を目指す

当サイトは、PRを含む場合があります。

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

問131

[21　慶應義塾環境情報　改]

$ A_n = \{ 1,2, \cdots n \} $を，1からnまでの自然数の集合とする。Sを$A_n$の部分集合としたとき，S''をSの要素それぞれに2を加えてできた集合とする。
たとえば$ A_3=\{1,2,3\} $の部分集合$ S=\{1,3\} $の場合，$ S''=\{3,5 \} $となる。

$ A_n $の部分集合Sで$ S\cup S''=A_n $となるようなSの個数を$ b_n $とする。$ b_{16} $を求めよ。

答え

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 $を求めていくと