トップ› 北海道大学› 1973年› 文系第3問

北海道大学 1973年文系第3問解説

方針・初手

(1) 辞書式配列の考え方を用いて、百の位の数で大きく場合分けを行い、条件を満たす数を数え上げる。

(2) 差が 2 以下である異なる 2 数の組は、差が 1 の場合と差が 2 の場合に分けられる。それぞれの組について積の逆数をつくり、シグマ記号を用いて総和の式を立てる。計算には部分分数分解を用いる。

解法1

(1) 3桁の整数のうち、654 より小さいものを百の位の数字で場合分けして数える。

(i) 百の位が 1, 2, 3, 4, 5 のとき百の位の数字の選び方は 5 通りある。十の位と一の位は、選んだ 1 つ以外の残りの 8 個の数字から異なる 2 個を選んで並べるので、その方法は

$$ {}_8\mathrm{P}_2 = 8 \times 7 = 56 \text{ 通り} $$

よって、この場合は

$$ 5 \times 56 = 280 \text{ 個} $$

(ii) 百の位が 6 のとき十の位の数字でさらに場合分けをする。

(ア) 十の位が 1, 2, 3, 4 のとき十の位の数字の選び方は 4 通りある。一の位は、残りの 7 個の数字から 1 個を選ぶので 7 通りある。よって、この場合は

$$ 4 \times 7 = 28 \text{ 個} $$

(イ) 十の位が 5 のとき百の位が 6、十の位が 5 であり、すでにこの 2 つの数字は使われている。 654 より小さくなるためには、一の位は 4 より小さい数字でなければならない。残りの数字のうち、条件を満たす一の位の数字は 1, 2, 3 のいずれかである。よって、この場合は

$$ 3 \text{ 個} $$

(i), (ii) より、求める整数の個数は

$$ 280 + 28 + 3 = 311 \text{ 個} $$

(2) 選んだ異なる 2 数を $k, j$（$k < j$）とする。条件より $j - k \leqq 2$ であるから、$j - k = 1$ または $j - k = 2$ である。

(i) $j - k = 1$ のとき $(k, j) = (k, k+1)$ であり、取り得る $k$ の範囲は $1 \leqq k \leqq n-1$ である。これらの積の逆数の総和を $S_1$ とすると

$$ S_1 = \sum_{k=1}^{n-1} \frac{1}{k(k+1)} $$

部分分数分解を用いて計算すると

$$ \begin{aligned} S_1 &= \sum_{k=1}^{n-1} \left( \frac{1}{k} - \frac{1}{k+1} \right) \\ &= \left( \frac{1}{1} - \frac{1}{2} \right) + \left( \frac{1}{2} - \frac{1}{3} \right) + \cdots + \left( \frac{1}{n-1} - \frac{1}{n} \right) \\ &= 1 - \frac{1}{n} \end{aligned} $$

(ii) $j - k = 2$ のとき $(k, j) = (k, k+2)$ であり、取り得る $k$ の範囲は $1 \leqq k \leqq n-2$ である。これらの積の逆数の総和を $S_2$ とすると

$$ S_2 = \sum_{k=1}^{n-2} \frac{1}{k(k+2)} $$

部分分数分解を用いて計算する。ここで、条件より $n \geqq 4$ であるから、$n-2 \geqq 2$ となり、項の相殺を過不足なく考えることができる。

$$ \begin{aligned} S_2 &= \sum_{k=1}^{n-2} \frac{1}{2} \left( \frac{1}{k} - \frac{1}{k+2} \right) \\ &= \frac{1}{2} \left\{ \left( \frac{1}{1} - \frac{1}{3} \right) + \left( \frac{1}{2} - \frac{1}{4} \right) + \left( \frac{1}{3} - \frac{1}{5} \right) + \cdots + \left( \frac{1}{n-2} - \frac{1}{n} \right) \right\} \end{aligned} $$

和の括弧内は、初めの 2 項の正の部分と、終わりの 2 項の負の部分が打ち消されずに残るため

$$ \begin{aligned} S_2 &= \frac{1}{2} \left( 1 + \frac{1}{2} - \frac{1}{n-1} - \frac{1}{n} \right) \\ &= \frac{3}{4} - \frac{1}{2(n-1)} - \frac{1}{2n} \end{aligned} $$

(i), (ii) より、求めるすべての総和は $S_1 + S_2$ であるから

$$ \begin{aligned} S_1 + S_2 &= \left( 1 - \frac{1}{n} \right) + \left( \frac{3}{4} - \frac{1}{2(n-1)} - \frac{1}{2n} \right) \\ &= \frac{7}{4} - \frac{3}{2n} - \frac{1}{2(n-1)} \\ &= \frac{7n(n-1) - 6(n-1) - 2n}{4n(n-1)} \\ &= \frac{7n^2 - 15n + 6}{4n(n-1)} \end{aligned} $$

解説

(1) は順列における辞書式配列の典型的な数え上げ問題である。大きい位から順に条件を固定し、残りの自由度を計算していくのが確実な手法である。

(2) は階差が一定である数列の積の逆数和を求める問題である。部分分数分解 $\frac{1}{k(k+a)} = \frac{1}{a} \left( \frac{1}{k} - \frac{1}{k+a} \right)$ を用いて、隣接する項同士で符号が逆になるペアを作り出し、相殺させる手法が有効である。特に差が 2 の場合は、前後に 2 項ずつ残ることに注意して計算を進める。