名古屋大学 1981年度理系数学第4問(a) 解答・解説

問題

$p$ ， $n$ は自然数で $p ≧ 2$ とする． $p^{n}$ より小さい自然数 $l$ を， $l = k = 0 \sum n - 1 a_{k} p^{k}$ （ $a_{k}$ は $0 ≦ a_{k} ≦ p - 1$ なる整数）と表し， $s (l) = k = 0 \sum n - 1 a_{k}$ とおく．このとき， $s (l) + s (p^{n} - l)$ $(1 ≦ l ≦ p^{n} - 1)$ の最小値とそれを与える自然数 $l$ をすべて求めよ．

出典：名古屋大学 1981年度前期日程第2次学力試験理系第4問(a)

方針

$p$ 進法で下位から見て最初に0でない桁を $r$ とする。 $p^{n} - l$ の筆算では、 $r$ 桁目が $p - a_{r}$ 、それより上が $p - 1 - a_{k}$ になる。これを $s (l)$ と足すと $a_{k}$ が消え、 $p + (n - 1 - r) (p - 1)$ となる。最小化は $r$ を最大にするだけなので、 $r = n - 1$ として対応する $l$ を列挙する。

解答

$l ≧ 1$ であるから、下位から見て初めて0でない桁がある。すなわち $a_{0} = a_{1} = \dots = a_{r - 1} = 0, a_{r} \neq = 0$ となる整数 $r$ がただ一つ定まる。ただし $0 ≦ r ≦ n - 1$ である。 $p^{n} - l$ を $p$ 進法の筆算で求める。下位 $r$ 桁は0で、 $r$ 桁目で初めて借り下がりが起こる。したがって $p^{n} - l$ の各桁は、 $0$ 桁目から $r - 1$ 桁目までは0、 $r$ 桁目は $p - a_{r}$ であり、 $r + 1$ 桁目から $n - 1$ 桁目までは $p - 1 - a_{k}$ である。

よって $s (p^{n} - l) = p - a_{r} + \sum_{k = r + 1}^{n - 1} (p - 1 - a_{k})$ である。一方 $s (l) = a_{r} + \sum_{k = r + 1}^{n - 1} a_{k}$ であるから $s (l) + s (p^{n} - l) = p + \sum_{k = r + 1}^{n - 1} (p - 1) = p + (n - 1 - r) (p - 1)$ である。

これは $r$ が大きいほど小さい。よって最小は $r = n - 1$ のときにとられ、その値は $p$ である。このとき $a_{0} = a_{1} = \dots = a_{n - 2} = 0, 1 ≦ a_{n - 1} ≦ p - 1$ なので $l = a p^{n - 1} (a = 1, 2, \dots, p - 1)$ である。

したがって最小値を与える自然数は $p^{n - 1}, 2 p^{n - 1}, \dots, (p - 1) p^{n - 1}$ である。

名古屋大学 1981年度理系数学 第4問(a)

問題

方針

解答

名古屋大学 1981年度
理系数学第4問(a)