2021年入試問題研究に戻る京大特色2番解答
(1) 横 $ n $ 個，縦2個からなるマスに黒玉が隣りあわないように白玉または黒球を入れる． そのうち， 左端の2マスがともに白玉である入れ方が $ b_{n,2} $ 通りあり， 左端の2マスが白玉と黒球である入れ方が $ c_{n,2} $ 通りあるとする． $ a_{n,2}=b_{n,2}+c_{n,2} $ である．そして，入れ方の条件から \[ \begin{array}{l} b_{n+1,2}=b_{n,2}+c_{n,2}\\ c_{n+1,2}=2b_{n,2}+c_{n,2}\\ b_{1,2}=1,\ c_{1,2}=2 \end{array} \] が成り立つ．これから， \begin{eqnarray*} a_{n+2,2}&=&3b_{n+1,2}+2c_{n+1,2}\\ &=&2a_{n+1,2}+b_{n+1,2}=2a_{n+1,2}+a_{n,2} \end{eqnarray*} を得る． $ \alpha=1-\sqrt{2} $ ， $ \beta=1+\sqrt{2} $ とおくと， \[ a_{n+2,2}-(\alpha+\beta)a_{n+1,2}+\alpha\beta a_{n,2}=0 \] つまり， \[ a_{n+2,2}-\alpha a_{n+1,2}=\beta\left(a_{n+1,2}-\alpha a_{n,2} \right) \] よって， \[ a_{n+1,2}-\alpha a_{n,2}=\beta^{n-1}\left(a_{2,2}-\alpha a_{1,2} \right) \] 同様に \[ a_{n+1,2}-\beta a_{n,2}=\alpha^{n-1}\left(a_{2,2}-\beta a_{1,2} \right) \] ここで， \begin{eqnarray*} a_{1,2}&=&b_{1,2}+c_{1,2}=3\\ a_{2,2}&=&b_{2,2}+c_{2,2}=3+4=7 \end{eqnarray*} なので， \begin{eqnarray*} a_{2,2}-\alpha a_{1,2}&=&4+3\sqrt{2}=\sqrt{2}\beta^2\\ a_{2,2}-\beta a_{1,2}&=&4-3\sqrt{2}=-\sqrt{2}\alpha^2 \end{eqnarray*} よって， \[ \begin{array}{l} a_{n+1,2}-\alpha a_{n,2}=\sqrt{2}\beta^{n+1}\\ a_{n+1,2}-\beta a_{n,2}=-\sqrt{2}\alpha^{n+1} \end{array} \] 辺々引いて $ a_{n,2} $ を求めると， \[ a_{n,2}=\dfrac{1}{2}\left\{\left(1+\sqrt{2} \right)^{n+1}+\left(1-\sqrt{2} \right)^{n+1} \right\} \] である．
(2) 縦方向に $ i $ 番目，横方向に $ j $ 番目のマスを $ (i,\ j) $ と表す．
$ \dfrac{1}{2}\leqq \dfrac{\log_2a_{n,n}}{n^2} $ を示す． これは $ 2^{\frac{n^2}{2}}\leqq a_{n,n} $ と同値である．
$ n $ が偶数のとき．
$ (1,\ 1),\ (1,\ 3),\ \cdots $ ， $ (2,\ 2),\ (2,\ 4),\ \cdots $ と1つおきにマスを $ \dfrac{n^2}{2} $ 個選び， ここに白玉または黒球を入れ，他のマスには白玉を入れる． これは黒玉が上下左右のいずれにも隣りあわない入れ方であり， $ 2^{\frac{n^2}{2}} $ 通りある． よって， $ 2^{\frac{n^2}{2}}\leqq a_{n,n} $ である．
$ n $ が奇数のとき．
同様に， $ (1,\ 1),\ (1,\ 3),\ \cdots $ ， $ (2,\ 2),\ (2,\ 4),\ \cdots $ と1つおきにマスを選ぶ． $ (n-1,\ 2),\ (n-1,\ 4),\ \cdots $ と選んだ段階で，選ばれたマスと選ばれなかったマスが同数である． よって，縦 $ n $ 番目まで選ぶと選ばれたマスは $ \dfrac{n^2+1}{2} $ である． ここに白玉または黒球を入れ，他のマスには白玉を入れる． これは黒玉が上下左右のいずれにも隣りあわない入れ方であり， $ 2^{\frac{n^2+1}{2}} $ 通りある． よって， $ 2^{\frac{n^2+1}{2}}\leqq a_{n,n} $ であり， $ 2^{\frac{n^2}{2}}\leqq a_{n,n} $ が成り立つ．
次に $ \dfrac{\log_2a_{n,n}}{n^2}\leqq \dfrac{1}{2}\log_2\left(1+\sqrt{2} \right)+\dfrac{D}{n} $ を示す．
$ n $ が奇数のとき．
$ 2\times n $ のマスで黒玉が隣りあわないものを $ \dfrac{n+1}{2} $ 個用意し， 縦方向に隣りあわせておく．そのうち最終の横一列をのぞくと， $ n\times n $ のマスができる．
これらの総数は $ {a_{n,2}}^{\frac{n+1}{2}} $ 個あり， $ n\times n $ で黒玉の隣りあわないものはすべてこのなかに含まれる．
よって， $ a_{n,n}\leqq {a_{n,2}}^{\frac{n+1}{2}} $ が成り立つ．
同様に考え， $ n $ が偶数のときは $ a_{n,\ n}\leqq {a_{n,2}}^{\frac{n}{2}} $ が成り立つ．
いずれの場合も $ a_{n,n}\leqq {a_{n,2}}^{\frac{n+1}{2}} $ が成り立つ．
したがって， \begin{eqnarray*} \log_2a_{n,n}&\leqq& \dfrac{n+1}{2}\log_2a_{n,\ 2}\\ &=&\dfrac{n+1}{2}\log_2\dfrac{1}{2}\left\{\left(1+\sqrt{2} \right)^{n+1}+\left(1-\sqrt{2} \right)^{n+1}\right\}\\ &\leqq &\dfrac{n+1}{2}\log_2\left(1+\sqrt{2} \right)^{n+1} =\dfrac{(n+1)^2}{2}\log_2\left(1+\sqrt{2} \right) \end{eqnarray*} ここで， $ (n+1)^2\leqq n^2+4n $ なので， \[ \dfrac{(n+1)^2}{2}\log_2\left(1+\sqrt{2} \right) < \dfrac{n^2}{2}\log_2\left(1+\sqrt{2} \right)+2n \log_2\left(1+\sqrt{2} \right) \] したがって， \[ \dfrac{\log_2a_{n,n}}{n^2}\leqq \dfrac{1}{2}\log_2\left(1+\sqrt{2} \right)+\dfrac{2 \log_2\left(1+\sqrt{2} \right)}{n} \] が成り立ち， $ D=2 \log_2\left(1+\sqrt{2} \right) $ が条件を満たす．