werry-chanの日記．料理とエンジニアリング

料理！コーディング！研究！日常！飯！うんち！睡眠！人間の全て！

ますらば東大模試(2)解いてみた

入試問題数学東京大学模試高校数学数列場合の数三項間漸化式漸化式

筑波山の梅祭りに行ってきて，休憩所で飲んだ梅昆布茶が美味しくて買ってしまったウェリーちゃんです．
3月3日に筑波山梅祭りの梅酒試飲会があるそうですが，その日は大阪に帰ってるかもです．行きたかったので残念です．

さて前回に続き「ますらば東大模試」第2問です．

werry-chan.hatenablog.com
↑問1の僕の解いた解答はこちらです．

それでは問題に入りましょう．

問2

nを正の整数とする．赤色と白色の 2 種類の球が十分な数ある．横一列に並んだn 個の箱それぞれに，赤白どちらかの球を最大1個ずつ入れていく事を考える（球を入れない箱があっても良い）．このとき，どの隣り合う 2 つの箱にも同色の球が存在しないような球の入れ方は何通りあるか．

下に解答を載せてますので，注意です．

[解答]

k個の箱が並んでいる時，
k番目が空の場合が $a_k$ 通り，赤の場合は $b_k$ 通り，白の場合は $c_k$ 通り存在すると仮定する．

k+1番目の箱を追加すると，
k番目の空の箱の次に並び得る物は，空or赤or白
k番目の白の箱の次に並び得る物は，空or赤
k番目の赤の箱の次に並び得る物は，空or白

すなわち，

$a_{k+1}=a_k+b_k+c_k$ ---①

$b_{k+1}=a_k+c_k$ ---②

$c_{k+1}=a_k+b_k$ ---③

とk+1番目の箱について考えられる．

ここで②-③式は，

$b_{k+1}-c_{k+1}=-(b_k-c_k)$

となる．これは左辺と右辺は同型なので

$b_{k+1}-c_{k+1}=-(b_k-c_k)=(-1)^2(b_{k-1}-b_{k-1})=...=(-1)^k(b_1-c_1)=0$

ここで， $b_1=1,c_1=1$ を利用した．
以上より， $b_k=c_k$ が導けた．(ぶっちゃけ言うと，対称性より明らか．)

$b_k=c_k$ を①, ②式に代入して，

$a_{k+1}=a_k+2b_k$ ---④

$b_{k+1}=a_k+b_k$ ---⑤

④式を

$b_k=\frac{a_{k+1}-a_k}{2}$

と変形して，⑤式に代入すると $a_k$ に関する式

$a_k=\frac{a_{k+2}-a_{k+1}}{2}-\frac{a_{k+1}-a_k}{2}$

整頓して

$a_{k+2}-2a_{k+1}-a_k=0$

となる．

特性方程式を解いてやると，

$a_{k+1}=\frac{\beta^k(a_2-\alpha a_1)-\alpha^k(a_2-\beta a_1)}{\beta -\alpha}$ ---⑥

ここで，特性方程式の解を

$\alpha =1+\sqrt{2}, \beta=1-\sqrt{2}$

とおきました．

最後に， $a_1=1, a_2=3$ を利用して⑥整理すると

$a_{k+1}=\frac{(1+\sqrt{2})^{k+1}+(1-\sqrt{2})^{k+1}}{2}$

が導かれる．

求めるべき通り数は $a_n+b_n+c_n$ であり，①式を利用すると，

$a_n+b_n+c_n=a_{n+1}=\frac{(1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1}}{2}$

とわかった．

解答終了.

間違ってるとか，別解あるよーとか，コメントあればよろしくです．