大阪大学 2003年度後期・理系数学後期第3問解答・解説

問題

1から $2 n$ のカードを一列に並べる。両隣（端では唯一の隣）が自分より小さいカードを極大と呼ぶ。

(1) $[2 n]$ のみが極大となる並べ方を求めよ。

(2) $[n], [2 n]$ のみが極大で、両者間の最小カードが $[k]$ となる並べ方を求めよ。

(3) $[n], [2 n]$ のみが極大となる総数を $P (n)$ とする。 $P (n) / a^{n}$ が0でない値に収束する $a$ と極限値を求めよ。

出典：大阪大学 2003年度後期日程第2次学力試験後期・理系後期第3問

方針

極大が一つなら列はそこまで増加し、その後減少する。(2)では二つの極大の順序を固定し、間の最小値 $k$ を谷として、各カードを左外側・下降部・上昇部・右外側のどこへ入れるか数える。各部で順序は単調性により一意に決まる。

解答

(1)

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

2^{2 n - 1}

通りである。

(2)

まず左から $[n], [2 n]$ の順に現れる場合を数える。列は

増加 \to [n] \to 減少 \to [k] \to 増加 \to [2 n] \to 減少

という形である。各カードをどの単調部分に入れるか決めれば、その部分での順序は一意に決まる。

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

2^{k - 1} 4^{n - k - 1} 2^{n - 1} = 2^{3 n - k - 4}

通りである。二つの極大の順序は2通りあるので

2^{3 n - k - 3} (1 ≦ k ≦ n - 1)

通りである。

(3)

(2)を $k = 1, \dots, n - 1$ について足すと

P (n) = k = 1 \sum n - 1 2^{3 n - k - 3} = 2^{3 n - 3} (1 - 2^{- (n - 1)}) = \frac{8 ^{n}}{8} - \frac{4 ^{n}}{4} .

したがって0でない有限値に収束するのは $a = 8$ のときであり

n \to \infty lim \frac{P ( n )}{8 ^{n}} = \frac{1}{8} .

大阪大学 2003年度後期・理系数学 後期 第3問

問題

方針

解答

(1)

(2)

(3)

大阪大学 2003年度
後期・理系数学後期第3問