2017年入試問題研究に戻る

東工大4番解答

(1)　 $ A_n $ の要素の個数は， $ n $ 個並んでいる文字を， $ a,\ b,\ c $ のどれにするかの場合だけあり， $ 3^n $ 個である． そのうち，文字cが連続して現れない並べ方の総数を $ a_n $ とする．
文字cが連続して現れない $ n+2 $ 個の文字列を，最初の文字で場合分けする． それが $ a $ か $ b $ なら，2番目からの $ n+1 $ 個は，そのなかで $ c $ が連続しなければよい． それが $ c $ ならその次は $ a $ か $ b $ で， 3番目からの $ n $ 個は，そのなかで $ c $ が連続しなければよい． よって， \[ a_{n+2}=2a_{n+1}+2a_n \] が成り立つ． $ n=1 $ のときは， $ a,\ b,\ c $ なので $ a_1=3 $ ， $ n=2 $ のときは， $ cc $ 以外なので $ a_2=3^2-1=8 $ である．
ここで，漸化式を \[ a_{n+2}-(\alpha+\beta)a_{n+1}+\alpha\beta a_n=0 \] と変形する． $ \alpha+\beta=2 $ ， $ \alpha\beta=-2 $ なので， \[ \alpha=1-\sqrt{3},\ \beta=1+\sqrt{3} \] である．このとき漸化式は \[ a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1}-\alpha a_n) \] と変形されるので， \[ a_{n+1}-\alpha a_n=\beta^{n-1}(a_2-\alpha a_1) \] ここで， \[ a_2-\alpha a_1=5+3\sqrt{3}=\left(1+\sqrt{3}\right)\left(2+\sqrt{3}\right) =\dfrac{\left(1+\sqrt{3}\right)^3}{2} \] なので， \[ a_{n+1}-\alpha a_n=\dfrac{\beta^{n+2}}{2} \] 同様に \[ a_{n+1}-\beta a_n=\dfrac{\alpha^{n+2}}{2} \] なので，この2式を辺々引いて， \[ (\beta-\alpha) a_n=\dfrac{\beta^{n+2}}{2}-\dfrac{\alpha^{n+2}}{2} \] $ \beta-\alpha=2\sqrt{3} $ より \[ a_n=\dfrac{1}{4\sqrt{3}}\left(\beta^{n+2}-\alpha^{n+2}\right) \] よって， \[ P(n) =\dfrac{a_n}{3^n} =\dfrac{1}{4\sqrt{3}\cdot3^n}\left(\beta^{n+2}-\alpha^{n+2}\right) \] ここで， $ \alpha $ と $ \beta $ は上記のものである．

(2)　 条件 $ (*) $ を満たし，その7番目の文字は $ c $ であるので， 6番目と8番目は $ a $ か $ b $ であり，このとき， 1〜5番と9〜 $ n $ 番はそのなかで $ c $ が連続しなければよい． その文字列の総数は $ 4\cdot a_5\cdot a_{n-8} $ である．
この条件の下でさらに，10番目の文字が $ c $ であるのは， 9番目と11番目は $ a $ か $ b $ であり，このとき， 1〜5番と12〜 $ n $ 番はそのなかで $ c $ が連続しなければよい． その文字列の総数は $ 4^2\cdot a_5\cdot a_{n-11} $ である． 総数はいずれも $ 3^n $ なので， \begin{eqnarray*} Q(n)&=&\dfrac{4^2\cdot a_5\cdot a_{n-11}}{4\cdot a_5\cdot a_{n-8}}\\ &=&\dfrac{4\cdot a_{n-11}}{a_{n-8}} =4\cdot\dfrac{\beta^{n-9}-\alpha^{n-9}}{\beta^{n-6}-\alpha^{n-6}}\\ &=&4\cdot\dfrac{1-(\alpha/\beta)^{n-9}}{\beta^3-\alpha^3(\alpha/\beta)^{n-9}} \end{eqnarray*} $ |\alpha/\beta|< 1 $ より \[ \lim_{n \to \infty}Q(n)= \dfrac{4}{\beta^3}=\dfrac{2}{5+3\sqrt{3}}=3\sqrt{3}-5 \]

問題