2003　東京工業大学　後期小論文第５類MathJax

【２】　以下の収支列と呼ばれる数列についての説明文を読み，問１から問９に答えよ．

　$n$を$n\geqq 1$である整数とする．$n$個の$+1$と，$n$個の$-1$を自由に並べて得られる項数$2n$の数列を，$2n$日間の収支列と呼ぶ．$2n$日間の収支列において，$1$番目の項，$2$番目の項，$\cdots \text{，}2n$番目の項を，それぞれ$1$日目の収支，$2$日目の収支，$\cdots \text{，}2n$日目の収支と呼ぶ．$j$を$1\leqq j\leqq 2n$である整数として，$1$日目から$j$日目までの収支の合計を$j$日目の残高と呼ぶ．$2n$日間の収支列において，どの日の残高も$0$以上の場合，健全な収支列と呼び，そうでない場合，不健全な収支列と呼ぶ．

　たとえば，次の数列

$+1\text{，}+1\text{，}-1\text{，}-1$

は$4$日間の収支列で，残高が，$1$日目は$+1\text{，}2$日目は$+2\text{，}3$日目は$+1\text{，}4$日目は$0$で，どの日も残高が$0$以上なので，健全な収支列である．次の数列

$+1\text{，}-1\text{，}-1\text{，}+1$

も$4$日間の収支列であるが，$3$日目の残高が$-1$となるので，不健全な残高である．

　収支列は次のような性質を持つ．

• 【性質１】$2n$日間の健全な収支列では，$1$日目の収支列は$+1\text{，}$残高は$+1$で，$2n$日目の収支は$-1\text{，}$残高は$0$である．$2n$日間の健全な収支列では，残高がはじめて$0$となる日が必ず存在する．健全な収支列で残高がはじめて$0$となる日を$k$日目とすると，$1$日目から$(k-1)$日目まで残高は，いつも$1$以上である．特に$k\geqq 4$の場合，$2$日目から$(k-1)$日目までの収支を並べて作られる項数$(k-2)$の数列

  $2$日目の収支，$\cdots \text{，}(k-1)$日目の収支

  は$(k-2)$日間の健全な収支列となる．
• 【性質２】$2n$日間の不健全な収支列では，残高がはじめて$-1$となる日が必ず存在する．不健全な収支列で，残高がはじめて$-1$となる日を$t$日目とすると，$t\geqq 3$の場合，$1$日目から$(t-1)$日目までの残高は，いつも$0$以上である．
• 【性質３】$2$日間の収支列は全部で$2$通りあり，そのうち健全な収支列の総数は$1\text{，}$不健全な収支列の総数は$1$である．$2n$日間の健全な収支列が与えられた場合，次の数列

  $+1\text{，}2n$日間の健全な収支列，$-1$

  は$2(n+1)$日間の健全な収支列となる．また$m$を$m\geqq 1$である整数として，$2m$日間の健全な収支列も与えられた場合，次の数列

  $2n$日間の健全な収支列，$2m$日間の健全な収支列

  は$2(n+m)$日間の健全な収支列となる．

問１　$4$日間の健全な収支列をすべて示せ．

問２　$6$日間のすべての健全な収支列を，$4$日間以下の健全な収支列を利用して表したい．たとえば，$6$日間の健全な収支列すべては，$2$日間の健全な収支列と$4$日間の健全な収支列を並べるだけで表せるものと仮定してみよう．すなわち，$6$日間の健全な収支列は

$2$日間の健全な収支列，$4$日間の健全な収支列

および

$4$日間の健全な収支列，$2$日間の健全な収支列

ですべて表せると仮定しよう．

　実際にこの表し方で数え上げてみると，重複や見落としが発生する．この表し方で，見落される$6$日間の健全な収支列をすべて示せ．

問３　$6$日間の健全な収支列すべてを，重複や見落しなく数え上げたい．$6$日間の健全な収支列すべては，残高がはじめて$0$となる日が何日目であるかで分類すると，$4$日間以下の健全な収支列を利用して表すことができる．どのように表せばよいか示せ．解答は，

$2$日目の場合：$+1\text{，}-1\text{，}4$日間の健全な収支列

などのように，場合分けして記述せよ．

問４　問３の健全な収支列の表し方を用いて， $6$日間の健全な収支列の総数を求めよ．

問５　不健全な収支列の総数は，収支列の総数と健全な収支列の総数を利用して求めることができる．この求め方で，$8$日間の不健全な収支列の総数を求めよ．

問６　$10$日間の不健全な収支列すべてを、重複や見落としなく数え上げたい．$10$日間の不健全な収支列すべては，残高がはじめて$-1$となる日が何日目であるかで分類すると，$8$日間以下の健全な収支列を利用して表すことができる．どのように表せばよいか示せ．解答は問３の解答の仕方にならって，場合分けして記述せよ．

問７　問６の不健全な収支列の表し方を用いて，$10$日間の不健全な収支列の総数を求めよ．

問８　一般の$2n$日間の不健全な収支列の総数を求めたい．直接に数え上げることは大変なので，不健全な収支列に以下の変換操作を施して，項数$2n$の数列を作り，この変換後の数列の総数を数え上げることにする．

【変換操作】一般の$2n$日間の不健全な収支列に対して，$1$日目から，残高がはじめて$-1$となる日までの収支の値の符号を反転させる．残りの日々の収支の値は変更しない．

たとえば，次の$4$日間の不健全な収支列

$+1\text{，}-1\text{，}-1\text{，}+1$

に対して変換操作を行ってみよう．残高が$3$日目ではじめて$-1$となるので，$1$日目から$3$日目までの毎日の収支の値は符号を反転させ，$4$日目は収支の値を変更しない．変換後の数列は，次の数列となる．

$-1\text{，}+1\text{，}+1\text{，}+1$

一般に，変換後の数列に対し，対応する変換前の数列はちょうど$1$つ存在する．変換後の数列から，変換前の数列を求める方法を示せ．

問９　$2n$日間の不健全な収支列すべてに，問８の変換操作を施して得られる数列の集合は，どのような条件を満たす数列の集合か，その条件を示せ．さらに，この条件を利用して，$2n$日間の不健全な収支列の総数を表す式を導出せよ．