入試数学コンテスト第5回第4問解答解説

更新日時 2021/12/10
目次
  • 第4問[場合の数・数列]

第4問[場合の数・数列]

第4問

非負整数 nn について,3種類の文字 ,{},\{\} から成る文字列 wnw_n を以下のように定める。

w0={}w_0=\{ \}

wn={w0,,wn1}w_n = \{ w_0, \dots , w_{n-1} \}

例えば w1={w0}={{}}w2={w0,w1}={{},{{}}}w3={w0,w1,w2}={{},{{}},{{},{{}}}}\begin{aligned} w_1 &= \{w_0\} = \{ \{\} \}\\ w_2 &= \{w_0,w_1\}\\ &= \{\{\} , \{ \{\} \} \}\\ w_3 &= \{ w_0,w_1,w_2 \}\\ &= \{ \{\} , \{ \{\} \} , \{\{\} , \{ \{\} \} \} \} \end{aligned} となる。

(1) wnw_n の文字数を lnl_n で表す。lnl_n を求めよ。

(2) wnw_n に含まれる ,{},\{\} の数をそれぞれ an,bn,cna_n,b_n,c_n とする。an,bn,cna_n,b_n,c_n を求めよ。

(3) wnw_n にあらわれる文字を左から vn(1),vn(2),,vn(ln)v_n (1) , v_n (2) , \cdots , v_n (l_n) とおく。1i<jln1 \leqq i < j \leqq l_n であり,vn(i)vn(j)v_n (i) v_n (j){}\{\} となる2整数 (i,j)(i,j) の選び方の総数を xnx_n とする。

例えば w0={}w_0 = \{\} より v0(1)={v_0 (1) = \{v0(2)=}v_0 (2) = \} であり,x0=1x_0 = 1 である。

w1={{}}w_1 = \{\{\}\} より v1(1)={v_1 (1) = \{v1(2)={v_1 (2) =\{v1(3)=}v_1 (3) =\}v1(4)=}v_1 (4) = \} である。このとき v1(1)v1(3)v_1 (1) v_1 (3)v1(1)v1(4)v_1 (1) v_1 (4)v1(2)v1(3)v_1 (2) v_1 (3)v1(2)v1(4)v_1 (2) v_1 (4){}\{\} となるため,x1=4x_1 = 4 である。

xnx_n を求めよ。

場合の数と数列の問題です.このような数え上げの問題には,漸化式を立てて計算することが基本的な方針となります.

この問題に出てくるxn=i=0n1xi+(nの式)x_n=\sum_{i=0}^{n-1}x_i+(n \text{の式})というタイプの漸化式には,ひとつずらして差をとる方法が有効です.

第4問(1)

文字列 SS の長さを L(S)L(S) で表すことにすると,n1n \geq 1 のとき ln=L(wn)=L({w0,,wn1})=L(w0)++L(wn1)+2+(n1)=l0++ln1+n+1=n+1+i=0n1li \begin{aligned} l_n&=L(w_n)\\ &=L(\{w_0, \dots, w_{n-1}\})\\ &=L(w_0)+\cdots +L(w_{n-1})+2+(n-1)\\ &=l_0+\cdots+l_{n-1}+n+1\\ &=n+1+\sum_{i=0}^{n-1}l_i \end{aligned} となる.これとln+1=(n+1)+1+i=0nlil_{n+1}=(n+1)+1+\sum_{i=0}^n l_iとの差をとってln+1ln=ln+1l_{n+1}-l_n=l_n+1すなわちln+1+1=2(ln+1)l_{n+1}+1=2(l_{n}+1)n1n \geq 1 で成り立つ.(n=0n=0 では正しくないことに注意!)これとl1+1=4+1=5l_1+1=4+1=5を合わせると,n1n \geq 1 のときln=52n11l_n=5\cdot 2^{n-1}-1が成り立つ.以上より ln={52n11 (n1)2 (n=0)\begin{equation*}l_n= \left \{ \begin{array}{ll} 5\cdot 2^{n-1}-1 &(n \geq 1) \\ 2 &(n=0) \end{array} \right. \end{equation*} となる.

次に (2) です.an,bn,cna_n,b_n,c_n それぞれで漸化式を立ててもよいですが,(1) の結果と左右の括弧の対称性を使うと ana_n のみ計算すればよいことがわかります.

第4問(2)

まず ana_n を計算する.文字列 SS に含まれるカンマ ,, の個数を A(S)A(S) で表すことにすると,n1n \geq 1 のとき an=A(wn)=A({w0,,wn1})=A(w0)++A(wn1)+(n1)=(n1)+i=0n1ai \begin{aligned} a_n&=A(w_n)\\ &=A(\{w_0, \dots, w_{n-1}\})\\ &=A(w_0)+\cdots+A(w_{n-1})+(n-1)\\ &=(n-1)+\sum_{i=0}^{n-1}a_i \end{aligned} となる.これとan+1=n+i=0naia_{n+1}=n+\sum_{i=0}^na_iの差をとってan+1an=an+1a_{n+1}-a_n=a_n+1すなわちan+1+1=2(an+1)a_{n+1}+1=2(a_n+1)n1n \geq 1 で成り立つ.これとa1+1=0+1=1a_1+1=0+1=1を合わせると,n1n \geq 1 のときan=2n11a_n=2^{n-1}-1が成り立つ.以上より an={2n11 (n1)0 (n=0)\begin{equation*}a_n= \left \{ \begin{array}{ll} 2^{n-1}-1 &(n \geq 1) \\ 0 &(n=0) \end{array} \right. \end{equation*} となる.

また定義よりln=an+bn+cnl_n=a_n+b_n+c_nであり,wnw_n の中に左括弧 {\{ と右括弧 }\} は必ずペアで出現するからbn=cnb_n=c_nが成り立つ.よって n1n \geq 1 のとき bn=cn=12(lnan)=12(52n11(2n11))=2n \begin{aligned} b_n=c_n&=\frac{1}{2} (l_n-a_n)\\ &=\frac{1}{2}\left(5 \cdot 2^{n-1}-1-(2^{n-1}-1)\right)\\ &=2^n \end{aligned} となる.これは n=0n=0 でも正しいから bn=cn=2nb_n=c_n=2^nである.

最後に (3) です.漸化式を立てるという原則から,nnが小さい場合の結果をうまく使えるようなやり方で文字の選び方を数えます.すると,wn={w0,,wn1}w_n=\{w_0,\dots,w_{n-1}\}から

  • 左右の括弧 {}\{\} を同じ wiw_i の中で選ぶ

もしくは

  • i<ji < j として wiw_i から左括弧 {\{ を,wjw_j から右括弧 }\} を選ぶ

という場合分けをして計算すればよさそうです.1つ目の場合は nn が小さい場合の結果からわかり,2つ目の場合は (2) で数えた {\{}\} の個数を使えば計算できます.

実際にはこれに加えて wnw_n の左端の {\{ と右端の }\} も考慮する必要があることから,左括弧 {\{ の位置で場合分けします.

第4問(3)

n1n \geq 1 のとき,wn={w0,,wn1}w_n=\{ w_0, \dots , w_{n-1} \}と書ける.条件を満たすような2文字の選び方を,左括弧 {\{ の位置で場合分けして数える.

  • {w0,,wn1}\{ w_0, \dots , w_{n-1} \} の左端の {\{ を選ぶとき

右括弧 }\}wnw_n に含まれるものならどれでもいいので,選び方は cn  通りc_n \; \text{通り}である.

  • {w0,,wn1}\{ w_0, \dots , w_{n-1} \}wiw_i の中の {\{ を選ぶとき

{}\{\} の作り方としてあり得るのは

  1. wiw_i の中で {}\{\} を作る」

もしくは

  1. wiw_i から {\{ を選び, wiw_i より右側の,wi+1,,wn1},w_{i+1},\dots, w_{n-1}\}の部分から }\} を選ぶ」

のどちらかである.それぞれの選び方はxi  通りx_i \; \text{通り}bi(ci+1++cn1+1)  通りb_i \cdot (c_{i+1}+\cdots +c_{n-1}+1) \; \text{通り} である.

以上を足し合わせることで,n1n \geq 1 のとき xn=cn+i=0n1{xi+bi(ci+1++cn1+1)}=2n+i=0n12i(2i+1++2n1+1)+i=0n1xi \begin{aligned} x_n&=c_n+\sum_{i=0}^{n-1}\left\{x_i+b_i \cdot (c_{i+1}+\cdots +c_{n-1}+1)\right\}\\ &=2^n + \sum_{i=0}^{n-1}2^i\cdot\left(2^{i+1}+\cdots+2^{n-1}+1 \right)+\sum_{i=0}^{n-1}x_i \end{aligned} が成り立つ.これとxn+1=2n+1+i=0n2i(2i+1++2n1+2n+1)+i=0nxix_{n+1}=2^{n+1} + \sum_{i=0}^{n}2^i\cdot\left(2^{i+1}+\cdots+2^{n-1}+2^n+1 \right)+\sum_{i=0}^nx_iの差をとると xn+1xn=2n+12n+i=0n12i2n+2n1+xn=2n+1+2n2n121+xn=xn+2n(2n+1) \begin{aligned} x_{n+1}-x_n&=2^{n+1}-2^n+\sum_{i=0}^{n-1}2^i\cdot2^n + 2^n \cdot 1 + x_n\\ &= 2^{n+1}+2^n\cdot \frac{2^n-1}{2-1}+x_n\\ &=x_n+2^n(2^n+1) \end{aligned} となるからxn+1=2xn+2n(2n+1)x_{n+1}=2x_n+2^n(2^n+1)n1n \geq 1 で成り立つ.また n=0n=0 のときも x0=1,x1=4x_0=1,x_1=4 だから正しい. xn+12n+1=xn2n+12(2n+1)\frac{x_{n+1}}{2^{n+1}}=\frac{x_n}{2^n}+\frac{1}{2}(2^n+1)と変形することで n0n \geq 0 のとき xn2n=x020+i=0n112(2i+1)=1+122n121+12n=1+12(2n1+n)=12(2n+n+1) \begin{aligned} \frac{x_n}{2^n}&=\frac{x_0}{2^0}+\sum_{i=0}^{n-1}\frac{1}{2}(2^i+1)\\ &=1+\frac{1}{2}\cdot\frac{2^n-1}{2-1}+\frac{1}{2}n\\ &=1+\frac{1}{2}(2^n-1+n)\\ &=\frac{1}{2}(2^n+n+1) \end{aligned} となる.よってxn=(2n+n+1)  2n1x_n=(2^n+n+1)\;2^{n-1}である.

略解

(1) ln={52n11(n1)2(n=0)l_n = \begin{cases} 5 \cdot 2^{n-1} - 1 & (n \geqq 1)\\ 2 & (n=0) \end{cases}

(2) an={2n11(n1)0(n=0)bn=2ncn=2n\begin{aligned} a_n &= \begin{cases} 2^{n-1} - 1 & (n \geqq 1)\\ 0 & (n=0) \end{cases}\\ b_n &= 2^n\\ c_n &= 2^n \end{aligned}

(3)

xn=(2n+n+1)  2n1 x_n = (2^n+n+1) \; 2^{n-1}

人気記事