トップ› 大阪大学› 1972年› 文系第4問

大阪大学 1972年文系第4問解説

注意画像の一部が不鮮明で、特に「図形 $A_n, B_n$ の形状」を図示した部分が欠落しており読取りに不確実性がある。以下は文脈から「$A_n$ は第1行に $n-2$ 個、第2行に $2$ 個の正方形が左詰めで並んだ図形、$B_n$ は第1行に $n-1$ 個、第2行に $1$ 個の正方形が左詰めで並んだ図形」として解釈した場合の解答解説である。

方針・初手

与えられた条件 (i), (ii) は、各行を左から右へ、各列を上から下へ見たときに、入る数が単調増加になることを意味している。

このような制約がある場合、最も大きな数である $n$ は「自身の右にも下にも隣接するマスが存在しない位置」にしか入ることができない。この $n$ が入る場所を特定し、そのマスを取り除いた残りの図形がどのような形状になるかを考えることで、場合の数の漸化式を導出する。

解法1

(1)

図形 $A_n$ は、第1行に $n-2$ 個、第2行に $2$ 個のマスが左詰めで並んでいる。

条件 (i), (ii) より、最大の数である $n$ は、自身の右にも下にもマスが存在しない位置にのみ入れることができる。

$A_n$ においてそのようなマスは、第1行の右端（第 $n-2$ 列）と、第2行の右端（第 $2$ 列）の $2$ 箇所である。

$n \geqq 5$ のとき、$n-2 \geqq 3 > 2$ であるから、これらのマスは異なる列に存在し、互いに重なることはない。

したがって、$n$ を入れることができる正方形の選び方は $2$ 通りである。

(2)

(1) より、$A_n$ において数 $n$ を入れる位置は次の 2 つの場合に分けられる。

（i）数 $n$ を第1行の右端に入れた場合

このマスを除いた残りの $n-1$ 個のマスの形状は、第1行に $n-3$ 個、第2行に $2$ 個の正方形が並んだ図形となる。

これは図形 $A_{n-1}$ に他ならない。残りのマスに $1$ から $n-1$ までの数を条件を満たすように入れる方法は $f(n-1)$ 通りである。

（ii）数 $n$ を第2行の右端に入れた場合

このマスを除いた残りの $n-1$ 個のマスの形状は、第1行に $n-2$ 個、第2行に $1$ 個の正方形が並んだ図形となる。

これは図形 $B_{n-1}$ に他ならない。残りのマスに $1$ から $n-1$ までの数を条件を満たすように入れる方法は $g(n-1)$ 通りである。

（i）, （ii）の場合は互いに排反であり、これ以外に $n$ を入れる方法はないので、以下の漸化式が成り立つ。

$$ f(n) = f(n-1) + g(n-1) $$

(3)

まず $g(n)$ を求める。

図形 $B_n$ は第1行に $n-1$ 個、第2行に $1$ 個（第1列のみ）の正方形が並んだ形状である。

条件より、一番左上のマス（第1行第1列）には最小の数である $1$ が入る。

第2行第1列のマスには、$2$ から $n$ までの任意の数 $k$ を入れることができる。

$k$ を決定すると、残りの $n-2$ 個の数はすべて第1行の残りのマスに入るため、左から小さい順に入れるしかなく、その入れ方は $1$ 通りに決まる。

$k$ の選び方は $2$ から $n$ までの $n-1$ 通りあるので、

$$ g(n) = n - 1 $$

である。

次に $f(n)$ を求める。

(2) で示した関係式に $g(n-1) = (n-1) - 1 = n-2$ を代入すると、$n \geqq 5$ のとき

$$ f(n) - f(n-1) = n - 2 $$

となる。これは数列 $\{f(n)\}$ の階差数列が $n-2$ であることを示している。したがって、$n \geqq 5$ のとき

$$ f(n) = f(4) + \sum_{k=5}^{n} (k-2) $$

ここで $f(4)$ の値を求める。

図形 $A_4$ は第1行に $2$ 個、第2行に $2$ 個の正方形が並んだ $2 \times 2$ の形状である。

条件より、第1行第1列は最小の $1$、第2行第2列は最大の $4$ に確定する。

残った $2, 3$ の入れ方は、第1行第2列に $2$、第2行第1列に $3$ を入れるか、その逆かの $2$ 通りである。

よって $f(4) = 2$ である。これを代入して計算すると、

$$ f(n) = 2 + \sum_{k=5}^{n} (k-2) $$

$$ \sum_{k=5}^{n} (k-2) = 3 + 4 + \cdots + (n-2) = \frac{(n-4)(n+1)}{2} $$

$$ f(n) = 2 + \frac{n^2 - 3n - 4}{2} $$

$$ f(n) = \frac{n(n-3)}{2} $$

この式は $n=4$ のとき $f(4) = \frac{4 \cdot 1}{2} = 2$ となり、成り立つ。

よって、すべての $n \geqq 4$ について以下が成り立つ。

$$ f(n) = \frac{n(n-3)}{2} $$

解説

マス目に数字を単調増加になるように配置する、いわゆる「標準ヤング盤」を題材とした問題である。

このような問題では、最大の数（本問では $n$）が配置できる場所が限定されることに着目し、そのマスを取り除いた状態を考えて漸化式を立てるのが定石である。(1) がその強力な誘導になっており、$A_n$ に $n$ を入れた結果として $A_{n-1}$ と $B_{n-1}$ の2種類の図形が内部状態として現れることに気づければ、(2) の関係式は自然に導かれる。

$g(n)$ の導出については、$B_n$ に $n$ を入れる方法から $g(n) = g(n-1) + 1$ の漸化式を立てて解くことも可能であるが、本解答のように第2行第1列の数字を固定して直接数え上げる方が手早く確実である。