トップ› 九州大学› 2012年› 文系第3問

九州大学 2012年文系第3問解説

方針・初手

(1) は $x$ を $3$ で割った余りに着目して式を変形する。整数の分類や合同式に関する基本的な証明問題である。 (2) は (1) の結果を利用して、条件を満たす整数の組をすべて求める。不定方程式の自然数解（$0$ 以上）を求める問題に帰着する。 (3) は購入金額を最小化する問題である。各セットの単価や、同じ枚数を購入したときの金額を比較することで、効率の悪いセット $B$ の購入数の上限を絞り込むと効率よく調べることができる。

解法1

(1)

$x$ は $0$ 以上の整数である。合同式（法を $3$ とする）を用いて考える。

$$ 100 - 7x \equiv 1 - 1 \cdot x \equiv 1 - x \pmod 3 $$

$\frac{1}{3}(100 - 7x)$ が整数となる条件は、$100 - 7x$ が $3$ の倍数となること、すなわち $100 - 7x \equiv 0 \pmod 3$ となることである。上の合同式より、

$$ 1 - x \equiv 0 \pmod 3 \iff x \equiv 1 \pmod 3 $$

となる。したがって、$100 - 7x$ が $3$ の倍数となるのは $x$ を $3$ で割ったときの余りが $1$ の場合のみである。よって、$\frac{1}{3}(100 - 7x)$ は、$x$ を $3$ で割ったときの余りが $1$ の場合に整数であり、それ以外の場合は整数ではない。

(2)

セット $A$ の購入数を $x$ 、セット $B$ の購入数を $y$ とおく。$x, y$ は $0$ 以上の整数である。乗車券を余らせずすべて利用するので、合計枚数は $100$ 枚である。よって、次の等式が成り立つ。

$$ 7x + 3y = 100 $$

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

$$ y = \frac{100 - 7x}{3} = \frac{1}{3}(100 - 7x) $$

$y$ は $0$ 以上の整数でなければならない。(1) の結果より、$y$ が整数となるのは、$x$ を $3$ で割った余りが $1$ のときである。また、$y \ge 0$ より、

$$ 100 - 7x \ge 0 \implies x \le \frac{100}{7} = 14.2\cdots $$

$x$ は $0$ 以上の整数であるから、$0 \le x \le 14$ を満たす。この範囲で、$3$ で割って $1$ 余る整数 $x$ は、$x = 1, 4, 7, 10, 13$ である。それぞれに対する $y$ の値を求めると、

(i) $x = 1$ のとき、$y = \frac{1}{3}(100 - 7 \cdot 1) = 31$

(ii) $x = 4$ のとき、$y = \frac{1}{3}(100 - 7 \cdot 4) = 24$

(iii) $x = 7$ のとき、$y = \frac{1}{3}(100 - 7 \cdot 7) = 17$

(iv) $x = 10$ のとき、$y = \frac{1}{3}(100 - 7 \cdot 10) = 10$

(v) $x = 13$ のとき、$y = \frac{1}{3}(100 - 7 \cdot 13) = 3$

これらが条件を満たすすべての組である。

(3)

セット $A$ を $x$ セット、セット $B$ を $y$ セット購入するとする（$x, y$ は $0$ 以上の整数）。乗車券は $100$ 枚以上あればよいので、次の不等式が成り立つ。

$$ 7x + 3y \ge 100 $$

このときの購入金額を $Z$ 円とすると、$Z$ は次のように表される。

$$ Z = 480x + 220y $$

ここで、セット $A$ とセット $B$ の金額効率を比較する。セット $A$ を $3$ セット購入すると、乗車券は $21$ 枚で金額は $480 \times 3 = 1440$ 円である。一方、セット $B$ を $7$ セット購入すると、乗車券は $21$ 枚で金額は $220 \times 7 = 1540$ 円である。枚数が同じ $21$ 枚でも、セット $A$ を $3$ セット購入する方が $100$ 円安い。したがって、セット $B$ を $7$ セット以上購入する場合（$y \ge 7$）、そのうちの $7$ セットをセット $A$ の $3$ セットに置き換えれば、総枚数を減らすことなく購入金額を安くすることができる。よって、購入金額が最小となるのは $y \le 6$ の範囲、すなわち $y = 0, 1, 2, 3, 4, 5, 6$ のいずれかの場合である。

各 $y$ について、条件 $7x \ge 100 - 3y$ を満たす最小の整数 $x$ を求め、そのときの金額 $Z$ を計算する。

(i) $y = 0$ のとき

$7x \ge 100$ より、最小の整数 $x$ は $15$ である。 $Z = 480 \cdot 15 + 0 = 7200$

(ii) $y = 1$ のとき

$7x \ge 97$ より、最小の整数 $x$ は $14$ である。 $Z = 480 \cdot 14 + 220 \cdot 1 = 6720 + 220 = 6940$

(iii) $y = 2$ のとき

$7x \ge 94$ より、最小の整数 $x$ は $14$ である。これは (ii) と同じ $x$ であり、$y$ が増えるため金額は高くなる（$Z = 6720 + 440 = 7160$）。

(iv) $y = 3$ のとき

$7x \ge 91$ より、最小の整数 $x$ は $13$ である。 $Z = 480 \cdot 13 + 220 \cdot 3 = 6240 + 660 = 6900$

(v) $y = 4$ のとき

$7x \ge 88$ より、最小の整数 $x$ は $13$ である。これは (iv) より高くなる。

(vi) $y = 5$ のとき

$7x \ge 85$ より、最小の整数 $x$ は $13$ である。これは (iv) より高くなる。

(vii) $y = 6$ のとき

$7x \ge 82$ より、最小の整数 $x$ は $12$ である。 $Z = 480 \cdot 12 + 220 \cdot 6 = 5760 + 1320 = 7080$

以上の結果から、$Z$ が最小となるのは $x=13, y=3$ のときであり、その金額は $6900$ 円である。

解法2

(1) の別解

$k$ を $0$ 以上の整数として、$x$ を $3$ で割った余りで場合分けして考える。

(i) $x = 3k$ のとき

$$ \frac{1}{3}(100 - 7x) = \frac{100 - 21k}{3} = \frac{100}{3} - 7k = 33 - 7k + \frac{1}{3} $$

$33 - 7k$ は整数であるが、$\frac{1}{3}$ は整数ではないため、全体は整数ではない。

(ii) $x = 3k + 1$ のとき

$$ \frac{1}{3}(100 - 7x) = \frac{1}{3}\{100 - 7(3k + 1)\} = \frac{93 - 21k}{3} = 31 - 7k $$

$31$ も $7k$ も整数であるため、全体は整数である。

(iii) $x = 3k + 2$ のとき

$$ \frac{1}{3}(100 - 7x) = \frac{1}{3}\{100 - 7(3k + 2)\} = \frac{86 - 21k}{3} = 28 - 7k + \frac{2}{3} $$

$28 - 7k$ は整数であるが、$\frac{2}{3}$ は整数ではないため、全体は整数ではない。

よって、$\frac{1}{3}(100 - 7x)$ は $x$ を $3$ で割ったときの余りが $1$ の場合のみ整数となる。

解説

1次不定方程式と不等式の応用問題である。 (1) は合同式を用いると計算が非常に簡潔になる。場合分けをして直接代入しても証明としては十分である。 (2) は (1) の誘導に乗ることで、候補となる $x$ を一気に絞り込むことができる。 (3) は条件が等式から不等式に変わる点がポイントである。目的関数の最小化において、効率の良いセットと悪いセットの「交換」を考えると、調べるべき範囲を大きく狭めることができる。この「$21$ 枚を基準とした単価比較」による絞り込みは、最適化問題において非常に有効な考え方である。