トップ› 大阪大学› 2000年› 理系第3問

大阪大学 2000年理系第3問解説

方針・初手

$m$ や $n$ に $0, 1, 2, \dots$ などの小さい値を代入し、$x = 5m+3n$ の形で表される整数を具体的に書き出してみる。表される数が連続して $3$ つ見つかれば、そこから $3n$ の $n$ を $1, 2, 3, \dots$ と増やすことで、それ以降のすべての整数が表せることに着目する。あるいは、$x$ を $3$ で割った余りで分類して考える。

解法1

正の整数 $x$ を $3$ で割った余りで分類する。

(i)

$x \equiv 0 \pmod 3$ のとき $x = 3k$ ($k$ は正の整数) と表せる。このとき、$m=0, n=k$ とすれば、$m \ge 0, n \ge 1 > 0$ であり、$x = 5 \cdot 0 + 3k$ と表すことができる。よって、$3$ の倍数である正の整数はすべて表すことができる。

(ii)

$x \equiv 2 \pmod 3$ のとき $x = 3k+2$ ($k$ は $0$ 以上の整数) と表せる。これを変形すると、

$$ x = 5 + 3k - 3 = 5 \cdot 1 + 3(k-1) $$

となる。したがって、$k-1 \ge 0$ すなわち $k \ge 1$ のときは、$m=1, n=k-1$ とすれば $m \ge 0, n \ge 0$ となり $x$ を表すことができる。 $k \ge 1$ は $x \ge 5$ に対応する。残る $k=0$ すなわち $x=2$ のとき、表せるかどうかを考える。 $x=2$ を $5m+3n=2$ とすると、$m \ge 1$ のとき $5m+3n \ge 5$ となるため $m=0$ でなければならない。しかし $m=0$ のとき $3n=2$ となり、これを満たす整数 $n$ は存在しない。よって、$x=2$ は表すことができない。

(iii)

$x \equiv 1 \pmod 3$ のとき $x = 3k+1$ ($k$ は $0$ 以上の整数) と表せる。これを変形すると、

$$ x = 10 + 3k - 9 = 5 \cdot 2 + 3(k-3) $$

となる。したがって、$k-3 \ge 0$ すなわち $k \ge 3$ のときは、$m=2, n=k-3$ とすれば $m \ge 0, n \ge 0$ となり $x$ を表すことができる。 $k \ge 3$ は $x \ge 10$ に対応する。残る $k=0, 1, 2$ すなわち $x=1, 4, 7$ のとき、表せるかどうかを個別に調べる。 $x=1$ のとき、$m \ge 1$ ならば $5m+3n \ge 5$ なので $m=0$ が必要だが、$3n=1$ となり整数 $n$ は存在しない。 $x=4$ のとき、$m \ge 1$ ならば $m=1$ が必要だが、$5 \cdot 1 + 3n = 4$ より $3n=-1$ となり不適。$m=0$ のときは $3n=4$ となり不適。 $x=7$ のとき、$m \ge 2$ ならば $5m+3n \ge 10$ なので不適。$m=1$ のとき $3n=2$ となり不適。$m=0$ のとき $3n=7$ となり不適。よって、$x=1, 4, 7$ は表すことができない。

以上（i）, （ii）, （iii）より、表すことができない正の整数 $x$ は $1, 2, 4, 7$ である。

解法2

$x = 5m+3n$ について、$m$ の値を固定して具体的に表せる数を調べる。

$m=0$ のとき、 $x = 3n$ ($n \ge 0$) より、$x = 0, 3, 6, 9, 12, 15, \dots$ が表せる。 $m=1$ のとき、 $x = 5+3n$ ($n \ge 0$) より、$x = 5, 8, 11, 14, 17, \dots$ が表せる。 $m=2$ のとき、 $x = 10+3n$ ($n \ge 0$) より、$x = 10, 13, 16, \dots$ が表せる。

これにより、$x=8, 9, 10$ という連続する $3$ つの整数が表せることがわかる。任意の整数 $x \ge 8$ は、ある $0$ 以上の整数 $k$ を用いて $x = 8+3k, 9+3k, 10+3k$ のいずれかの形で表すことができる。

$$ \begin{aligned} 8+3k &= 5 \cdot 1 + 3(1+k) \\ 9+3k &= 5 \cdot 0 + 3(3+k) \\ 10+3k &= 5 \cdot 2 + 3k \end{aligned} $$

$k \ge 0$ であれば、それぞれの式における $5$ の係数と $3$ の係数はすべて $0$ 以上の整数となる。したがって、$8$ 以上のすべての正の整数は $x = 5m+3n$ の形で表すことができる。

次に、$x \le 7$ の正の整数について、表せるかどうかを個別に調べる。

$x=1$: $m=0 \implies 3n=1$ (不適)、 $m \ge 1 \implies 5m+3n \ge 5$ (不適)。表せない。 $x=2$: $m=0 \implies 3n=2$ (不適)、 $m \ge 1 \implies 5m+3n \ge 5$ (不適)。表せない。 $x=3$: $m=0, n=1$ のとき $x=3$。表せる。 $x=4$: $m=0 \implies 3n=4$ (不適)、 $m=1 \implies 3n=-1$ (不適)。表せない。 $x=5$: $m=1, n=0$ のとき $x=5$。表せる。 $x=6$: $m=0, n=2$ のとき $x=6$。表せる。 $x=7$: $m=0 \implies 3n=7$ (不適)、 $m=1 \implies 3n=2$ (不適)。表せない。

以上より、表すことができない正の整数 $x$ は $1, 2, 4, 7$ である。

解説

「フロベニウスの硬貨問題」として知られる有名なテーマである。互いに素な正の整数 $a, b$ が与えられたとき、$ax+by$ ($x \ge 0, y \ge 0$) の形で表すことができない最大の整数は $ab - a - b$ であることが知られている。本問では $a=5, b=3$ であるため、表せない最大の数は $5 \times 3 - 5 - 3 = 7$ となる。これを記述試験で示すには、解法1のように法 $3$ や法 $5$ に着目して余りで分類するか、解法2のように「連続する $3$ つの整数が作れれば、それ以降は $3$ を足し続けるだけですべて作れる」という性質を利用するのが定石である。