東北大学 1998年度 後期日程 第2次学力試験理系（後期）数学 第2問

(1)
まず $n=2$ のときは、最大の長さが $1$ となる列は $+-,-+$ の2通りであるから $$P(1)={\displaystyle \frac{2}{4}}={\displaystyle \frac{1}{2}}$$ である。

以下 $n\geqq 3$ とする。最大の長さが $n-1$ となるには、長さ $n-1$ の同符号のブロックが1つあり、残り1個だけが反対の符号でなければならない。反対の符号が左端にある場合と右端にある場合、さらに全体の符号を反転した場合があるので、該当する列は4通りである。したがって $$P(n-1)={\displaystyle \frac{4}{2^n}}={\displaystyle \frac{1}{2^{n-2}}}$$ である。

(2)
任意の符号列について、すべての $+$ と $-$ を入れ替える。この操作をしても、同符号が続く部分の長さは変わらない。また、入れ替えた後の列がもとの列と一致することはない。したがって、最大の長さが $k$ である列全体は2個ずつ組に分けられる。よって、その個数である $2^{n}P(k)$ は偶数である。

(3)
まず $k=n$ のときは、すべて $+$ またはすべて $-$ の2通りなので $P(n)={\displaystyle \frac{2}{2^n}}$ である。

次に $n\mathrm{/}2<k<n$ とする。このとき長さ $k$ のブロックは2つ同時には存在できない。長さ $k$ のブロックの符号を先に決めると2通りである。ブロックの左に $L$ 個、右に $R$ 個の文字があるとすると $L+R=n-k$ である。ブロックのすぐ左またはすぐ右に文字がある場合、その文字はブロックと反対の符号でなければならない。残りの文字は全部で $n-k-1$ 個または $n-k-2$ 個となり、どのように並べても長さ $k$ を超えるブロックはできない。 $m=n-k$ とおく。ブロックが端にある場合は2か所あり、それぞれ $2\cdot 2^{m-1}$ 通りである。ブロックが端でない場合は $m-1$ か所あり、それぞれ $2\cdot 2^{m-2}$ 通りである。したがって個数は $$2\cdot 2\cdot 2^{m-1}+(m-1)\cdot 2\cdot 2^{m-2}=(m+3)2^{m-1}$$ である。つまり $$2^{n}P(k)=(n-k+3)2^{n-k-1}$$ である。

最後に、$n$ が偶数で $k=n\mathrm{/}2$ の場合を考える。このとき上と同じ数え方では、長さ $k$ のブロックが2つある列$$\underset{k}{\underbrace{++\cdots +}}\underset{k}{\underbrace{--\cdots -}},\underset{k}{\underbrace{--\cdots -}}\underset{k}{\underbrace{++\cdots +}}$$をそれぞれ2回数えている。したがって、$m=k$ として得られる $(k+3)2^{k-1}$ から2を引き、$$2^{n}P(k)=(k+3)2^{k-1}-2=2\{(k+3)2^{k-2}-1\}$$ である。

以上より、$k\geqq n\mathrm{/}2$ では$$P(k)=\{\begin{array}{ll}{\displaystyle \frac{2}{2^n}},& k=n,\\ {\displaystyle \frac{(n-k+3)2^{n-k-1}}{2^n}},& {\displaystyle \frac{n}{2}}<k<n,\\ {\displaystyle \frac{(k+3)2^{k-1}-2}{2^n}},& n\text{が偶数で }k={\displaystyle \frac{n}{2}}\mathrm{.}\end{array}$$である。

符号列を連続ブロック長の組、すなわちnの合成と対応させる。最初の符号2通りを掛け、k≥n/2では長さkの部分が高々1つであることから合成を数える。

符号列は「最初の符号」と「各連続ブロックの長さ」によって一意に決まる。したがって符号列は、$n$ の合成1つにつき最初の符号2通りに対応する。

(1)

$n\geqq 3$ では合成の最大部分が $n-1$ となるものは$$(n-1,1),(1,n-1)$$の2つである。最初の符号を掛けて4列だから$$P(n-1)={\displaystyle \frac{4}{2^n}}\mathrm{.}$$$n=2$ では $P(1)=1\mathrm{/}2$ である。

(2)

最初の符号は常に2通りなので、どのブロック長の合成に対しても符号列は2列ずつ現れる。よって $2^{n}P(k)$ は偶数である。

(3)

$n\mathrm{/}2<k<n$ とし、$m=n-k$ と置く。長さ $k$ の部分は1つだけである。その左側の和を $j$、右側を $m-j$ とする。正整数 $s$ の合成数は $2^{s-1}$、0の合成は空列1通りなので、印を付けた部分 $k$ の置き方は$$2\cdot 2^{m-1}+(m-1)2^{m-2}=(m+3)2^{m-2}\mathrm{.}$$最初の符号2通りを掛け、$$2^{n}P(k)=(m+3)2^{m-1}\mathrm{.}$$$n=2k$ のときは合成 $(k,k)$ が印を付ける部分の選択により2回数えられるので、符号列2通りを引く。したがって$$P(k)=\{\begin{array}{ll}{\displaystyle \frac{2}{2^n}}& (k=n),\\ {\displaystyle \frac{(n-k+3)2^{n-k-1}}{2^n}}& (n\mathrm{/}2<k<n),\\ {\displaystyle \frac{(k+3)2^{k-1}-2}{2^n}}& (n=2k)\mathrm{.}\end{array}$$