集合 $\{3m+5n | m, n \text{ は自然数}\}$ の要素ではない自然数のうち、最大のものを求めよ。

1. 問題の内容

集合 $\{3m+5n | m, n \text{ は自然数}\}$ の要素ではない自然数のうち、最大のものを求めよ。

2. 解き方の手順

この問題は、Frobeniusの硬貨問題の特殊なケースです。一般に、$a$と$b$が互いに素な自然数であるとき、$am + bn$ ($m, n$は非負整数) で表せない最大の整数は $ab - a - b$ で与えられます。

ここでは、$m, n$ は自然数なので、 $m, n \ge 1$ です。

まず、$3m+5n$ で表せる最小の自然数を考えます。$m=1, n=1$のとき、$3m+5n = 3+5 = 8$です。

$3m+5n = k$ で表せない最大の整数を求めます。

$3m+5n$ という形ですべての整数を表すことはできません。例えば、$1, 2, 4, 7$ などは表すことができません。

まず、$m,n$ は非負整数として、$3m+5n$ で表せない最大の整数を求めます。

このとき、$ab - a - b = 3 \times 5 - 3 - 5 = 15 - 8 = 7$ です。

$3m + 5n = 7$ となる非負整数 $m,n$ は存在しません。

$3m + 5n = 8$ となる自然数 $m,n$ は $m=1, n=1$ のとき成り立ちます。

$3m + 5n$ の形の整数で、 $m, n$ が自然数の場合、$3m+5n = 3(m' + 1) + 5(n' + 1) = 3m' + 5n' + 8$ となります（$m'=m-1$, $n'=n-1$）。ここで、$m', n'$ は非負整数です。

$3m' + 5n'$ で表せない最大の整数は7なので、$3m + 5n = 3m' + 5n' + 8$ で表せない最大の整数は $7+8 = 14 - 1 = 7$ではありません。

$3m+5n$ （$m,n$は自然数）の形で表せない最大の自然数を求めるには、まず$3m+5n=k$を表せる最小の整数を求める。それは$3(1)+5(1)=8$である。

次に、8以上の整数がすべて$3m+5n$の形で表せるかを確認する。

$8 = 3(1) + 5(1)$

$9 = 3(3) + 5(0)$ (0は自然数でないので不可)

$10 = 3(0) + 5(2)$ (0は自然数でないので不可)

$11 = 3(2) + 5(1)$

$12 = 3(4) + 5(0)$ (0は自然数でないので不可)

$13 = 3(1) + 5(2)$

$14 = 3(3) + 5(1)$

$3m+5n$ で表せない整数を小さい方から書き出すと $1, 2, 3, 4, 5, 6, 7$ などがあります。

$3m+5n = 7$ は、m, n が自然数では作れない

$3m+5n = 8$ は、m=1, n=1 で作れる

$3m+5n$ という形の整数が連続して3つ以上あれば、それ以降の整数はすべて表せることを利用します。

例えば、$13=3(1)+5(2)$、$14=3(3)+5(1)$、$15=3(5)+5(0)$となり、$n$が自然数という条件を満たさない。

10以上の3の倍数は全て表現できるので、$3m+5n=3(m-5)+5(n+3)$として$n$を大きくすることで、任意の整数が作れます。

$3m + 5n = k$ ($m, n$ は自然数) で表せない最大の整数を求めるためには、まず、ある数以上では必ず表せることを示します。

$8, 11, 14$ が表せるので、$11 = 8+3$, $14 = 11+3$

それ以降の数も必ず表せる。

7は表せない。6, 5, 4, 3, 2, 1も表せない。

よって、7が $3m+5n$ （m, nは自然数）で表せない最大の整数である。

3. 最終的な答え

7