トップ› 大阪大学› 1971年› 文系第4問

大阪大学 1971年文系第4問解説

方針・初手

1円、5円、10円の硬貨の枚数をそれぞれ文字でおき、合計金額の条件から方程式を立てる。変数が3つあるが、1円硬貨の枚数を他の2つの変数で表して消去することで、不等式の領域内の格子点の数を数える問題に帰着させる。 (2)では、50円硬貨の枚数を固定し、残りの金額に対して(1)の結果を利用する。

解法1

(1) 1円，5円，10円硬貨の枚数をそれぞれ $x, y, z$（$x, y, z$ は0以上の整数）とする。合計金額が $10n$ 円になるので、以下の式が成り立つ。

$$ x + 5y + 10z = 10n $$

これを $x$ について解くと、

$$ x = 10n - 5y - 10z $$

$x \ge 0$ であるから、

$$ 10n - 5y - 10z \ge 0 $$

両辺を5で割って整理すると、

$$ y + 2z \le 2n $$

これを満たす0以上の整数 $(y, z)$ の組が1つ定まると、$x$ も0以上の整数として一意に定まる。したがって、この不等式を満たす $(y, z)$ の組の個数を求めればよい。

$z$ の値で場合分けをする。$y \ge 0$ であるため、$2z \le 2n$ より $z$ は $0 \le z \le n$ の範囲の整数となる。 $z = k$（$k = 0, 1, 2, \dots, n$）と固定すると、

$$ y \le 2n - 2k $$

これを満たす0以上の整数 $y$ は、$0, 1, 2, \dots, 2n - 2k$ の合計 $(2n - 2k + 1)$ 個ある。したがって、求める総数は、各 $k$ に対する個数を足し合わせて、

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

この和は、初項が $2n + 1$（$k=0$ のとき）、末項が $1$（$k=n$ のとき）、項数が $n + 1$ の等差数列の和であるから、

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

ゆえに、硬貨をとり混ぜて合計 $10n$ 円にするしかたは $(n + 1)^2$ 通りあることが示された。

(2) 50円硬貨の枚数を $w$（$w$ は0以上の整数）とする。これら4種類の硬貨をとり混ぜて合計 1000 円にするとき、1円，5円，10円の硬貨の合計金額は $1000 - 50w$ 円となる。

$$ 1000 - 50w = 10(100 - 5w) $$

$N = 100 - 5w$ とおくと、残りの3種類の硬貨の合計金額は $10N$ 円と表せる。金額は0以上であるから、

$$ 1000 - 50w \ge 0 \implies w \le 20 $$

$w$ は0以上の整数であるから、$w = 0, 1, 2, \dots, 20$ の値をとり、各 $w$ に対して $N$ は $N = 100, 95, 90, \dots, 0$ となる。

$N$ が正の整数のとき、(1) の結果から、1円，5円，10円の硬貨で合計 $10N$ 円にするしかたは $(N + 1)^2$ 通りある。 $N = 0$（すなわち、1000円すべてを50円硬貨で支払う場合）のとき、1円，5円，10円の硬貨はそれぞれ0枚の1通りとなる。これは式 $(N + 1)^2$ に $N = 0$ を代入した値 $(0 + 1)^2 = 1$ と一致する。したがって、$N \ge 0$ のすべての整数について、組み合わせの数は $(N + 1)^2$ 通りとして計算できる。

求める総数は、各 $w$ の場合の数を足し合わせて、

$$ \sum_{w=0}^{20} (100 - 5w + 1)^2 = \sum_{w=0}^{20} (101 - 5w)^2 $$

式を展開して計算する。

$$ \begin{aligned} \sum_{w=0}^{20} (10201 - 1010w + 25w^2) &= 10201 \sum_{w=0}^{20} 1 - 1010 \sum_{w=0}^{20} w + 25 \sum_{w=0}^{20} w^2 \\ &= 10201 \cdot 21 - 1010 \cdot \frac{20 \cdot 21}{2} + 25 \cdot \frac{20 \cdot 21 \cdot 41}{6} \\ &= 214221 - 1010 \cdot 210 + 25 \cdot 2870 \\ &= 214221 - 212100 + 71750 \\ &= 73871 \end{aligned} $$

ゆえに、求めるしかたは 73871 通りである。

解説

一次不定方程式を解く際に、係数が小さい変数を消去して不等式の領域の条件に帰着させる手法は、場合の数を数える問題の定石である。係数の大きい文字から順に値を固定して数え上げると、場合分けがスムーズになる。 (2)では、(1)の形（$10n$ 円）を作り出して結果を再利用することがポイントである。その際、(1)では $n$ が正の整数と指定されていたため、(2)の境界条件となる $N = 0$ の場合がそのまま公式 $(N + 1)^2$ に適用できるかを必ず確認する必要がある。