トップ› 東京工業大学› 1962年› 理系第1問

東京工業大学 1962年理系第1問解説

方針・初手

正の整数 $N$ を $5$ で割った商と余りに着目し、$N=5q+r$ とおいて条件を満たすか考える方法と、$m$ に具体的な値を代入して表される数を順に調べ、法則性と上限を見出す方法が考えられる。

解法1

任意の正の整数 $N$ は、非負整数 $q$ と $0 \leqq r \leqq 4$ を満たす整数 $r$ を用いて、

$$ N = 5q + r $$

と一意に表される。これが $0 \leqq n < m$ を満たす整数 $m, n$ を用いて $N = 5m + n$ と表されたと仮定する。

$$ \begin{aligned} 5m + n &= 5q + r \\ n - r &= 5(q - m) \end{aligned} $$

よって、$n - r$ は $5$ の倍数である。 $k$ を整数として $n - r = 5k$ とおくと、$n = 5k + r$ となり、さらに $m = q - k$ となる。これらが条件 $0 \leqq n < m$ を満たすとすると、

$$ 0 \leqq 5k + r < q - k $$

が成り立つ。左側の不等式 $0 \leqq 5k + r$ について、$0 \leqq r \leqq 4$ であるから、もし $k \leqq -1$ とすると

$$ 5k + r \leqq -5 + 4 = -1 < 0 $$

となり矛盾する。したがって、$k \geqq 0$ である必要がある。

次に右側の不等式 $5k + r < q - k$ を整理すると、

$$ 6k < q - r $$

となる。つまり、$N$ が $5m+n$ （$0 \leqq n < m$）の形に表されるための条件は、「$6k < q - r$ を満たす非負整数 $k$ が存在すること」である。 $k \geqq 0$ より $6k \geqq 0$ であるから、そのような $k$ が存在するためには、少なくとも $k=0$ のとき、すなわち

$$ 0 < q - r \iff q \geqq r + 1 $$

が成り立つことが必要である。逆に $q \geqq r + 1$ であれば、$k=0$ が条件を満たす。したがって、$N$ が題意の形に表されるための必要十分条件は $q \geqq r + 1$ である。

ゆえに、$N$ が題意の形に表されないための条件は

$$ q \leqq r $$

となる。 $0 \leqq r \leqq 4$ の各 $r$ について、$q \leqq r$ を満たす非負整数 $q$ を求め、対応する $N = 5q + r$ を計算する。

$r=0$ のとき、$q=0$。$N = 0$ となるが、正の整数ではないため不適。
$r=1$ のとき、$q=0, 1$。$N = 1, 6$。
$r=2$ のとき、$q=0, 1, 2$。$N = 2, 7, 12$。
$r=3$ のとき、$q=0, 1, 2, 3$。$N = 3, 8, 13, 18$。
$r=4$ のとき、$q=0, 1, 2, 3, 4$。$N = 4, 9, 14, 19, 24$。

以上より、表されない正の整数を列挙すると、 1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 18, 19, 24 となる。

解法2

$m$ の値を小さな整数から順に動かし、$5m+n$ （$0 \leqq n < m$）で表される数を書き出していく。不等式 $0 \leqq n < m$ より $m > 0$ であるから、$m$ は $1$ 以上の整数である。

$m=1$ のとき、$n=0$。値は $5(1)+0 = 5$
$m=2$ のとき、$n=0, 1$。値は $10, 11$
$m=3$ のとき、$n=0, 1, 2$。値は $15, 16, 17$
$m=4$ のとき、$n=0, 1, 2, 3$。値は $20, 21, 22, 23$
$m=5$ のとき、$n=0, 1, 2, 3, 4$。値は $25, 26, 27, 28, 29$

$m \geqq 5$ のとき、$n$ は $0, 1, 2, 3, 4$ をすべてとることができる。したがって、$m=k$ （$k \geqq 5$）のとき、$5k+n$ は $5k, 5k+1, 5k+2, 5k+3, 5k+4$ の連続する $5$ つの整数をすべて表す。 $k$ は $5$ 以上の任意の整数をとれるため、$25$ 以上のすべての整数は表すことができる。

よって、表されない可能性があるのは $1$ から $24$ までの整数のみである。上の実験から、$24$ 以下の正の整数のうち、表されるものは

$$ 5, 10, 11, 15, 16, 17, 20, 21, 22, 23 $$

である。 $1$ から $24$ までの整数のうち、これらを除外したものが表されない正の整数である。

解説

ある特定の形で表される（あるいは表されない）数を求める問題では、「余りによる分類」を行って代数的に処理するか、「具体的に実験」して法則性や上限を見つけるアプローチが有効である。本問は $m$ が大きくなると $n$ のとり得る範囲が広がり、ある一定以上の数はすべて表せるようになる性質を持っているため、解法2のような実験的アプローチが非常に早く確実である。