トップ› 大阪大学› 1985年› 理系第1問

大阪大学 1985年理系第1問解説

方針・初手

(1) は $a_1 + 2a_2 = n$ を満たす非負整数解の個数を求める問題である。係数の大きい $a_2$ を固定し、$a_1$ がとりうる条件を考えるのが定石である。

(2) は前問の結果を利用する。$a_1 + 2a_2 + 3a_3 = m$ の解の個数 $Y(m)$ を、$a_3$ の値を固定することで $X$ を用いて表す。等式を示すには、$Y(3n)$、$Y(3n+1)$、$Y(3n+2)$ をそれぞれ和の形で書き下し、すべての項が過不足なく現れることを確認する。後半の和の計算では、$X(l)$ が同じ値を $2$ 回ずつとるような数列になるため、$l$ の上限の偶奇によって場合分けをして和を求める。

解法1

(1)

$a_1 + 2a_2 = n$ より、$a_1 = n - 2a_2$ である。 $a_1$ は $0$ 以上の整数であるから、$n - 2a_2 \ge 0$ すなわち $a_2 \le \frac{n}{2}$ が成り立つ。 $a_2$ も $0$ 以上の整数であるため、$a_2$ のとりうる値は $0, 1, 2, \dots, \lfloor \frac{n}{2} \rfloor$ の $\lfloor \frac{n}{2} \rfloor + 1$ 個である。 $a_2$ を一つ決めると $a_1$ はただ一つ定まるため、解の組の個数 $X(n)$ は $a_2$ のとりうる値の個数に等しい。

したがって、$n$ が偶数か奇数かで場合分けをすると、 $n$ が偶数のとき、$a_2$ は $0$ から $\frac{n}{2}$ までの整数をとるため、

$$ X(n) = \frac{n}{2} + 1 $$

$n$ が奇数のとき、$a_2$ は $0$ から $\frac{n-1}{2}$ までの整数をとるため、

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

(2)

$Y(m)$ は、$a_1 + 2a_2 + 3a_3 = m$ を満たす $0$ 以上の整数の組 $(a_1, a_2, a_3)$ の個数である。 $a_3 = k$ ($k$ は $0$ 以上の整数) と固定すると、$a_1 + 2a_2 = m - 3k$ を満たす $0$ 以上の整数の組 $(a_1, a_2)$ の個数となり、これは $X(m-3k)$ 個である。 $a_1, a_2 \ge 0$ より $m - 3k \ge 0$ すなわち $k \le \frac{m}{3}$ であるから、$Y(m)$ は次のように表せる。

$$ Y(m) = \sum_{k=0}^{\lfloor \frac{m}{3} \rfloor} X(m-3k) $$

これを用いて、左辺の $Y(3n)$、$Y(3n+1)$、$Y(3n+2)$ をそれぞれ書き下す。

$$ \begin{aligned} Y(3n) &= \sum_{k=0}^{n} X(3n-3k) = X(3n) + X(3n-3) + \dots + X(0) \\ Y(3n+1) &= \sum_{k=0}^{n} X(3n+1-3k) = X(3n+1) + X(3n-2) + \dots + X(1) \\ Y(3n+2) &= \sum_{k=0}^{n} X(3n+2-3k) = X(3n+2) + X(3n-1) + \dots + X(2) \end{aligned} $$

これら $3$ つの式を辺々加えると、右辺には $X(0)$ から $X(3n+2)$ までのすべての項がちょうど $1$ 回ずつ現れる。したがって、次の等式が成り立つ。

$$ Y(3n) + Y(3n+1) + Y(3n+2) = \sum_{l=0}^{3n+2} X(l) $$

次に、この右辺の値を計算する。 (1) の結果から、任意の $0$ 以上の整数 $m$ に対して $X(2m) = m+1$、$X(2m+1) = m+1$ である。 $M$ を $0$ 以上の整数とし、和を $S(M) = \sum_{l=0}^M X(l)$ とおく。

(i)

$M$ が偶数のとき $M = 2k$ ($k$ は $0$ 以上の整数) とおくと、

$$ \begin{aligned} S(2k) &= \sum_{m=0}^{k-1} \{X(2m) + X(2m+1)\} + X(2k) \\ &= \sum_{m=0}^{k-1} 2(m+1) + (k+1) \\ &= 2 \cdot \frac{k(k+1)}{2} + (k+1) \\ &= k(k+1) + (k+1) \\ &= (k+1)^2 \end{aligned} $$

(ii)

$M$ が奇数のとき $M = 2k+1$ ($k$ は $0$ 以上の整数) とおくと、

$$ \begin{aligned} S(2k+1) &= \sum_{m=0}^{k} \{X(2m) + X(2m+1)\} \\ &= \sum_{m=0}^{k} 2(m+1) \\ &= 2 \cdot \frac{(k+1)(k+2)}{2} \\ &= (k+1)(k+2) \end{aligned} $$

求める値は $M = 3n+2$ のときであるから、$n$ の偶奇で場合分けを行う。

(ア)

$n$ が偶数のとき $n = 2j$ ($j$ は $0$ 以上の整数) とおける。このとき $3n+2 = 6j+2 = 2(3j+1)$ より、$M$ は偶数である。 $S(2k)$ の式で $k = 3j+1$ とすると、

$$ \begin{aligned} S(3n+2) &= (3j+2)^2 \\ &= \left(3 \cdot \frac{n}{2} + 2\right)^2 \\ &= \frac{(3n+4)^2}{4} \end{aligned} $$

(イ)

$n$ が奇数のとき $n = 2j+1$ ($j$ は $0$ 以上の整数) とおける。このとき $3n+2 = 3(2j+1)+2 = 6j+5 = 2(3j+2)+1$ より、$M$ は奇数である。 $S(2k+1)$ の式で $k = 3j+2$ とすると、

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

解説

一次不定方程式の非負整数解の個数を求める典型問題である。多変数の場合は、係数の大きい文字を固定して文字数を減らしていくのが基本である。

(2) の等式の証明は、$Y(3n)$、$Y(3n+1)$、$Y(3n+2)$ の中に $3$ を法とする剰余類がすべて網羅されていることに気付くかがポイントである。式を書き並べて視覚的に確認することで、すっきりと証明できる。後半の和の計算では、数列 $X(l)$ が $1, 1, 2, 2, 3, 3, \dots$ と同じ値を $2$ 回ずつ繰り返す規則性を持つため、隣り合う $2$ 項をペアにして計算するとスムーズである。最後の $l = 3n+2$ が偶数か奇数かによってペアの端数が変わるため、$n$ の偶奇による場合分けが必須となる。