トップ› 名古屋大学› 2000年› 文系第2問

名古屋大学 2000年文系第2問解説

方針・初手

不等式 $0 \leqq a \leqq 2b \leqq c \leqq n$ を満たす整数の組を考えるにあたり、真ん中にある $b$ の値を固定して考えるのが基本です。$b$ を固定すると、$a$ と $c$ はそれぞれ独立した不等式を満たす整数として個数を数え上げることができます。全体としては、$b$ のとりうる範囲でそれらの個数を足し合わせることで総数を求めます。

解法1

条件 $0 \leqq a \leqq 2b \leqq c \leqq n$ を満たす整数の組 $(a, b, c)$ を求める。

ある整数 $b$ を固定したとき、整数 $a, c$ はそれぞれ独立に $0 \leqq a \leqq 2b$ $2b \leqq c \leqq n$ を満たせばよい。これを満たす整数 $a$ は $0, 1, \dots, 2b$ の $2b+1$ 個ある。また、これを満たす整数 $c$ は $2b, 2b+1, \dots, n$ の $n - 2b + 1$ 個ある。 $a$ と $c$ は互いに無関係に選べるため、$b$ を固定したときの組 $(a, c)$ の個数は $(2b+1)(n-2b+1)$ 個となる。

不等式 $0 \leqq 2b \leqq n$ より、$b$ のとりうる範囲は $0 \leqq b \leqq \frac{n}{2}$ を満たす整数である。

(1)

$n=5$ のとき、$0 \leqq b \leqq \frac{5}{2}$ より $b = 0, 1, 2$ である。求める個数 $P(5)$ は、各 $b$ に対する個数を足し合わせて、

$$ \begin{aligned} P(5) &= \sum_{b=0}^{2} (2b+1)(5-2b+1) \\ &= \sum_{b=0}^{2} (2b+1)(6-2b) \end{aligned} $$

$b=0$ のとき、$1 \times 6 = 6$ $b=1$ のとき、$3 \times 4 = 12$ $b=2$ のとき、$5 \times 2 = 10$

したがって、

$$ P(5) = 6 + 12 + 10 = 28 $$

(2)

$n$ が奇数のとき、$b$ のとりうる範囲は $0 \leqq b \leqq \frac{n-1}{2}$ となる。 $N = \frac{n-1}{2}$ とおくと、$n = 2N+1$ であり、和をとる範囲は $0 \leqq b \leqq N$ である。 $b$ を固定したときの個数は、

$$ (2b+1)(n-2b+1) = (2b+1)(2N+1-2b+1) = 2(2b+1)(N-b+1) $$

となるため、$P(n)$ を $N$ を用いて計算する。

$$ \begin{aligned} P(n) &= \sum_{b=0}^{N} 2(2b+1)(N-b+1) \\ &= 2 \sum_{b=0}^{N} \{ -2b^2 + (2N+1)b + N + 1 \} \\ &= 2 \left( -2 \sum_{b=0}^{N} b^2 + (2N+1) \sum_{b=0}^{N} b + (N+1) \sum_{b=0}^{N} 1 \right) \\ &= 2 \left\{ -2 \cdot \frac{N(N+1)(2N+1)}{6} + (2N+1) \cdot \frac{N(N+1)}{2} + (N+1)^2 \right\} \\ &= 2(N+1) \left\{ -\frac{N(2N+1)}{3} + \frac{N(2N+1)}{2} + N+1 \right\} \\ &= 2(N+1) \left\{ \frac{N(2N+1)}{6} + \frac{6(N+1)}{6} \right\} \\ &= \frac{N+1}{3} (2N^2 + N + 6N + 6) \\ &= \frac{1}{3} (N+1)(2N^2 + 7N + 6) \\ &= \frac{1}{3} (N+1)(N+2)(2N+3) \end{aligned} $$

ここで、$N = \frac{n-1}{2}$ であるから、

$$ N+1 = \frac{n+1}{2}, \quad N+2 = \frac{n+3}{2}, \quad 2N+3 = n+2 $$

これらを代入して、

$$ P(n) = \frac{1}{3} \cdot \frac{n+1}{2} \cdot \frac{n+3}{2} \cdot (n+2) = \frac{(n+1)(n+2)(n+3)}{12} $$

解法2

(2) について、重複組合せを用いた別解を示す。

$n$ を奇数とする。$0 \leqq a \leqq 2b \leqq c \leqq n$ を満たす組 $(a, b, c)$ において、非負整数 $x, y, z, w$ を次のように定める。

$$ x = a, \quad y = 2b - a, \quad z = c - 2b, \quad w = n - c $$

これらを辺々足し合わせると、

$$ x + y + z + w = a + (2b - a) + (c - 2b) + (n - c) = n $$

となる。また、$x + y = 2b$ であるため、$x + y$ は偶数である。逆に、$x + y + z + w = n$ かつ $x + y$ が偶数である非負整数の組 $(x, y, z, w)$ が与えられれば、$b = \frac{x+y}{2}, a = x, c = x+y+z$ とすることで、条件を満たす組 $(a, b, c)$ が一意に定まる。したがって、$P(n)$ は「$x+y+z+w=n$ を満たす非負整数解のうち、$x+y$ が偶数であるものの個数」に等しい。

$x+y+z+w=n$ を満たす非負整数解の総数は、異なる4種類のものから重複を許して $n$ 個選ぶ組合せに等しく、

$$ {}_{4}\mathrm{H}_{n} = {}_{n+4-1}\mathrm{C}_{n} = {}_{n+3}\mathrm{C}_{3} = \frac{(n+3)(n+2)(n+1)}{6} $$

である。ここで、$X = x+y, Y = z+w$ とおくと $X+Y=n$ である。方程式 $x+y=X$ の非負整数解 $(x, y)$ の個数は $X+1$ 個、方程式 $z+w=Y$ の非負整数解 $(z, w)$ の個数は $Y+1$ 個であるから、$X$ の値を一つ固定したときの $(x, y, z, w)$ の組の個数は $(X+1)(n-X+1)$ 個である。

$X$ が偶数となる場合の総数を $S_{\text{even}}$、$X$ が奇数となる場合の総数を $S_{\text{odd}}$ とおく。$X$ の最大値は奇数 $n$ なので、$X$ が奇数となるとき $X = 2k+1$ $\left(0 \leqq k \leqq \frac{n-1}{2}\right)$ とおける。

$$ S_{\text{odd}} = \sum_{k=0}^{\frac{n-1}{2}} \{ (2k+1)+1 \} \{ n-(2k+1)+1 \} = \sum_{k=0}^{\frac{n-1}{2}} (2k+2)(n-2k) $$

ここで、$l = \frac{n-1}{2} - k$ と変換する。$k$ が $0$ から $\frac{n-1}{2}$ まで動くとき、$l$ は $\frac{n-1}{2}$ から $0$ まで動く。

$$ 2k+2 = 2 \left( \frac{n-1}{2} - l \right) + 2 = n - 2l + 1 $$

$$ n-2k = n - 2 \left( \frac{n-1}{2} - l \right) = 2l + 1 $$

となるため、

$$ S_{\text{odd}} = \sum_{l=0}^{\frac{n-1}{2}} (n-2l+1)(2l+1) $$

と変形できる。これは $X=2l$ （偶数）として計算したときの和 $S_{\text{even}}$ そのものである。よって、$S_{\text{even}} = S_{\text{odd}}$ が成り立つ。 $S_{\text{even}} + S_{\text{odd}} = {}_{n+3}\mathrm{C}_{3}$ より、

$$ P(n) = S_{\text{even}} = \frac{1}{2} {}_{n+3}\mathrm{C}_{3} = \frac{(n+1)(n+2)(n+3)}{12} $$

解説

不等式の条件式から特定の文字を固定して数え上げる、場合の数の典型的な問題です。本問では真ん中にある $b$ を固定することで、$a$ と $c$ の条件が互いに独立になり、単純な積の形で個数を表現できることが最大のポイントです。 (2)のシグマ計算はやや煩雑になりますが、$\frac{n-1}{2}$ を別の文字に置き換えて計算ミスを防ぐ工夫が有効です。また、解法2のように重複組合せ（${}_{n}\mathrm{H}_{r}$）に帰着させる手法は、差を文字で置くという発想が必要ですが、計算量を大幅に減らすことができる強力な解法です。