大阪大学 2003年度 後期日程 第2次学力試験理系（後期）数学 第3問

(1) $[2n]$ の左側は増加順、右側は減少順でなければ、途中に別の極大が生じる。逆にこの形なら極大は $[2n]$ だけである。残る $2n-1$ 枚を左側に置くか右側に置くかを選べば順序は一意だから$$2^{2n-1}$$通りである。

(2) まず左から $[n],[2n]$ の順に現れる場合を数える。列は$$\text{増加}\to [n]\to \text{減少}\to [k]\to \text{増加}\to [2n]\to \text{減少}$$という形である。各カードをどの単調部分に入れるか決めれば、その部分での順序は一意に決まる。

$1,\dots ,k-1$ は二つの極大の外側にしか置けず各2通り、$k+1,\dots ,n-1$ は四つの部分のどこにも置けて各4通り、$n+1,\dots ,2n-1$ は $[k]$ から $[2n]$ への上昇部か右外側の2通りである。したがって固定した順序では$$2^{k-1}{4}^{n-k-1}{2}^{n-1}=2^{3n-k-4}$$通りである。二つの極大の順序は2通りあるので$$2^{3n-k-3}(1\leqq k\leqq n-1)$$通りである。

(3) (2)を $k=1,\dots ,n-1$ について足すと$$\begin{array}{rl}{\displaystyle P(n)}& {\displaystyle =\sum _{k=1}^{n-1}{2}^{3n-k-3}=2^{3n-3}(1-2^{-(n-1)})}\\ {\displaystyle }& {\displaystyle ={\displaystyle \frac{8^n}{8}}-{\displaystyle \frac{4^n}{4}}\mathrm{.}}\end{array}$$したがって0でない有限値に収束するのは $a=8$ のときであり$$\underset{n\to \mathrm{\infty }}{\lim }{\displaystyle \frac{P(n)}{8^n}}={\displaystyle \frac{1}{8}}\mathrm{.}$$

(1) は頂点の左右へカードを振り分ける。(2) では最小値が $k$ の並べ方を $N_{n,k}$ とし、まず $k=n-1$ を数える。谷を1段下げるごとに、新しく中間値となるカードの配置先が2通りから4通りへ増えるので、個数が2倍になる。

(1)
$[2n]$ より左は増加、右は減少でなければ別の極大が生じる。残る $2n-1$ 枚を左右のどちらへ置くかを選べば各側の順序は一意なので$$2^{2n-1}$$通りである。

(2)
条件を満たし、2つの極大にはさまれた最小値が $k$ である並べ方の数を $N_{n,k}$ とする。

まず $k=n-1$ とする。$1,\dots ,n-2$ は2つの極大の外側の左右どちらか、$n+1,\dots ,2n-1$ は $[2n]$ に接続する2本の単調部分のどちらかへ置く。さらに $[n]$ と $[2n]$ の左右順が2通りある。各部分内の順序は一意だから$$N_{n,n-1}=2^{n-2}\cdot 2^{n-1}\cdot 2=2^{2n-2}\mathrm{.}$$谷の役割を $[k+1]$ から $[k]$ へ1段下げると、$[k]$ がもっていた外側2部分の選択はなくなる一方、$[k+1]$ は4つの単調部分へ置けるようになる。他のカードの選択肢は変わらないので、全体は $${\displaystyle \frac{4}{2}}=2$$ 倍になる。したがって$$N_{n,k}=2N_{n,k+1}\mathrm{.}$$これを繰り返すと$$N_{n,k}=2^{n-1-k}{N}_{n,n-1}=2^{3n-k-3}\mathrm{.}$$(3)$$\begin{array}{rl}{\displaystyle P(n)}& {\displaystyle =\sum _{k=1}^{n-1}{2}^{3n-k-3}}\\ {\displaystyle }& {\displaystyle =2^{3n-3}(1-2^{-(n-1)})}\\ {\displaystyle }& {\displaystyle ={\displaystyle \frac{8^n}{8}}-{\displaystyle \frac{4^n}{4}}\mathrm{.}}\end{array}$$したがって0でない有限値へ収束するのは$$a=8$$のときで、その極限は$$\underset{n\to \mathrm{\infty }}{\lim }{\displaystyle \frac{P(n)}{8^n}}={\displaystyle \frac{1}{8}}$$である。