トップ› 東京工業大学› 1984年› 理系第2問

東京工業大学 1984年理系第2問解説

方針・初手

与えられた3つの不等式を、方程式 $x+y+z=n$ を用いて変形し、各変数に対する上限の条件として捉え直す。正の整数解の個数を求める典型的な問題に帰着されるため、すべての正の整数解の組から「条件を満たさない組（余事象）」を引く方針が考えられる。また、与えられた不等式が三角形の成立条件の形をしていることに着目し、新たな変数を導入して同値変形する解法も有効である。

解法1

方程式 $x+y+z=n$ より、$y+z = n-x$ である。これを不等式 $x \leqq y+z$ に代入すると、$x \leqq n-x$ より $2x \leqq n$、すなわち $x \leqq \frac{n}{2}$ を得る。同様にして、$y \leqq z+x$ および $z \leqq x+y$ から、$y \leqq \frac{n}{2}$ および $z \leqq \frac{n}{2}$ を得る。

したがって求める組の個数は、$x+y+z=n$ を満たす正の整数 $(x,y,z)$ の組全体のうち、条件

$$ x \leqq \frac{n}{2} \quad \text{かつ} \quad y \leqq \frac{n}{2} \quad \text{かつ} \quad z \leqq \frac{n}{2} $$

を満たすものの個数である。ここで、余事象を考える。$x > \frac{n}{2}$ かつ $y > \frac{n}{2}$ と仮定すると、辺々足して $x+y > n$ となるが、これは $x+y+z=n$ かつ $z \geqq 1$ であることに矛盾する。したがって、「$x > \frac{n}{2}$」「$y > \frac{n}{2}$」「$z > \frac{n}{2}$」という3つの事象は互いに排反である。対称性より、$x > \frac{n}{2}$ となる組の個数を求めて3倍し、全体の個数から引けばよい。

$x+y+z=n$ を満たす正の整数の組の総数は、

$$ {}_{n-1}\mathrm{C}_{2} = \frac{(n-1)(n-2)}{2} $$

(i)

$n$ が偶数すなわち $n=2k$ （$k$ は $k \geqq 2$ を満たす整数）のとき

$x \leqq k$ が条件となるため、余事象は $x \geqq k+1$ である。 $x' = x-k$ とおくと、$x' \geqq 1$ であり、方程式は $x' + y + z = k$ となる。これを満たす正の整数の組 $(x', y, z)$ の個数は、

$$ {}_{k-1}\mathrm{C}_{2} = \frac{(k-1)(k-2)}{2} $$

求める組の個数は、全体から余事象の3倍を引いて、

$$ \frac{(2k-1)(2k-2)}{2} - 3 \times \frac{(k-1)(k-2)}{2} = \frac{k-1}{2} \{ 2(2k-1) - 3(k-2) \} = \frac{(k-1)(k+4)}{2} $$

$k = \frac{n}{2}$ を代入して整理すると、

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

(ii)

$n$ が奇数すなわち $n=2k+1$ （$k$ は $k \geqq 1$ を満たす整数）のとき

$x \leqq k+\frac{1}{2}$ であり、$x$ は整数だから $x \leqq k$ が条件となる。余事象は $x \geqq k+1$ であるから、$x' = x-k$ とおくと $x' \geqq 1$。方程式は $x' + y + z = k+1$ となり、これを満たす正の整数の組の個数は、

$$ {}_{k}\mathrm{C}_{2} = \frac{k(k-1)}{2} $$

求める組の個数は、全体から余事象の3倍を引いて、

$$ \frac{2k(2k-1)}{2} - 3 \times \frac{k(k-1)}{2} = \frac{k}{2} \{ 2(2k-1) - 3(k-1) \} = \frac{k(k+1)}{2} $$

$k = \frac{n-1}{2}$ を代入して整理すると、

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

解法2

新たな変数 $X, Y, Z$ を次のように定める。

$$ X = y+z-x, \quad Y = z+x-y, \quad Z = x+y-z $$

与えられた不等式の条件より、$X \geqq 0, Y \geqq 0, Z \geqq 0$ である。また、これらの式を $x, y, z$ について解くと、

$$ x = \frac{Y+Z}{2}, \quad y = \frac{Z+X}{2}, \quad z = \frac{X+Y}{2} $$

$x, y, z$ は正の整数であるから、$X, Y, Z$ は偶奇がすべて一致する整数であり、$Y+Z \geqq 2, Z+X \geqq 2, X+Y \geqq 2$ を満たす。さらに、和について以下が成り立つ。

$$ X+Y+Z = (y+z-x)+(z+x-y)+(x+y-z) = x+y+z = n $$

(i)

$n$ が偶数すなわち $n=2k$ （$k \geqq 2$）のとき

$X+Y+Z = 2k$ であり、偶奇が一致するため $X, Y, Z$ はすべて偶数である。 $X=2A, Y=2B, Z=2C$ （$A, B, C$ は非負整数）とおく。 $2A+2B+2C = 2k$ より $A+B+C = k$。条件 $Y+Z \geqq 2$ は $2B+2C \geqq 2$ より $B+C \geqq 1$ となり、これは $A \leqq k-1$ を意味する。同様に $B \leqq k-1, C \leqq k-1$。すなわち、$A+B+C=k$ を満たす非負整数の組から、1つの変数が $k$ となる（例えば $A=k, B=0, C=0$ のような）3通りを除けばよい。求める個数は、

$$ {}_{k+2}\mathrm{C}_{2} - 3 = \frac{(k+2)(k+1)}{2} - 3 = \frac{k^2+3k-4}{2} = \frac{(k-1)(k+4)}{2} $$

$k = \frac{n}{2}$ を代入して、

$$ \frac{n^2+6n-16}{8} $$

(ii)

$n$ が奇数すなわち $n=2k+1$ （$k \geqq 1$）のとき

$X+Y+Z = 2k+1$ であり、偶奇が一致するため $X, Y, Z$ はすべて奇数である。 $X=2A+1, Y=2B+1, Z=2C+1$ （$A, B, C$ は非負整数）とおく。 $(2A+1)+(2B+1)+(2C+1) = 2k+1$ より $A+B+C = k-1$。このとき、$Y+Z = 2B+2C+2 \geqq 2$ は非負整数 $B, C$ に対して常に成り立つため、上限に関する制約は発生しない。求める個数は、$A+B+C = k-1$ を満たす非負整数の組の個数に等しく、

$$ {}_{(k-1)+2}\mathrm{C}_{2} = {}_{k+1}\mathrm{C}_{2} = \frac{k(k+1)}{2} $$

$k = \frac{n-1}{2}$ を代入して、

$$ \frac{n^2-1}{8} $$

解説

方程式 $x+y+z=n$ の正の整数解の個数を求める問題に上限の条件が加わった、標準的かつ重要な問題である。解法1のように「上限を満たさない事象（余事象）」を利用するのは定石であり、余事象同士が排反になること（2つの変数が同時に半分より大きくなることはない）を見抜ければ、見通しよく計算が進む。解法2の変数変換は、三角形の成立条件を扱う際によく用いられる「Ravi変換」と呼ばれるテクニックの応用である。偶奇による場合分けが必要になるが、計算量が抑えられ、ミスを減らしやすいというメリットがある。どちらの解法も身につけておきたい考え方である。