トップ› 北海道大学› 1979年› 理系第3問

北海道大学 1979年理系第3問解説

方針・初手

求める三角形の残りの2辺の長さを $a, b$ とおき、$a \le b \le n$ として条件を整理する。三角形の成立条件から $a, b$ の満たすべき不等式を導き、それを満たす整数の組 $(a, b)$ の個数を数え上げる。数え上げの際は、一方の文字を固定して考える方針と、まず大小関係を無視して全体の組数を求めてから対称性を利用する方針が考えられる。

解法1

残りの2辺の長さを $a, b$ とおく。合同な三角形は同じものとみなすため、$a \le b$ としても一般性を失わない。条件より、他の2辺の長さは $n$ 以下であるから、$1 \le a \le b \le n$ が成り立つ。この3辺 $a, b, n$ が三角形を構成する条件は、 $$ a + b > n, \quad b + n > a, \quad n + a > b $$ である。$1 \le a \le b \le n$ より、$b + n > a$ と $n + a > b$ は常に成り立つ。したがって、考えるべき条件は $$ a + b > n \iff a + b \ge n + 1 $$ である。以上より、満たすべき条件は $$ 1 \le a \le b \le n \quad \text{かつ} \quad a + b \ge n + 1 $$ となる。これを $b$ を固定して考える。 $a$ について整理すると、 $$ n + 1 - b \le a \le b $$ この不等式を満たす整数 $a$ が存在するためには、 $$ n + 1 - b \le b \iff 2b \ge n + 1 $$ が必要である。これと $b \le n$ より、$b$ のとり得る範囲は、 $$ \frac{n+1}{2} \le b \le n $$ となる。ある $b$ に対して、条件を満たす $a$ の個数は、 $$ b - (n + 1 - b) + 1 = 2b - n $$ 個である。これを満たす $b$ について足し合わせる。ここで、$n$ の偶奇で場合分けを行う。

(i) $n$ が偶数のとき

$n = 2k$ ($k$ は正の整数) とおく。 $b$ の範囲は $\frac{2k+1}{2} = k + \frac{1}{2} \le b \le 2k$ であり、$b$ は整数であるから $k + 1 \le b \le 2k$ となる。求める個数は、 $$ \sum_{b=k+1}^{2k} (2b - 2k) $$ これは初項 $2(k+1) - 2k = 2$、末項 $2(2k) - 2k = 2k$、項数 $k$ の等差数列の和であるから、 $$ \frac{1}{2} k (2 + 2k) = k(k+1) $$ $k = \frac{n}{2}$ を代入して、 $$ \frac{n}{2} \left( \frac{n}{2} + 1 \right) = \frac{n(n + 2)}{4} $$

(ii) $n$ が奇数のとき

$n = 2k - 1$ ($k$ は正の整数) とおく。 $b$ の範囲は $\frac{2k}{2} = k \le b \le 2k - 1$ であり、$b$ は整数であるから $k \le b \le 2k - 1$ となる。求める個数は、 $$ \sum_{b=k}^{2k-1} \{2b - (2k - 1)\} $$ これは初項 $2k - (2k - 1) = 1$、末項 $2(2k - 1) - (2k - 1) = 2k - 1$、項数 $k$ の等差数列の和であるから、 $$ \frac{1}{2} k \{1 + (2k - 1)\} = k^2 $$ $k = \frac{n + 1}{2}$ を代入して、 $$ \left( \frac{n + 1}{2} \right)^2 = \frac{(n + 1)^2}{4} $$

解法2

残りの2辺の長さを $x, y$ とおく。条件より $1 \le x \le n, \quad 1 \le y \le n$ である。三角形の成立条件は解法1と同様に $x + y > n$ である。まずは $x \le y$ の制約を設けずに、これを満たす $(x, y)$ の組の総数 $N$ を求める。

全事象である $(x, y)$ の組は $n^2$ 個ある。このうち、$x + y \le n$ となる組の数を引く。 $x + y = m$ ($2 \le m \le n$) と固定すると、これを満たす整数の組 $(x, y)$ は $(1, m-1), (2, m-2), \ldots, (m-1, 1)$ の $m - 1$ 個ある。したがって、$x + y \le n$ を満たす組は $$ \sum_{m=2}^{n} (m - 1) = 1 + 2 + \cdots + (n - 1) = \frac{1}{2} n (n - 1) $$ 個である。よって、$x + y > n$ を満たす $(x, y)$ の組の総数 $N$ は、 $$ N = n^2 - \frac{1}{2} n (n - 1) = \frac{1}{2} n (n + 1) $$ 個となる。

次に、この $N$ 個の組の中で $x = y$ となる組の数 $M$ を求める。 $x = y$ のとき、条件 $x + y > n$ より $2x > n \iff x > \frac{n}{2}$ となる。

(i) $n$ が偶数のとき

$n = 2k$ ($k$ は正の整数) とおくと、$x > k$ より $x = k + 1, k + 2, \ldots, 2k$ となり、$M = k = \frac{n}{2}$ 個である。

(ii) $n$ が奇数のとき

$n = 2k - 1$ ($k$ は正の整数) とおくと、$x > k - \frac{1}{2}$ より $x = k, k + 1, \ldots, 2k - 1$ となり、$M = k = \frac{n + 1}{2}$ 個である。

求める三角形の個数は、順序を無視した組 $\{x, y\}$ の数である。 $N$ 個の組のうち、$x \neq y$ であるものは対称性より $(x, y)$ と $(y, x)$ の2つで1組の三角形に対応する。$x = y$ であるものはそのまま1組の三角形に対応する。したがって、求める個数は $$ \frac{N - M}{2} + M = \frac{N + M}{2} $$ と計算できる。

(i) $n$ が偶数のとき

$$ \frac{1}{2} \left\{ \frac{n(n + 1)}{2} + \frac{n}{2} \right\} = \frac{n(n + 1) + n}{4} = \frac{n(n + 2)}{4} $$

(ii) $n$ が奇数のとき

$$ \frac{1}{2} \left\{ \frac{n(n + 1)}{2} + \frac{n + 1}{2} \right\} = \frac{n(n + 1) + (n + 1)}{4} = \frac{(n + 1)^2}{4} $$

解説

三角形の成立条件を不等式で表し、条件を満たす組を数える場合の数の典型問題である。「合同なものは同じものとみなす」という条件の扱い方が最大のポイントとなる。解法1のように、あらかじめ $a \le b$ と大小関係を設定しておくことで重複を防ぎ、一方の変数を固定してシグマ計算に持ち込むのが最もオーソドックスな手法である。一方、解法2のように、一旦大小関係を無視して全体の数を求めた後、「異なるもののペアの数」と「同じものの数」に分けて順序の重複を解消するアプローチ（重複組合せに似た考え方）も非常に有効であり、計算の見通しが良くなることが多い。なお、答えはガウス記号（床関数）を用いて $\lfloor \frac{(n+1)^2}{4} \rfloor$ と1つの式で表現することも可能である。