トップ› 名古屋大学› 2020年› 文系第3問

名古屋大学 2020年文系第3問解説

方針・初手

長方形は各辺が座標軸に平行であるため、左下の頂点を $(x_1, y_1)$、右上の頂点を $(x_2, y_2)$ とおくと、長方形はこの2点の座標によって完全に決定される。長方形が領域 $D$ 内にあるための条件は、右上の頂点 $(x_2, y_2)$ が $D$ に含まれること、すなわち $x_2 + y_2 \le n$ を満たすことである。したがって、長方形の総数 $R(n)$ は、整数 $x_1, x_2, y_1, y_2$ が $$ 0 \le x_1 < x_2, \quad 0 \le y_1 < y_2, \quad x_2 + y_2 \le n $$ を満たす組 $(x_1, x_2, y_1, y_2)$ の個数に等しい。この条件をもとに、シグマ計算による和をとるか、条件式の形から組合せの問題に帰着させることで求めることができる。

解法1

(1)

右上頂点を $(X, Y)$ とすると、これを満たす整数は $X \ge 1, Y \ge 1, X+Y \le n$ である。この $(X, Y)$ を固定したとき、左下頂点 $(x_1, y_1)$ の選び方は、$0 \le x_1 \le X-1$ より $X$ 通り、$0 \le y_1 \le Y-1$ より $Y$ 通りあるので、長方形は $XY$ 個存在する。

$n=3$ のとき、$X+Y \le 3$ となる組 $(X,Y)$ と対応する長方形の個数は以下のようになる。

$(X,Y) = (1,1)$ のとき、$1 \times 1 = 1$ 個
$(X,Y) = (2,1)$ のとき、$2 \times 1 = 2$ 個
$(X,Y) = (1,2)$ のとき、$1 \times 2 = 2$ 個

これらを足し合わせて、 $$ R(3) = 1 + 2 + 2 = 5 $$

$n=4$ のとき、$X+Y \le 4$ となる組 $(X,Y)$ と対応する長方形の個数は以下のようになる。

$(X,Y) = (1,1)$ のとき、$1 \times 1 = 1$ 個
$(X,Y) = (2,1)$ のとき、$2 \times 1 = 2$ 個
$(X,Y) = (3,1)$ のとき、$3 \times 1 = 3$ 個
$(X,Y) = (1,2)$ のとき、$1 \times 2 = 2$ 個
$(X,Y) = (2,2)$ のとき、$2 \times 2 = 4$ 個
$(X,Y) = (1,3)$ のとき、$1 \times 3 = 3$ 個

これらを足し合わせて、 $$ R(4) = 1 + 2 + 3 + 2 + 4 + 3 = 15 $$

(2)

1つの辺が $x$ 軸上にある長方形は、底辺が $y=0$ にある長方形であるから、左下頂点の $y$ 座標は $y_1 = 0$ に固定される。右上の頂点を $(x_2, y_2)$ （ただし $x_2 \ge 1, y_2 \ge 1, x_2 + y_2 \le n$）と固定したとき、左下頂点 $(x_1, 0)$ の選び方は $0 \le x_1 \le x_2-1$ の $x_2$ 通りある。よって、$S(n)$ は $y_2$ を $k$ ($1 \le k \le n-1$) に固定したときの $x_2$ の総和となるので、

$$ \begin{aligned} S(n) &= \sum_{k=1}^{n-1} \sum_{x_2=1}^{n-k} x_2 \\ &= \sum_{k=1}^{n-1} \frac{1}{2}(n-k)(n-k+1) \end{aligned} $$

ここで $m = n-k$ とおくと、$k$ が $1$ から $n-1$ まで動くとき、$m$ は $n-1$ から $1$ まで動くので、

$$ \begin{aligned} S(n) &= \sum_{m=1}^{n-1} \frac{1}{2}m(m+1) \\ &= \frac{1}{6} \sum_{m=1}^{n-1} \{ m(m+1)(m+2) - (m-1)m(m+1) \} \\ &= \frac{1}{6}(n-1)n(n+1) \end{aligned} $$

(3)

長方形の底辺の $y$ 座標が $y=k$ ($0 \le k \le n-2$) であるものの数を考える。このとき、長方形の4頂点は $y \ge k, x \ge 0, x+y \le n$ の領域に含まれる。 $Y = y-k$ と座標を置き換えると、この領域は $Y \ge 0, x \ge 0, x+Y \le n-k$ となり、正の整数 $n-k$ に対する元の領域 $D$ と合同になる。この領域において底辺が $Y=0$（すなわち $y=k$）にある長方形の数は、(2)の定義より $S(n-k)$ に等しい。したがって、$R(n)$ は各 $k$ についての長方形の数の和として求められる。

$$ R(n) = \sum_{k=0}^{n-2} S(n-k) $$

$m = n-k$ とおくと、$k$ が $0$ から $n-2$ まで動くとき、$m$ は $n$ から $2$ まで動く。

$$ \begin{aligned} R(n) &= \sum_{m=2}^{n} S(m) \\ &= \sum_{m=2}^{n} \frac{1}{6}(m-1)m(m+1) \\ &= \frac{1}{24} \sum_{m=2}^{n} \{ (m-1)m(m+1)(m+2) - (m-2)(m-1)m(m+1) \} \\ &= \frac{1}{24}(n-1)n(n+1)(n+2) \end{aligned} $$

(4)

$R(n) = 1001$ より、

$$ \frac{1}{24}(n-1)n(n+1)(n+2) = 1001 $$

両辺に 24 を掛けて整理すると、

$$ (n-1)n(n+1)(n+2) = 24 \times 1001 $$

右辺を素因数分解して、連続する4つの整数の積の形に変形する。

$$ \begin{aligned} 24 \times 1001 &= 24 \times 7 \times 11 \times 13 \\ &= 2 \times 3 \times 4 \times 7 \times 11 \times 13 \\ &= 11 \times (3 \times 4) \times 13 \times (2 \times 7) \\ &= 11 \times 12 \times 13 \times 14 \end{aligned} $$

$n$ は正の整数であり、左辺は $n$ について単調増加であるから、これを満たす $n$ はただ1つ存在する。比較すると $n-1 = 11$ となるため、

$$ n = 12 $$

解法2

(2) および (3) については、長方形を構成する座標の条件式から変数を置き換えることで、重複組合せの問題に帰着させる別解がある。

長方形を決定する条件は、整数 $x_1, x_2, y_1, y_2$ が以下を満たすことである。

$$ 0 \le x_1 < x_2, \quad 0 \le y_1 < y_2, \quad x_2 + y_2 \le n $$

ここで、新しい変数 $z_1, z_2, z_3, z_4, z_5$ を次のように定義する。

$$ \begin{aligned} z_1 &= x_1 \\ z_2 &= x_2 - x_1 - 1 \\ z_3 &= y_1 \\ z_4 &= y_2 - y_1 - 1 \\ z_5 &= n - (x_2 + y_2) \end{aligned} $$

元の条件から、これら5つの変数はすべて $0$ 以上の整数（非負整数）である。これら5つの変数の和をとると、

$$ \begin{aligned} z_1 + z_2 + z_3 + z_4 + z_5 &= x_1 + (x_2 - x_1 - 1) + y_1 + (y_2 - y_1 - 1) + n - x_2 - y_2 \\ &= n - 2 \end{aligned} $$

となる。

(3)の別解

$R(n)$ は和が $n-2$ となる5つの非負整数 $(z_1, z_2, z_3, z_4, z_5)$ の組の総数に等しい。したがって、異なる5つのものから重複を許して $n-2$ 個選ぶ重複組合せの数として計算できる。

$$ \begin{aligned} R(n) &= {}_{5}H_{n-2} \\ &= {}_{n-2+5-1}C_{5-1} \\ &= {}_{n+2}C_{4} \\ &= \frac{(n+2)(n+1)n(n-1)}{4 \times 3 \times 2 \times 1} \\ &= \frac{1}{24}(n-1)n(n+1)(n+2) \end{aligned} $$

(2)の別解

$S(n)$ は、底辺が $x$ 軸上にある長方形の数であるから、条件に $y_1 = 0$ が加わる。これは変数変換において $z_3 = 0$ と固定することに相当する。したがって、$S(n)$ は和が $n-2$ となる4つの非負整数 $(z_1, z_2, z_4, z_5)$ の組の総数に等しい。

$$ \begin{aligned} S(n) &= {}_{4}H_{n-2} \\ &= {}_{n-2+4-1}C_{4-1} \\ &= {}_{n+1}C_{3} \\ &= \frac{(n+1)n(n-1)}{3 \times 2 \times 1} \\ &= \frac{1}{6}(n-1)n(n+1) \end{aligned} $$

解説

格子点や領域に関する計数問題であるが、各辺が座標軸に平行であることから、図形的な重なり合いを気にせず座標の選び方の問題に言い換えることが重要である。解法1のように、$y$ 座標の制約を変えながら平行移動の考え方を用いて $R(n)$ と $S(n)$ の関係性を見抜く解法は、問題の誘導に乗る素直な方針である。和の計算においては恒等式を用いた階差の形を作り出すと計算ミスを防ぎやすい。一方で、解法2で示した変数の置き換えによる組合せへの帰着（スラック変数の導入）は、不等式を方程式に変えて数え上げる際の強力な定石である。この発想を知っていると、シグマ計算を一切せずに瞬時に答えを導き出すことができるため、ぜひ習得しておきたい。